Recursive method

ปกติแล้ว เราสามารถเรียก method นึงจากอีก method นึงได้

static void F() {
    ...
}

static void G() {
    ...
    F();
}

ดังนั้นแล้วการจะเรียก method ตัวเองก็คงไม่ใช่เรื่องแปลก

static void F() {
    ...
    F();
}

ดู ๆ แล้วอาจจะ non-sense นะครับ แต่ในความเป็นจริงแล้วการเขียนโปรแกรมแบบ recursive นี่ก็ช่วยให้โปรแกรมเขียนง่ายขึ้นมาก

ตัวอย่างที่เห็นได้ชัด ก็คือการนิยาม Factorial ในทางคณิตศาสตร์

n! = n * (n - 1)!    โดยที่ 0! = 1

นั่นก็มองเหมือนเป็นการเรียกฟังก์ชัน Factorial แบบ recursive ครับ ถ้าเขียนเป็นโปรแกรมก็คงเขียนได้แบบนี้

static int Fac(int n) {
    int fac;

    if(n == 0) {
        fac = 1;
    } else {
        fac = n * Fac(n - 1);
    }

    return fac;
}

แต่เขียนแบบข้างบนคงยาวไปหน่อย ปกติเค้าเขียนกันสั้น ๆ แบบนี้

static int Fac(int n) {
    if(n == 0) {
        return 1;
    }

    return n * Fac(n - 1);
}

เขียนแบบเชิงคณิตศาสตร์ก็ประมาณนี้

3! = 3 * 2!
   = 3 * 2 * 1!
   = 6 * 1 * 0!
   = 6 *
   = 6

ถ้าไม่มีตรง if(n ==0) ... คงคิดออกกันใช่มั้ยครับ ว่ามันคงเรียก method นี้ไม่จบ ดังนั้นจำไว้นะครับ การเขียน recursive method ทุกครั้งต้องมีการเช็ก ให้หยุดการเรียก method ที่ค่า ๆ หนึ่ง

ลองดูตัวอย่างยอดฮิตอีกอย่างนึงของเรื่องนี้ คือ fibonacci number

f0 = 0, f1 = 1
fn = fn - 1 + fn - 2

ถ้าเขียนเป็น method ก็ควรได้อย่างนี้

static int Fibo(int n) {
    if(n == 0) {
        return 0;
    }

    if(n == 1) {
        return 1;
    }

    return Fibo(n - 1) + Fibo(n - 2)
}

recursive method สามารถเขียนกับกรณีอื่น ๆ ได้อีก ไม่เฉพาะตัวเลขเท่านั้น เช่นในเชิง data structure ก็ทำ tree traversal ด้วยวิธี recursive

หรือในทางคณิตศาสตร์มีนิยามสมาชิก set ของจำนวนเต็มไว้แบบหนึ่ง โดยแค่นิยาม constant และ ฟังก์ชันบางอย่างดังนี้

  • constant 0
  • successor function succ ซึ่งให้ค่าตัวถัดไป
  • predecessor function pred ซึ่งให้ค่าตัวก่อนหน้านี้
  • ...

ดังนั้นจะนิยาม set ของจำนวนเต็มได้ดังนี้

Z = {..., pred(pred(0)), pred(0), 0, succ(0), succ(succ(0)), ...}

และนิยามต่อมาคือ operator +, - ของ set นี้ หรือจะมองเป็นฟังก์ชัน บวก, ลบ ก็ได้

ให้ n, m ∈ Z

add(n, 0) = n
add(n, m) = add(succ(n), pred(n))

sub(n, 0) = n
sub(n, m) = sub(pred(n), pred(m))

เราสามารถเขียนฟังก์ชัน ข้างบนนี้ได้ โดยการนิยาม succ, pred ด้วย operator ++, -- เช่น

static int Add(int n, int m) {
    if(m == 0) {
        return n;
    }

    return Add(++n, --m);
}

static int Sub(int n, int m) {
    if(m == 0) {
        return n;
    }

    return Sub(--n, --m);
}

แต่อาจจะมองแล้วไม่เท่ เอาให้มองสวยหน่อยก็สร้าง method Succ กับ Pred มาก็ดี (ถ้าทำโจทย์ข้อนี้ด้วยภาษา pascal ก็มีฟังก์ชัน pred กับ succ ให้ใช้เลย)

static int Succ(int n) {
    return ++n;
}

static int Pred(int n) {
    return --n;
}

static int Add(int n, int m) {
    if(m == 0) {
        return n;
    }

    return Add(Succ(n), Pred(m));
}

static int Sub(int n, int m) {
    if(m == 0) {
        return n;
    }

    return Sub(Pred(n), Pred(m));
}

static int Mul(int n, int m) {
    ...
}

static int Fac(int n, int m) {
    ...
}

ลองเขียน Mul กับ Fac ต่อ เป็นการบ้านละกันครับ

Hint : ลองนึกถึงนิยามการคูณดูครับ

อ้อ เสริมเล็กน้อย การเขียน method แบบ recursive นี้มีข้อระวังเล็กน้อย คือไม่ควรจะมีการเรียก method นั้นหลายชั้นมากจนเกินไป(โดยเฉพาะการเขียนไม่ครอบคลุม เช่นการเช็กการหยุดการเรียก method ผิด) เพราะจะทำให้ stack ของระบบ overflow ได้

Comment

Comment:

Tweet

<a href="http://uirkxfjvobfldot.com">ssjyeufuyyaytnx</a> http://xuptpjbjwsfgkzx.com [url=http://pzjvhitiltpwwea.com]rcocvhxqqrevfnq[/url]

#18 By ieviukglbf (94.102.52.87) on 2010-06-14 15:38

i cant speak you language
please speak to me in atgvjhy

#17 By (41.196.224.226) on 2009-01-13 16:00

ขอบคุงครับสำหรับโจทย์ดีๆ

#16 By besuto (203.113.60.73) on 2008-01-06 11:14

ผมว่าหา Fac แบบนี้สั้นกว่านะคับ ^^

static int Fac(int n)
{
return (n==0)?1:n * Fac(n - 1);
}

#15 By (58.8.135.95) on 2007-12-11 20:19

static int Fac(int n)
{
return (n==0)?1:n * Fac(n - 1);
}

#14 By ComSpu50 (58.8.135.95) on 2007-12-11 20:19

ผมเอาไปเขียนการแตกภาพออกเป็นชิ้นย่อยอะคับ ใช้ recusive ก้อ work นะคับ

#13 By jack (158.108.166.4 /192.168.2.185) on 2007-09-28 15:49

66666666

#12 By (124.121.149.176) on 2007-06-18 09:35

อ่า....เคยอ่านหลายครั้ง และกลับมาอ่านหลายครั้งแล้ว

ผมก็ยังไม่เข้าใจว่า Recursive ใช้ดีในกรณีไหน

Fibonacci ผมยังไม่เข้าใจน่ะครับ แต่ Factorial กับ Multiply ผมว่าใช้ตัวแปรซัก 1 - 2 ตัว กับ while ดีกว่าน่ะครับ

อย่าง
int Factorial(int F)
{
int f = F;
while(f > 0)
{
F *= f
f--;
}
return(F);
}

การใช้ Recursive ดีกว่าวิธีนี้ยังไงรึครับ?
ยังเขียนไม่ออกเลยค่ะ แต่เห็นเพื่อนบอกว่าใช้ในโปรแกรมเช็คผลการแข่งฟุตบอล เวลามีทีมที่มีคะแนนเท่าแล้วต้องดูมินิลีก

#10 By ~Padchy (158.108.212.55) on 2005-12-05 23:02

แนะนำวิชาที่สอน Scheme ที่มหิดลนครสวรรค์ ความแตกต่างของ Linear Recursive กับ Linear Iterative Function

http://www.nks.cmmu.net/cf/18/226

#9 By ตัวร้าย on 2005-09-02 01:34

เคยใช้ในการหาวันทำงานถัดๆไปในปฏิทินครับ
เนื่องจากในฐานข้อมูลเก็บวันหยุดไว้ด้วย
ประมาณว่าจากวันนี้ไปอีก 10 วันทำงานเป็นวันอะไร
พวก recursive ช่วยได้ครับ

ไม่ก็พวกผังองกรณ์ อันนี้ได้ใช้แน่นอน

#8 By เป้ (203.195.107.230) on 2005-08-11 16:48

> hima
ฟังก์ชันรีเคอร์ซีฟในคณิตศาสตร์ เป็นเรื่องเดียวกับที่ใช้ในการเขียนโปรแกรมครับ สามารถเขียนอธิบายด้วยคณิตศาสตร์ได้เหมือนกัน
http://en.wikipedia.org/wiki/Recursion
http://en.wikipedia.org/wiki/Recursive_function

#7 By PaePae on 2005-07-20 16:18

เรียนคณิตศาสตร์ก็เหมือนจะมีเหมือนกัน function ประเภท recursive :D

ขอแอดเฟเวอริธนะคะ > <

#6 By = HIMA = on 2005-07-13 22:37

JAVA

#5 By hellooak on 2005-07-12 20:33

อีกหน่อยดีกว่า เพิ่งนึกได้ ตัวอย่างที่ใช้ recursive แล้วง่าย ก็มี Travel in Binary tree คับ แบบ pre / in / post order ใน ไม่กี่บรรทัด แต่เข้าใจไม่ค่อยจะง่ายเท่าไหร่ (ต้องเรียน data structure มาด้วยอะ )

#4 By Patr on 2005-07-12 01:08

ความคิดส่วนตัว recursive ทำให้เรามองปัญหาได้ถึง แก่นคับ (เพื่อนผมเคยบอกว่ามันเป็น born to be เลยนะ บางคนยังไงก็คิดไม่ออก : ออกจะเวอร์นิดๆแต่ก็เห็นด้วนส่วนนึง) ส่วนด้านอื่นๆ เห็นด้วยกับทั่งสอง เม้นต์ด้านบน

แต่ส่วนใหญ่ ก็จะเห็น Factorail กับ Fibonacci นี่แหละฮิตนักแล

#3 By Patr on 2005-07-12 01:03

recursive ใช้ได้แค่หลักการเบื้องต้น

แต่ในทางปฏิบัติ recursive ยังไม่อาจตอบสนองได้เพียงพอ เช่น
- stack overflow
- ความซ้ำซ้อนของการคำนวณ (recusive ซ้ำ ๆ แบบเดิม ๆ)
- ความช้าในการทำงาน (call เยอะไปหน่อย)

สมควรจะรู้ไว้ แต่เวลาเอาไปใช้จริงต้องคิดดี ๆ

#2 By PaePae on 2005-07-11 21:26

รู้สึกไม่ดีกับโจทย์ข้อนี้เท่าใหร่ เพราะเคยได้การบ้าน Factorial แล้วเขียนแบบดีๆ ไป กลับโดนว่า ว่าทำไมไม่ใช้ Recursive

จริงๆ แล้วโจทย์ข้อนี้ถือว่าเป็น Bad Practice นะ แต่ยังคิดไม่ออกเลยว่าจะหาโจทย์อย่างอื่นที่ใช้ได้จริง และเข้าใจง่ายด้วยมาใช้ยังไง

#1 By ลิ่ว on 2005-07-11 17:43