Principles of Recursion in Data Structures (หลักการของ Recursion)

Recursion (การเรียกซ้ำ) คือกระบวนการที่ฟังก์ชันเรียกตัวเอง ใช้แก้ปัญหาใหญ่โดยแบ่งเป็นย่อยปัญหาเล็กลง ถ้าย่อยปัญหาแต่ละอันมีรูปแบบเดียวกัน จึงใช้ Recursive Approach ได้

Recursive Function มี 2 ส่วน: Base Case (กรณีฐาน - หยุดการเรียกซ้ำ) และ Recursive Case (กรณีเรียกซ้ำ) ถ้าไม่มี Base Case จะเรียกซ้ำอนันต์ (ทฤษฎี)

ในโปรแกรม เรียกฟังก์ชันจะเก็บ Program Counter ลง Stack ก่อนกระโดดเข้าไปทำงาน จบแล้ว Pop ออกมาใส่กลับคืนทำงานต่อ ใน Recursive Call จะเก็บ Address หลายครั้ง ถ้าไม่มี Base Case Stack จะเต็ม → Stack Overflow

ตัวอย่าง: หา Factorial n! = n × (n-1)! เรียกซ้ำจน argument = 0 หรือ 1 คืนค่า 1 (Base Case)

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

long fact(long n) {
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}

main() {
    cout << "Factorial of 6: " << fact(6);
}

Output

Factorial of 6: 720