Chuyên đề: ĐỆ QUI

1. KHÁI NIỆM

Một đối tượng gọi là đệ qui nếu có bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng chính nó.
Ví dụ:

a. Số tự nhiên

 - 1 là một số tự nhiên.
 - x là số tự nhiên nếu x-1 là số tự nhiên.

b. Hàm n giai thừa: n!

 - 0! = 1
 - Nếu n>0 thì n! = n*(n-1)!

2. THỦ TỤC ĐỀ QUI

Một 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ó nhưng với kích thước nhỏ hơn của tham số.
Ví dụ:  Function GT( n:word): longint;
                Begin
                      if n=0 then GT:=1
                           else GT:= n*GT(n-1);
                End;

3. CẤU TRÚC CỦA MỘT THỦ TỤC ĐỆ QUI

Một thủ tục đệ qui luôn gồm hai phần:
- Phần neo: Trong đó 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ố.
Ví dụ:
      if n=0 then GT:=1
- Phần hạ bậc: Trong đó tác động cần được thực hiện cho giá trị hiện thời của các tham số được định nghĩa bằng các tác động đã được định nghĩa trước đây.
Ví dụ:  GT:= n* GT(n-1)

4. ƯU ĐIỂM CỦA ĐỆ QUI

* Đệ qui mạnh ở chỗ có thể định nghĩa một tập rất lớn các tác động chỉ bởi một số hữu hạn các mệnh đề.
* Rất thích hợp để giải các bài toán có bản chất đệ qui
* Một chương trình viết theo giải thuật có tính đệ qui sẽ:
       - Sáng sủa
       - Dễ hiểu
       - Nêu bật được bản chất của vấn đề
* Có nhiều bài toán mà việc nghĩ ra lời giải đệ qui thường dễ hơn nhiều so với việc nghĩ ra lời giải dùng vòng lặp.
* Khử đệ qui:
       - Có một số giải thuật đệ qui thuộc loại tính toán đơn giản có thể được thay thế bởi một giải thuật khác không tự gọi chúng, sự thay thế đó được gọi là khử đệ qui.
       - Tuy nhiên điều trên không có nghĩa là phải khử đệ qui bằng mọi giá và không nên e ngại cũng như có ác cảm với việc dùng đệ qui.

5. ĐỆ QUI VÀ QUAY LUI

- Trong lập trình, phương pháp giải một bài toán tổng quát rất được chú ý. Đó là việc xác định các giải thuật để tìm lời giải cho một bài toán nào đó không phải theo một luật tính toán cố định mà bằng phương pháp "thử và sai"
- Thông thường ta phân tích quá trình thử và sai thành các công việc cục bộ dưới dạng một cây tìm kiếm và ta phải từng bước duyệt cây tìm kiếm đó một cách đệ qui theo cấp của cây.
- Trong nhiều bài toán, cây tìm kiếm này lớn lên rất nhanh theo hướng hàm mũ và công sức tìm kiếm cũng tăng theo với sự lớn lên của cây.
- Trong thực tế ta phải tỉa cây tìm kiếm bằng các cách Heuristic và như vậy ta đã làm giảm công sức tính toán tới một giới hạn có thể chấp nhận được.
- Nét đặc trưng của phương pháp này là ở chỗ các bước đi đến lời giải hoàn toàn bằng cách làm thử. Nếu có một lựa chọn được chấp nhận thì ghi nhớ các thông tin cần thiết và tiến hành các bước thử tiếp theo. Nếu trái lại không có một lựa chọn nào thích hợp cả thì làm lại bước trước, xóa bớt các ghi nhớ và quay về chu trình thử với các lựa chọn còn lại. Hành động này được gọi là quay lui (Back tracking) và các giải thuật thể hiện phương pháp này gọi là các giải thuật quay lui.
- Hơn nữa nếu ở mỗi bước số những nước có thể đi là m thì ta có thể dùng một tham số để chỉ độ sâu của sự đệ qui và như thế làm đơn giản đi kiều kiện dùng theo sơ đồ sau: