Recursive

Recursive function คืออะไร

คำอธิบาย ฟังก์ชันเรียกตัวเอง (recursive function) คือฟังก์ชันที่สามารถเรียกใช้ตัวมันเองจากภายในนิยาม (หรือคำอธิบาย) ของฟังก์ชัน เป็นวิธีการแก้ไขปัญหาโดยการแบ่งปัญหาใหญ่ให้เป็นปัญหาย่อยๆ ที่มีรูปแบบคล้ายคลึงกัน

ส่วนประกอบสำคัญ

• เงื่อนไขหยุด (Base Case): เงื่อนไขที่ทำให้ฟังก์ชันหยุดเรียกตัวเองซ้ำๆ หากไม่มีเงื่อนไขหยุด ฟังก์ชันจะเรียกตัวเองไม่สิ้นสุด นำไปสู่ปัญหา stack overflow error
• กรณีเรียกตัวเอง (Recursive Case): ส่วนของฟังก์ชันที่ทำให้มีการเรียกใช้ตัวเองอีกครั้ง โดยทั่วไปจะเป็นการเรียกตัวเองด้วยข้อมูลที่ผ่านการดัดแปลงแล้วเพื่อให้เข้าใกล้เงื่อนไขหยุดมากขึ้น

หลักการทำงาน

1. เริ่มต้นด้วยการเรียกใช้ฟังก์ชันครั้งแรก
2. หากเจอเงื่อนไขหยุด ฟังก์ชันจะคืนค่ากลับมา
3. หากไม่เจอเงื่อนไขหยุด กรณีเรียกตัวเองจะทำงาน ทำให้ฟังก์ชันเรียกใช้ตัวเองอีกครั้งด้วยรูปแบบปัญหาย่อยที่ถูกลดขนาดลง
4. การทำงานนี้จะสร้างเป็นลูกโซ่ของการเรียกใช้ฟังก์ชัน โดยแต่ละครั้งจะทำงานบนส่วนที่เล็กลงของปัญหาเดิม
5. เมื่อกระทั่งถึงเงื่อนไขหยุด ผลลัพธ์จะถูกส่งกลับขึ้นบนลูกโซ่ของการเรียกฟังก์ชัน จนท้ายสุดการเรียกใช้ฟังก์ชันครั้งแรกจะได้รับคำตอบสุดท้าย

ทำไมต้องใช้การเรียกตัวเอง (Recursion)?

• ความอ่านง่ายและกระชับ: วิธีแก้ปัญหาแบบ recursive มักจะออกมาสั้นและอ่านง่าย เมื่อใช้กับปัญหาที่สามารถแบ่งย่อยออกเป็นปัญหาเล็กลงที่มีลักษณะคล้ายๆ กัน
• การสำรวจโครงสร้างต้นไม้ (Tree Traversal): การเรียกตัวเองเหมาะมากในการทำงานกับโครงสร้างข้อมูลแบบต้นไม้
• การแก้ปัญหา: ปัญหาบางอย่าง เช่น การคำนวณหาค่าแฟกทอเรียล สามารถอธิบายด้วยกระบวนการแบบ recursive ได้ง่ายกว่าวิธีอื่น

ข้อพิจารณา

• การใช้พื้นที่ของ Stack: Recursion อาจจะใช้หน่วยความจำมากกว่าวิธีการแก้ปัญหาแบบวนลูป (iterative) เพราะมีการเรียกใช้ฟังก์ชันซ้อนกันหลายครั้ง
• ประสิทธิภาพ: ในบางกรณี การแก้ปัญหาแบบวนลูปอาจทำงานได้มีประสิทธิภาพมากกว่า

ตัวอย่าง Recursive function

Factorial (Classic Example)

int factorial(int n) {
    if (n == 0) { // Base Case
        return 1;
    } else {
        return n * factorial(n - 1); // Recursive Case
    }
}

คำอธิบายฟังก์ชัน: โค้ดที่ให้มานี้ได้นิยามฟังก์ชันชื่อว่า "factorial" ทำหน้าที่รับค่าจำนวนเต็ม n เป็นตัวแปรขาเข้า และจะคืนค่าจำนวนเต็มอีกจำนวนหนึ่งออกมา (ซึ่งก็คือค่าแฟกทอเรียลของ n)

กรณีหลัก (Base Case): if (n == 0) { return 1; } บรรทัดนี้เป็นกรณีหลักของฟังก์ชัน โดยนิยามไว้ว่าแฟกทอเรียลของ 0 มีค่าเท่ากับ 1 เมื่อค่า n ที่รับเข้ามาเป็น 0 การเรียกซ้ำ (recursion) จะหยุดลง และฟังก์ชันจะคืนค่า 1

กรณีเรียกซ้ำ (Recursive Case): else { return n * factorial(n - 1); } ตรงนี้คือส่วนสำคัญของกระบวนการ ถ้าตัวแปรขาเข้า n ไม่ใช่ 0 ฟังก์ชันจะคำนวณหาค่าแฟกทอเรียลด้วยวิธี:

• เรียกตัวฟังก์ชันเองอีกครั้ง โดยใส่ค่าที่น้อยกว่าเดิมลงไป 1 ค่า (n-1)
• นำค่า n ในปัจจุบัน ไปคูณกับผลลัพธ์ที่ได้จากการเรียกฟังก์ชันซ้ำ

ตัวอย่างการทำงานของการเรียกซ้ำ: สมมติว่าเราต้องการหาค่าแฟกทอเรียลของ 4 ขั้นตอนจะเป็นดังนี้:

1. การเรียกครั้งแรก: เรียกใช้ factorial(4)
2. ไม่เข้าเงื่อนไขกรณีหลัก: เนื่องจาก n ไม่ใช่ 0 ระบบจะทำงานในส่วนของกรณีเรียกซ้ำ
3. การเรียกซ้ำ: ฟังก์ชันจะคำนวณ 4 * factorial(3) ซึ่งจำเป็นต้องเรียก factorial(3) เพื่อหาผลลัพธ์
4. การเรียกซ้ำต่อเนื่อง: factorial(3) จะเรียก 3 * factorial(2) และ factorial(2) จะเรียก 2 * factorial(1) และต่อกันไปเรื่อยๆ
5. เข้าเงื่อนไขกรณีหลัก: factorial(0) จะเข้าเงื่อนไขกรณีหลัก และคืนค่า 1 ออกมา
6. คำนวณย้อนกลับ: ผลลัพธ์จะถูกส่งย้อนกลับไปตามลำดับการเรียก:
   • factorial(1) จะได้รับ 1 * 1 = 1
   • factorial(2) จะได้รับ 2 * 1 = 2
   • factorial(3) จะได้รับ 3 * 2 = 6
   • factorial(4) จะได้รับ 4 * 6 = 24
7. คืนค่าสุดท้าย: การเรียก factorial(4) ในครั้งแรกจะคืนค่า 24 ออกมา

Fibonacci Sequence

int fibonacci(int n) {
    if (n <= 1) { // Base Case
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // Recursive Case
    }
} 

คำอธิบายฟังก์ชัน: โค้ดที่ให้มานี้นิยามฟังก์ชันชื่อ "fibonacci" ซึ่งทำหน้าที่รับค่าจำนวนเต็ม n เป็นตัวแปรขาเข้า และคืนค่าเลขลำดับที่ n ของชุดตัวเลขฟีโบนัชชี

กรณีหลัก (Base Case): if (n <= 1) { return n; } บรรทัดนี้เป็นกรณีหลักของฟังก์ชัน โดยนิยามไว้ว่าเลขฟีโบนัชชีตัวที่ 0 จะมีค่าเป็น 0 และตัวที่ 1 จะมีค่าเป็น 1 เมื่อฟังก์ชันถูกเรียกด้วยค่าเริ่มต้นเหล่านี้ การเรียกซ้ำ (recursion) จะหยุดลง

กรณีเรียกซ้ำ (Recursive Case): else { return fibonacci(n - 1) + fibonacci(n - 2); } ตรงนี้คือส่วนสำคัญของกระบวนการคิดแบบเรียกซ้ำ เพื่อที่จะคำนวณหาเลขฟีโบนัชชีตัวที่ n ฟังก์ชันจำเป็นต้องหา:

• เลขฟีโบนัชชีตัวที่ (n-1) และ
• เลขฟีโบนัชชีตัวที่ (n-2) ...จากนั้นนำทั้งสองตัวมาบวกกัน!

ตัวอย่างการทำงานของการเรียกซ้ำ: สมมติว่าเราต้องการหาค่าเลขฟีโบนัชชีตัวที่ 5 ขั้นตอนจะเป็นดังนี้:

1. การเรียกครั้งแรก: เรียกใช้ fibonacci(5)
2. เริ่มแยกย่อย: เพื่อที่จะหา fibonacci(5) ฟังก์ชันจะต้องหา fibonacci(4) + fibonacci(3)
3. เรียกซ้ำต่อเนื่อง: ในการคำนวณ fibonacci(4) ต่อไป ก็จะต้องหา fibonacci(3) และ fibonacci(2) เป็นต้น กระบวนการจะแตกแขนงออกไปเรื่อยๆ จนกว่าจะเจอกับกรณีหลัก
4. เข้าเงื่อนไขกรณีหลัก: fibonacci(1) และ fibonacci(0) เข้าเงื่อนไขกรณีหลัก ทำให้แต่ละค่าถูกคืนออกมาโดยตรง (1 และ 0 ตามลำดับ)
5. รวมผลลัพธ์ย้อนกลับ: ผลลัพธ์จากกรณีหลักจะถูกนำกลับมารวมกันตามลำดับที่ถูกเรียกไป
6. คืนค่าสุดท้าย: การเรียก fibonacci(5) ครั้งแรกจะได้รับค่าคำนวณสุดท้ายกลับมา

                              fibonacci(5)
                       /                      \   
               fibonacci(4)               +          fibonacci(3)
              /          \                         /            \
    fibonacci(3)    +    fibonacci(2)        fibonacci(2)     +   fibonacci(1)
   /        \               /       \            /       \          
fibonacci(2) + fibonacci(1)  fibonacci(1)+fibonacci(0) fibonacci(1)+fibonacci(0)