Đệ quy đuôi (Tail Recursion) trong cấu trúc dữ liệu

Đệ quy đuôi (Tail Recursion) là khi lời gọi hàm đệ quy là câu lệnh cuối cùng của hàm. Khi không còn việc gì sau khi trả về từ lời gọi đệ quy, đó là tail recursion.

Ví dụ đơn giản

#include <iostream>
using namespace std;

void printN(int n) {
    if(n < 0) return;
    cout << n << " ";
    printN(n - 1); // tail call
}

int main() { printN(10); }

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

Tail recursion tốt hơn non-tail recursion. Vì không có việc sau lời gọi đệ quy, compiler dễ tối ưu hóa (không cần lưu địa chỉ trả về vào stack).

Ví dụ: Giai thừa (Factorial)

Đệ quy thường (không phải tail):

long fact(int n) {
    if(n <= 1) return 1;
    return n * fact(n-1); // dùng kết quả fact(n-1) -> không phải tail
}

Chuyển thành tail recursion bằng tham số tích lũy (accumulator):

long fact(long n, long acc) {
    if(n == 0) return acc;
    return fact(n-1, acc * n); // tail call
}