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 !
Nguyễn Thị Xuân
School@net (Theo THNT)
|