.
THUẬT TOÁN ĐỆ QUY
Định nghĩa: một đối tượng gọi là đệ quy nếu bao gồm chính nó hay nó được định nghĩa bởi chính nó.
Một khái niệm X được định nghĩa theo đệ quy nếu trong định nghĩa X có sử dụng ngay chính khái niệm X.
• Ví dụ 1: Định nghĩa số tự nhiên
- 0 là một số tự nhiên.
- n là số tự nhiên nếu n – 1 là số tự nhiên.
• Ví dụ 2: Định nghĩa Hàm giai thừa n!
- 0! = 1
- Nếu n > 0 thì n! = n(n – 1)!
Trong lập trình một chương trình con (hàm, thủ tục) được gọi là đệ qui nếu trong quá trình thực hiện nó có phần phải gọi đến chính nó.
Cấu trúc chính
Một chương trình con đệ qui căn bản gồm hai phần.
• Phần cơ sở: chứa các tác động của hàm hoặc thủ tục với một số giá trị cụ thể ban đầu của tham số.
• Phần đệ qui: định nghĩa tác động cần được thực hiện cho giá trị hiện thời của các tham số bằng các tác động đã được định nghĩa trước đây với kích thước tham số nhỏ hơn.
Ví dụ: Hàm tính giai thừa của một số tự nhiên n (tính n!) (Đoạn mã sau được viết bằng ngôn ngữ Pascal)
Qui trình thực hiện
Trong ví dụ trên, qui trình thực hiện như sau:
• Khi có lệnh gọi hàm, chẳng hạn:
x := gt(3);
• thì máy sẽ ghi nhớ là:
gt(3) := 3 * gt(2);
và đi tính gt(2)
• kế tiếp máy lại ghi nhớ:
gt(2) := 2 * gt(1);
và đi tính gt(1)
• Theo định nghĩa của hàm thì:
gt(1) := 1;
• Máy sẽ quay ngược lại:
gt(2) := 2 * 1;
cho kết quả là 2
• Tiếp tục:
gt(3) := 3 * 2;
cho kết quả là 6
• Như vậy kết quả cuối cùng trả về là 6. Ta có: 3! = 6.
Bài tập:
1. Viết chương trình tính 1+2+…+n với n được nhập từ bàn phím bằng thuật toán đệ quy
2. Nhập vào số n. Tính tổng các chữ số của n bằng thuật toán đệ quy
