Đệ qui và giải thuật đệ qui
Quang Hưng
* Khái niệm về đệ qui
Một đối tượng là đệ qui nếu nóbao gồm chính nó như một bộ phận hoặc có được định
nghĩa dưới dạng chính nó.
Ví dụ: Trên vô tuyến truyền hình,có những hình ảnh đệ qui như: phát thanh viên ngồi bên
máy vô tuyến truyềnhình, trên màn hình của máy này lại có chính hình ảnh của phát thanh
viên ấyngồi bên máy vô tuyến truyền hình và cứ như thế...
Trong Toán học, ta cũng thường hay gặp các định nghĩa đệ qui:
1) Số tự nhiên:
a) 1 là một số tự nhiên
b) x là số tự nhiên nếu x-1 là số tự nhiên
2) Hàm giai thừa: n!
a) 0!=1
b) Nếu n>0 thì n! = n(n -1)!
* Giải thuật đệ qui và thủ tục đệ qui
Nếu lời giải của một bài toán T được thực hiện bằng lời giải của một bài toán T có dạng
giống như T, thì đó là một lời giải đệ qui. Giải thuật tương ứng với lời giải như vậy gọi là
giải thuật đệ qui.
Thoạt nghe thì các bạn thấy có vẻ hơi lạ nhưng điểm mấu chốt cần lưu ý là: T? tuy có dạng
giống như T, nhưng theo một nghĩa nào đó, nó phải "nhỏ" hơn T.
Hãy xét bài toán tìm một từ trongmột quyển từ điển. Có thể nêu giải thuật như sau:
if Từ điển là một trang
then Tìm từ trong trang này
else begin
Mở từ điển vào trang giữa
Xác định xem nửa nào của từ điển chứa từ cần tìm
if Từ đó nằm ở nửa trước của từ điển
then Tìm từ đó trong nửa trước
else Tìm từ đó trong nửa sau
end;

end;
{TD 1 và TD 2 là đầu mối để truy nhập đượcvào nửa trước và nửa sau của từ điển}
3. Return
Thủ tục như trên được gọi là thủtục đệ qui. Từ đó, có thể nêu ra mấy đặc điểm sau:
a) Trongthủ tục đệ qui có lời gọi đến chính thủ tục đó.ởđây, trong thủ tục TIMKIEM có
call TIMKIEM.
b) Mỗilần có lời gọi lại thủ tục thì kích thước của bài toán đã thu nhỏ hơn trước. ở đây khi
có call TIMKIEM thì kích thướctừ điển chỉ còn bằng một "nửa" trước đó.
c) Cómột trường hợp đặc biệt: trường hợp suy biến. Đó chính là trường hợp mà từ điểnchỉ
còn là một trang. Khi trường hợp này xảy ra thì bài toán còn lại sẽ đượcgiải quyết theo một
cách khác hẳn và gọi đệ qui cũng kết thúc. Chính tình trạngkích thước của bài toán cứ
giảm dần sẽ đảm bảo dẫn tới trường hợp suy biến.
Một số ngôn ngữ lập trình nhưPascal chẳng hạn, cho phép viết các thủ tục đệ qui. Nếu thủ
tục chứa lời gọiđến chính nó, như thủ tục TIMKIEM ở trên thì nó được gọi là đệ qui trực
tiếp.Cũng có dạng thủ tục chứa lời gọi đến thủ tục khác mà ở thủ tục này lại chứalời gọi
đến nó. Trường hợp này gọi là đệ qui gián tiếp.
* Thiết kế giải thuật đệ qui
Khi bài toán đang xét hoặc dữliệu đang xử lý được định nghĩa dưới dạng đệ qui thì việc
thiết kế các giảithuật đệ qui tỏ ra rất thuận lợi. Hầu như nó phản ánh rất sát nội dung của
địnhnghĩa đó. Các bạn có thể thấy điều này qua bài toán sau:
* Bài toán Dãy số FIBONACCI
Dãy số Fibonacci bắt nguồn từ bàitoán cổ về việc sinh sản của các cặp thỏ. Bài toán được
đặt ra như sau:
1) Cáccon thỏ không bao giờ chết.
2) Haitháng sau khi ra đời một cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực và mộtcái).
3) Khiđã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới.
Giả sử bắt đầu từ một cặp mới rađời thì đến tháng thứ n sẽ có bao nhiêu cặp?
Ví dụ: n=6, ta thấy:
Tháng thứ 1: 1 cặp (cặp banđầu)
Tháng thứ 2: 1 cặp (cặp banđầu vẫn chưa đẻ)

FunctionFIBONACCI(n)
1. if n<=2 then FIBONACCI:=1;
2. Fib1:=1; Fib2:=2;
3. For i:=3 to no do begin
Fibn:=Fib1+ Fib2;
Fib1:=Fib2;