Đệ quy đuôi (Tail Recursion)

Đệ quy thông thường cho dãy Fibonacci:

Trước hết, hãy xem cách triển khai đệ quy thông thường của dãy Fibonacci trong C++:

#include <iostream>

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

int main() {
    int n = 10;
    std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
    return 0;
}

Trong cách triển khai này, mỗi lần gọi hàm fibonacci đều thực hiện thêm công việc sau khi lời gọi đệ quy hoàn thành, do đó không phải là đệ quy đuôi.

Đệ quy đuôi (Tail Recursion) cho dãy Fibonacci:

Để chuyển đổi thành đệ quy đuôi, chúng ta cần một hàm trợ giúp (helper function) để giữ trạng thái của phép tính:
 

#include <iostream>

// Hàm đệ quy đuôi (hàm trợ giúp)
int fibonacci_tail(int n, int a, int b) {
    if (n == 0) {
        return a;
    } else if (n == 1) {
        return b;
    } else {
        return fibonacci_tail(n - 1, b, a + b);
    }
}

// Hàm chính để gọi hàm đệ quy đuôi
int fibonacci(int n) {
    return fibonacci_tail(n, 0, 1);
}

int main() {
    int n = 10;
    std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
    return 0;
}

Giải thích:

1. Hàm trợ giúp fibonacci_tail:

   • Đây là hàm đệ quy đuôi thực sự.
   • a và b là hai biến giữ trạng thái của hai số Fibonacci liền kề.
   • Khi n là 0, giá trị trả về là a, tương ứng với Fibonacci(0).
   • Khi n là 1, giá trị trả về là b, tương ứng với Fibonacci(1).

2. Hàm chính fibonacci:

   • Hàm này đơn giản gọi hàm trợ giúp fibonacci_tail với các giá trị khởi đầu cho a và b là 0 và 1 tương ứng.

3. Đệ quy đuôi:

   • Ở đây, lời gọi đệ quy cuối cùng trong hàm fibonacci_tail không cần thực hiện thêm công việc nào sau đó, vì vậy đây là đệ quy đuôi.
   • fibonacci_tail(n - 1, b, a + b) là lời gọi đệ quy cuối cùng và tất cả các giá trị cần thiết đã được tính toán trước khi gọi hàm.

Ưu điểm của đệ quy đuôi:

• Hiệu quả về bộ nhớ: Nếu trình biên dịch của C++ hỗ trợ tối ưu hóa đệ quy đuôi, nó có thể chuyển đổi lời gọi đệ quy thành vòng lặp nội bộ, giúp tiết kiệm bộ nhớ và tránh tràn ngăn xếp.
• Dễ hiểu: Đệ quy đuôi tương đương với việc sử dụng vòng lặp, giúp mã nguồn dễ hiểu và bảo trì hơn.

Kết luận:

Đệ quy đuôi là một kỹ thuật mạnh mẽ trong lập trình đệ quy, giúp cải thiện hiệu suất và độ an toàn của mã nguồn. Bằng cách sử dụng hàm trợ giúp và các tham số bổ sung để lưu trữ trạng thái, chúng ta có thể chuyển đổi các hàm đệ quy thông thường thành đệ quy đuôi, tối ưu hóa hiệu suất và tránh các vấn đề về bộ nhớ.