Toán tin vuotlen.com

Tổng quan đệ quy (Recursion)

Khái niệm về hàm đệ quy (Recursion)

Các lời giải đệ quy cho một bài toán có thể được viết gọn vào trong một hàm, và hàm đó được gọi là hàm đệ quy. Đặc điểm của một hàm đệ quy là luôn luôn có lời gọi lại tới chính nó (thực tế bài toán đệ quy cũng là đi giải lại chính bài toán đó nhưng với kích thước nhỏ hơn):

{Hàm_đệ_quy} ({Danh_sách_tham_số})
{
    {Gọi_lại_hàm_đệ_quy}({Danh_sách_tham_số});
}
Một cách dễ hiểu nhất, chúng ta có thể tưởng tượng hàm đệ quy giống như một vòng lặp. Nếu như vòng lặp sẽ lặp đi lặp lại khối lệnh của nó với một số lần hữu hạn hoặc vô hạn, thì hàm đệ quy cũng sẽ lặp đi lặp lại đoạn mã được viết bên trong nó một số lần hữu hạn hoặc vô hạn, tùy vào cách viết của chúng ta.

Các thành phần của một hàm đệ quy

Một hàm đệ quy luôn luôn bao gồm hai phần:

Ta lấy một ví dụ là hàm đệ quy tính n! như sau:

int factorial(int n)
{
    if (n == 0) // Phần neo.
        return 1;
    else // Phần gọi đệ quy.
        return factorial(n - 1) * n;
}

Ở bài toán này, phần neo định nghĩa trước lời giải cho trường hợp n=0 là 1, còn đối với các bài toán có n>1, ta sẽ dùng lời gọi đệ quy để đưa về giải bài toán có kích thước bằng n−1 rồi từ đó tính 𝑛!=(𝑛−1)!×𝑛 . Chẳng hạn, nếu dùng hàm này để tính 3!, giải thuật sẽ diễn ra như sau:

Việc giải bài toán factorial(3) sẽ diễn ra trong 6 bước từ việc phân rã factorial(3) xuống factorial(0) rồi lần lượt trả ngược kết quả các bài toán nhỏ lên các bài toán lớn hơn đã gọi nó, cho tới khi đạt được kết quả của bài toán ban đầu. Nguyên lí của việc này là do máy tính khi nhận thấy một bài toán chưa được giải ở lời gọi đệ quy, nó sẽ tạm thời lưu bài toán đó vào một ngăn xếp theo chiều từ trên xuống dưới, như vậy các bài toán chưa được giải sẽ xếp chồng lên nhau theo thứ tự bài toán lớn hơn ở dưới, bài toán nhỏ hơn ở trên. Việc giải các bài toán lại được thực hiện từ trên xuống dưới, như vậy bài toán ở bên dưới (là bài toán lớn hơn) sẽ thu nhận được kết quả của bài toán bên trên (là bài toán nhỏ hơn),...Tiếp tục thực hiện như vậy cho tới khi trong ngăn xếp chỉ còn lại một bài toán cuối cùng, đó chính là bài toán gốc.

Đây là một đặc điểm rất thú vị của đệ quy, có ứng dụng rất lớn trong việc thiết kế các giải thuật sau này như: Quay lui, nhánh cận,...

 

Có nên sử dụng đệ quy?

Mặc dù mang trong mình nhược điểm là thời gian thực hiện lớn, nhưng đệ quy không phải là không có ưu điểm. Nhờ vào việc cài đặt đơn giản, ngắn gọn nên giải thuật đệ quy được áp dụng trong nhiều bài toán mà nếu sử dụng lời giải lặp thì rất khó để lập trình, tiêu biểu như giải thuật sắp xếp nhanh (quick sort). Ở một số bài toán phức tạp, việc chuyển giải thuật đệ quy sang giải thuật không đệ quy là việc không đơn giản, cần có sự am hiểu về thuật toán và sự tinh tế nhất định, nên giải thuật đệ quy vẫn luôn luôn có chỗ đứng của nó.

Tuy nhiên, về tổng thể, ta vẫn nên cố gắng hạn chế sử dụng hàm đệ quy ở mức tối đa. Có rất nhiều phương pháp để khử cài đặt đệ quy, tiêu biểu là phương pháp quy hoạch động hoặc phương pháp đệ quy có nhớ mà chúng ta sẽ được học tới ở trong một vài chuyên đề nữa.