GA BDHSG KN ĐỆ QUI

ĐỆ QUI
KHÁI NIỆM
Một khái niệm X được định nghĩa theo đệ qui nếu trong địng nghĩa X có sử dụng ngay chính khái niệm X.
Ví dụ1:
Số tự nhiên:
0 là số tự nhiên
n là số tự nhiên nếu n-1 là số tự nhiên
Ví dụ2:
Hàm giai thừa n!
0!=1
Nếu n > 0 thì n!=n(n-1)!
CHƯƠNG TRÌNH CON ĐỆ QUI
Khái niệm
Một chương trình con đệ qui(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 của chương trình con đệ qui
Một chương trình con đệ qui căn bản gồm hai phần:
Phần cố định: Chứa các tác động của hàm hoặc thủ tục với một số giá trị ban đầu của tham số.
Phần hạ bậc: Định nghĩa tác động cần được thực hiện cho giá trị hiện thời của tham số bằng các tác động đã được định nghiã 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 n (tính n!)
Function gt(n: Word): Longint;
Begin
  if n<= 1 then
    gt := 1
  else
    gt := n * gt(n - 1);
End;
Quá trình thực hiện
Trong ví trên, qui trình sau:
Khi có hàm, :     x := gt(3);
Thì máy ghi