Thuật toán Đệ quy - Các ví dụ

Thuật toán đệ quy
1. Định nghĩa
Ta nói một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng với chính nó bằng quy nạp.
Nếu lời giải của một bài toán T được thực hiện bằng lời giải của bài toán T’ có dạng giống T thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy được gọi là giải thuật đệ quy. Chú ý, T’ có dạng giống T nhưng theo một nghĩa nào đó thì T’ phải “nhỏ” hơn T, dễ giải hơn T và việc giải T’ không phụ thuộc vào T.
Ta đã biết đến khá nhiều ví dụ nổi tiếng về bài toán đệ quy và lời giải của nó như : bài toán tháp Hà Nội, số Fibonacci …
Định nghĩa một hàm đệ quy như sau:
-Phần neo: Phần này sẽ được thực hiện khi công việc quá đơn giản, có thể giải trực tiếp, nhanh chóng mà không cần nhờ đến một bài toán con nào.
-Phần đệ quy: Thực hiện khi bài toán phức tạp hơn, chưa thể giải được bằng phần neo, ta xác định những bài toán con và đệ quy để giải những bài đó. Khi đã có lời giải của những bài toán con rồi thì phối hợp lại để giải bài toán gốc.
Phần đệ quy thể hiện tính quy nạp của thuật toán đệ quy.
Vì mỗi lần gọi đệ quy bộ nhớ sẽ cần 1 lưu trữ 1 vùng nhớ mới trong khi vùng nhớ cũ vẫn phải duy trì, nên trong các ứng dụng thực tế số lần gọi đệ quy không những phải hữu hạn mà còn phải đủ nhỏ.
2. Các dạng đệ quy thông thường
2.1 Đệ quy tuyến tính
Có dạng:
P = { if thỏa điều kiện dừng then thực hiện S;
else
{thực hiện S*;
gọi P}
}
(S, S* là các thao tác không đệ quy)
Ví dụ: hàm tính số hạng n của dãy n!


2.2 Đệ quy nhị phân
Có dạng:
P= {if thỏa điều kiện dừng thenthực hiện S;
else
{thực hiện S*;
gọi P;
gọi P}
}
(S, S* là các thao tác không đệ quy)
Ví dụ: hàm tính số hạng n của dãy Fibonacci


2.3 Đệ quy phi tuyến
Có dạng
P= {forgiá trị đầu to giá trị cuối do
{thực hiện S;
if(thỏa điều kiện dừng) then thực hiện S*
else gọi P
}
}
Ví dụ: tính Xn theo công thức truy hồi:
X0 = 1; Xn = n2X0 + (n-1)2X1 + … + 22Xn-2 + 12Xn-1


2.4 Đệ quy quay lui
Có dạng
P= { for giá trị đầu to giá trị cuối do
{thực hiện S;
if(thỏa điều kiện) then
{gọi P;
Trả lại giá trị ban đầu cho S}
}
}
Ví dụ: thủ tục tìm kiếm theo chiều sâu

Các bạn thấy đấy, thuật toán đệ quy là một thuật toán lập trình khá đơn giản, khá dễ dàng áp dụng cho các bài toán, nhưng khi lập trình các bạn nên lưu ý đến dung lượng bộ nhớ. Chúc các bạn thành công !