Đệ qui và một số bài toán đệ qui ( Cấu trúc dữ liệu và giải thuật)

Trong lĩnh vực lập trình, một chương trình máy tính gọi là đệ qui nếu trong chương trình có lời gọi chính nó. Điều này nghe có vẻ vô lý, nhưng chương trình không thể gọi mãi chính nó vì sẽ tạo ra vòng lập vô hạn. Trên thực tế, khi viết một chương trình đệ qui thì bao giờ người lập trình cũng có một thao tác gọi là điều kiện dừng. Nói ngắn gọn thì một chương trình đệ qui thường có các đặc điểm sau:

Chương trình có thể gọi lại chính nó.

Khi chương trình gọi lại chính nó, mục đích giải quyết là giải quyết vấn đề tương tự nhưng nhỏ hơn.

Vấn đề nhỏ hơn này cho tới một lúc nào đó sẽ đơn giản đến mức mà chương trình có thể tự giải quyết được mà không cần gọi lại nữa.

Điều kiện để viết một chương trình đệ qui: Ngoài việc chương trình phải có dạng đệ qui thì để viết được chương trình đệ qui thì: ngôn ngữ viết chương trình phải hỗ trợ đệ qui, có hỗ trợ hàm và thủ tục, nhờ đó có một thủ tục hoặc hàm có thể có lời gọi đến chính hàm đó và quan trọng hơn là tư duy người lập trình phải xem xét và nhận ra đó là đệ qui.

Thiết kế giải thuật đệ qui cho một số bài toán

1. Chương trình tính hàm n! 
   Nhận thấy: điểm dừng của giải thuật này là khi n=0. Khi đó, giá trị của hàm sẽ có thể tính ngày mà không cần phải đệ qui. Nếu điều kiện dừng không thỏa mãn, sẽ có lời gọi đệ qui hàm giai thừa với tham số là n-1, nhỏ hơn tham số ban đầu một đơn vị.
   Code :

   int giaithua(int n)
   {
   	if (n == 0)
   		return 1;
   	else
   	{
   		return giaithua(n - 1)*n;
   	}
   }

2. Chương trình hàm tìm ước chúng lớn nhất của 2 số nguyên dương a, b.
   Nhận xét: Điểm dừng của giải thuật là khi b=0. Khi đó ước chung lớn nhất( UCLN) của a và b chính là 0 vì 0 chia hết cho mọi số. Khi b khác 0 thì sẽ lời gọi đệ qui sẽ là UCLN(a, a%b). Sau mỗi lần gọi đệ qui, các tham số sẽ nhỏ đần di và sau 1 số hữu hạn lời gọi tham số nhỏ hơn sẽ bằng 0. Đó chính là điểm dừng của giải thuật.
   Code:

   int UCLN(int a,int  b)
   {
   	if (b == 0)
   		return a;
   	else
   	{
   		return UCLN(a, a%b);
   	}
   }

   Trên đây là khái niệm đơn giản về đệ qui và một số ví dụ về giải thuật của các bài toán có dạng đệ qui. Các ví dụ trên đây khá cơ bản, các bạn có thể tìm hiểu thêm một số bài toán đệ qui kinh điển như Tháp Hà Nội, bài toán 8 hậu,… Trong quá trình tìm hiểu nếu có vấn đề các bạn có thể để lại bình luận để được giúp đỡ. Hẹn gặp lại ở các bài viết sau ở chủ đề Cấu trúc dữ liệu và giải thuật. Chúc các bạn thành công!