Đệ quy và giải thuật

Đệ 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