Categories Thuật toán

Hiểu thêm về đệ quy thông qua một số ví dụ [serial về các thuật toán cơ bản trong lập trình]

Đệ quy trong lập trình là gì

Ở trong hai bài viết trước về sắp xếp trộn (merge sort)sắp xếp nhanh (quick sort), chúng ta đã thấy được sức mạnh của đệ quy (recursion), đặc biệt là với sắp xếp nhanh, khi hiệu suất của nó là vượt trội, điều rất quan trọng khi xử lý dữ liệu lớn.

Tuy nhiên đệ quy không quá dễ hiểu, và tôi hy vọng qua bài viết này chúng ta sẽ nhìn rõ hơn về nó.

Tổng quát, một bài toán được giải quyết bằng đệ quy nếu nó có hai đặc điểm sau:

  • Chúng ta chia nó được thành các bài toán nhỏ hơn, và phương pháp giải bài toán nhỏ hơn cũng giống hệt như phương pháp giải bài toán lớn.
  • Nó có một điểm dừng, để cho phép đệ quy kết thúc, nếu không quá trình truy hồi sẽ là vô tận. Điểm dừng này là một kết quả đã biết trước, và nhiều khi là một công thức rất đơn giản.

Chúng ta sẽ phải nhắc lại một ví dụ kinh điển về đệ quy, đó là tính giai thừa của một số tự nhiên n.

Chúng ta biết công thức của nó như sau:

  • Nếu n = 0, thì n! = 1
  • Nếu n > 0, thì n! = 1 * 2 * … * n

Như vậy bài toán lớn n! tính được thông qua bài toán nhỏ hơn là (n-1)!, cụ thể:

n! = n * (n-1)!

Và cũng vậy (n-1)! tính được thông qua (n-2)!

(n-1)! = (n-1) * (n-2)!

Đây chính là tính đệ quy.

Còn điểm dừng của đệ quy này, giúp cho quá trình truy hồi kết thúc chính là khi n = 0, và chúng ta biết giá trị của điểm dừng đó là 1.

Thể hiện trong một ngôn ngữ lập trình, ví dụ PHP, nó sẽ trông giống như dưới đây:

function factorial($n){
    if($n == 0){
        return 1;
    }
    else{
        return $n * factorial($n-1);
    }
}

echo factorial(6); // Output: 720

Như vậy đoạn mã trong lập trình cũng sẽ phản ánh tính chất của đệ quy, nó gồm hai phần:

  • Điểm dừng đệ quy, với giá trị biết trước:
if($n == 0){
    return 1;
}
  • Mã đệ quy:
return $n * factorial($n-1);

Tiếp theo chúng ta sẽ nói về dãy số Fibonacci, một ví dụ dễ hiểu khác về khả năng đệ quy.

Chúng ta biết rằng công thức tính của một số Fibonacci là như sau:

  • Nếu n = 0 hoặc n = 1 thì fib(n) = n. Đây chính là điểm dừng của đệ quy.
  • Nếu n > 1 thì fib(n) = fib(n-1) + fib(n-2). Đây là phần đệ quy, khi bài toán lớn được chia và hoàn toàn giải quyết được bằng các bài toán nhỏ hơn với cách thức tương tự.

Đoạn mã PHP để giải quyết bài toán này:

function fibonacci($n) {
    if ($n == 0 || $n == 1) {
        return $n;
    }
    return fibonacci($n - 1) + fibonacci($n - 2);
}

Lỗi stack overflow

Giới lập trình thường cảnh báo là phải hết sức thận trọng khi viết mã sử dụng thuật toán đệ quy đặc biệt khi xử lý dữ liệu lớn, phức tạp.

Sở dĩ như vậy vì quá trình đệ quy sử dụng nhiều bộ nhớ để làm đệm trong quá trình truy hồi, do vậy nếu không khéo, nó sẽ làm tràn bộ nhớ (stack overflow), cái vốn luôn hữu hạn với bất cứ hệ thống tính toán nào.

Và khi bị stack overflow, chương trình sẽ dừng hoặc bị treo (crash), và tất nhiên, chương trình sẽ không hoạt động như chúng ta mong muốn.

Back to Top