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 X_n theo công thức truy hồi:

X₀ = 1; X_n = n²X₀ + (n-1)²X₁ + … + 2²X_n-2 + 1²X_n-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

School@net (Theo THNT)