Đệ quy nhị phân (Binary Recursion)
Là một dạng đệ quy nâng cấp hơn, trong mỗi hàm đệ quy sẽ có một dòng lệnh gọi lại chính hàm đó 2 lần. Cùng xem xét bài toán sau: Dãy số Fibonaci được định nghĩa theo công thức:
Hãy tìm số fibonaci thứ n?
Ta thấy số fibonaci là một đối tượng có bản chất đệ quy, do đó ta có thể tìm được số fibonaci thứ n bằng một hàm đệ quy nhị phân như sau:
int fibo_n(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fibo_n(n - 1) + fibo_n(n - 2);
}
Đặc điểm:
- Đơn giản: Mã nguồn rất đơn giản và dễ hiểu.
- Hiệu suất kém: Đệ quy lồng cho Fibonacci không hiệu quả về mặt tính toán, vì có rất nhiều lời gọi đệ quy trùng lặp. Độ phức tạp thời gian là O(2n).
- Tốn bộ nhớ: Sử dụng nhiều ngăn xếp đệ quy, có thể dẫn đến tràn ngăn xếp khi
nlớn. -
Tối ưu hóa bằng cách sử dụng bộ nhớ đệm (Memoization).
So sánh giữa cài đặt đệ quy và cài đặt không đệ quy:
Từ bài toán dãy Fibonaci
Mọi bài toán có bản chất đệ quy đều có thể chuyển về cách cài đặt khử đệ quy, bởi vì thực tế các hàm đệ quy sẽ được chương trình dịch chuyển về những mã lệnh không đệ quy trước khi thực hiện. Vì thế, bài toán Fibonaci có thể viết được lại ở dạng không đệ quy sử dụng mảng một chiều như sau:
int fibo_n(int n)
{
if (n <= 1)
return n;
int f[n + 1];
f[0] = 0, f[1] = 1;
for (int i = 2; i <= n; ++i)
f[i] = f[i - 1] + f[i - 2];
return f[n];
}
Nếu nhìn thoáng qua về độ dài thì cả hai giải thuật đệ quy và không đệ quy của bài toán này đều như nhau. Nhưng nếu phân tích về số lần tính toán, thì câu chuyện sẽ trở nên khác đi rất nhiều. Nếu cùng tính giá trị f(5), thì giải thuật không đệ quy chỉ cần mất đúng 6 bước tính toán, vì kết quả các bài toán sau khi tính xong sẽ được lưu lại luôn trên mảng một chiều, chỉ cần sử dụng luôn để tính toán. Còn đối với giải thuật đệ quy, thì việc phân tách các bài toán con sẽ diễn ra như sau:
Ta thấy để tính được bài toán f(5), chương trình phải tính lại 1 lần 𝑓(4), 2 lần 𝑓(3), 3 lần 𝑓(2), 5 lần f(1) và 3 lần f(0). Đó gọi là sự xuất hiện của các bài toán con gối nhau, khiến cho chương trình phải tính toán lại nhiều lần một bài toán trong khi đáng lẽ nó chỉ cần tính một lần, từ đó làm cho chương trình chạy rất chậm. Đối với những hàm đệ quy có nhiều lời gọi hơn thì độ phức tạp tính toán sẽ còn tăng lên gấp nhiều lần hơn nữa!