Đệ Quy

Khái niệm

Trong thực tế, có sự việc được định nghĩa bằng chính nó. Ví dụ như ta định nghĩa hoa hậu quốc gia, chính là hoa hậu của các hoa hậu tỉnh, mà hoa hậu tỉnh là là hoa hậu của các hoa hậu huyện. Có nghĩa là hoa hậu được định nghĩa dựa trên hoa hậu.

ví dụ thứ hai là giai thừa, giai thừa, chẳng hạn giai thừa 5 tức là lấy 5 nhân với 4 giai thừa, mà giai thừa 4 là 4 nhân với 3 giai thừa, ....Như vậy ta tính giai thừa dựa trên giai thừa.

Cụ thể như sau

Mô tả đệ quy tập số tự nhiên

Số 1 là số tự nhiên

Số tự nhiên bằng số tự nhiên công 1

Mô tả đệ quy giai thừa

0!=1

n!=n*(n-1)!

Mô tả đệ quy giai thừa

0!=1

n!=n*(n-1)!

Cài đặt

Việc cài đặt đệ quy đòi hỏi phải nắm vững kiến thức về chương trình con. Thực tế giải thuật đệ quy khi cài đặt là ta sẽ gọi lại chính chương trình con đó bên trong nó.

Để cài đặt được giải thuật đệ quy, em phải xác định được hai yếu tố sau đây

• Phần neo

• Công thức truy hồi

Trong đó

• Phần neo: là giá trị cuối cùng mà tại đó ta có ngay kết quả

• Công thức truy hồi là biểu thức mà ta tính toán một giá trị dựa vào giá trị nhỏ hơn nó, quá trình này cứ thực hiện cho đến khi gặp neo

Ví dụ:

Tính giai thừa:

- Phần neo: 0! = 1

- Công thức truy hồi: n!=n*(n-1)!

Khi cài đặt ta viết như sau

1. Function giaithua(n:word):integer;

2. begin

3. if n=0 then giaithua:=1

4. else giaithua:=giaithua(n-1)*n

5. end;

Cơ chế thực hiện giải thuật đệ quy:

Cơ chế chung khi thực hiện chương trình đệ quy là:Ghi nhớ lại trạng thái đang thự hiện dang dở

Tính toán kết quả trạng thái nhỏ hơn

Trả kết quả lại để tính toán cho trạng thái dang dở

Nên ngoài việc lưu trữ các thông tin về biến và lệnh được được thực thi tiếp theo, chương trình con đệ quy phải lưu trữ thêm trạng thái đang dang dở

Tuy nhiên cách thực thi của từng loại đệ quy mà ta nêu ở trên có khác nhau.

Khử đệ quy