Tail Recursion ในโครงสร้างข้อมูล

Tail Recursion คืออะไร?

Tail Recursion คือการเรียกฟังก์ชัน Recursive เป็น คำสั่งสุดท้าย ของฟังก์ชัน ไม่มีงานเหลือหลังจาก Recursive Call กลับมา

ตัวอย่าง: Print N ถึง 0

void printN(int n) {
    if (n < 0) return;
    cout << n << " ";
    printN(n - 1);  // Tail Recursive Call
}

Output: 10 9 8 7 6 5 4 3 2 1 0

ข้อดีของ Tail Recursion

• Compiler สามารถ Optimize (Tail Call Optimization) ได้
• ไม่ต้องเก็บ Address ใน Stack ทุกครั้ง → ประหยัด Memory และป้องกัน Stack Overflow

ตัวอย่างที่ไม่ใช่ Tail Recursion: Factorial

long fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);  // ไม่ใช่ Tail Recursion - ต้องคูณ n หลัง Return
}

ปรับให้เป็น Tail Recursion

long fact(long n, long acc) {
    if (n == 0) return acc;
    return fact(n - 1, acc * n);  // Tail Recursive - Accumulator Pattern
}