Đệ quy trong C: điều kiện dừng, giai thừa và độ sâu stack

Một hàm gọi chính nó

Không có gì ngăn một hàm C gọi chính nó. Tên của hàm nằm trong phạm vi ngay bên trong thân hàm, nên đoạn này hợp lệ:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* calls itself - but never stops! */
}

Nhưng nó cũng hỏng. Nó in mãi không dừng, xuống tới các số âm, cho đến khi chương trình crash. Thứ nó thiếu là một điều kiện dừng (base case): một điều kiện mà khi gặp, hàm trả về không gọi lại chính nó.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* base case: stop */
        printf("Liftoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* recursive case: a smaller problem */
}

int main(void) {
    countdown(5);
    return 0;
}

Mọi hàm đệ quy (recursion) đều có đúng hai phần này:

• Một điều kiện dừng: đầu vào nhỏ nhất, được trả lời trực tiếp, không gọi thêm lần nào.
• Một bước đệ quy: giải bài toán dựa trên một phiên bản nhỏ hơn hẳn của chính nó.

"Nhỏ hơn hẳn" là phần người ta hay làm sai. countdown(n - 1) tiến về 0 sau mỗi lời gọi. countdown(n) thì không, và countdown(n / 2) cũng không nếu n có thể mãi là 1. Mọi nhánh đều phải thu nhỏ bài toán, nếu không điều kiện dừng sẽ không bao giờ được chạm tới.

Giai thừa

Ví dụ đầu tiên kinh điển. n! là n × (n-1) × ... × 1, và 0! được định nghĩa bằng 1. Định nghĩa đó vốn đã đệ quy: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* base case: 0! and 1! are both 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* recursive case */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

Lần theo factorial(4) để xem đáp án được ghép lại thế nào. Các lời gọi đi xuống, còn các phép nhân diễn ra trên đường quay lên:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (base case)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Không có gì được nhân cho đến khi điều kiện dừng trả về. Mỗi lời gọi đang chờ đều nằm đó, giữ n của riêng nó, và đây là điều đáng ghi nhớ: những lời gọi đang chờ đó chiếm bộ nhớ.

Hãy để ý kiểu trả về. int bị tràn số ở khoảng 13!, âm thầm cho ra một số sai, vì C không kiểm tra. unsigned long long đưa bạn tới 20! và không xa hơn, vì 21! vượt quá 64 bit. Ở đây đệ quy không phải yếu tố giới hạn; kiểu dữ liệu mới là.

Điều kiện dừng dùng n <= 1 thay vì n == 1 là có chủ ý: factorial(0) phải bằng 1, và <= xử lý được trường hợp đó. Với n == 1, gọi factorial(0) sẽ đệ quy xuống -1, -2 và không bao giờ kết thúc: một minh họa tốt cho việc một điều kiện dừng "hiển nhiên đúng" vẫn có thể bỏ sót một đầu vào.

Fibonacci, và vì sao bản ngây thơ là một cái bẫy

Fibonacci là ví dụ kinh điển còn lại: mỗi số là tổng của hai số đứng trước, bắt đầu từ 0 và 1. Định nghĩa đệ quy gần như tự viết ra.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld calls)\n", n, result, calls);
    }
    return 0;
}

Hãy nhìn số lời gọi. fib(10) cần 177 lời gọi; fib(35) cần gần 30 triệu. Mỗi lần tăng thêm 5, khối lượng công việc nhân lên khoảng mười một lần.

Lý do hiện rõ trong cây lời gọi. fib(5) gọi fib(4) và fib(3); fib(4) lại gọi fib(3) thêm lần nữa; và mỗi lời gọi đó lại tính fib(2) từ đầu. Không có gì được ghi nhớ, nên cùng những bài toán con bị giải đi giải lại, và số lời gọi tăng xấp xỉ 1,6ⁿ. Tính fib(50) theo cách này sẽ chạy hàng ngày trời; fib(100) thì còn lâu hơn cả tuổi thọ vũ trụ.

Bản dùng vòng lặp giữ hai giá trị gần nhất và có độ phức tạp tuyến tính:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) trả về ngay lập tức. Bài học không phải là "đệ quy thì chậm", mà là đệ quy có các bài toán con chồng lấn sẽ chậm trừ khi bạn ghi nhớ đáp án. Lưu kết quả vào một mảng ngay khi tính (memoization) thì bản đệ quy cũng trở thành tuyến tính.

Call stack và stack overflow

Mỗi lời gọi hàm cần một chỗ để giữ tham số, biến cục bộ và địa chỉ để quay về. Chỗ lưu đó là một stack frame, được đẩy vào khi lời gọi bắt đầu và lấy ra khi nó trả về. Đệ quy xếp các frame chồng lên nhau: factorial(1000) có một nghìn frame cùng tồn tại một lúc, mỗi frame có n riêng.

Stack không lớn. Mức mặc định thường từ 1 đến 8 MB, nên vài chục nghìn frame là giới hạn thực tế, và ít hơn nhiều nếu mỗi frame chứa một mảng cục bộ lớn. Vượt quá là chương trình chết:

Segmentation fault (core dumped)

Đó là stack overflow, và có hai cách để gặp nó:

Đệ quy vô hạn: thiếu điều kiện dừng hoặc không bao giờ chạm tới nó. Đây là bug, và crash xảy ra ngay lập tức:

int bad(int n) {
    return bad(n - 1);      /* no base case - crashes in a fraction of a second */
}

Đúng nhưng quá sâu: đệ quy một lần cho mỗi phần tử trên một danh sách một triệu phần tử. Logic thì đúng; nhưng cách làm không vừa với stack. Hãy viết lại bằng vòng lặp, hoặc tổ chức lại để độ sâu là logarit (đệ quy trên từng nửa, như tìm kiếm nhị phân và merge sort, cho độ sâu khoảng 20 với một triệu phần tử).

Một số trình biên dịch có thể biến đệ quy đuôi (tail recursion), khi lời gọi đệ quy là việc cuối cùng hàm làm và sau đó không còn việc gì chờ, thành một vòng lặp dùng lại một frame duy nhất. countdown ở trên là đệ quy đuôi; factorial thì không, vì phép nhân vẫn phải diễn ra sau khi lời gọi trả về. Nhưng C không bắt buộc tối ưu hóa này, nên nó có thể xảy ra hoặc không tùy trình biên dịch và các cờ biên dịch. Đừng bao giờ viết code C chỉ chạy được nhờ trình tối ưu đã loại bỏ một lời gọi đuôi.

Khi đệ quy thật sự chiếm ưu thế

Mọi hàm đệ quy đều có thể viết lại thành vòng lặp, và với việc đếm đơn giản thì vòng lặp rõ ràng tốt hơn. Đệ quy phát huy giá trị khi chính dữ liệu có tính đệ quy, tức khi một cấu trúc chứa các bản sao nhỏ hơn của chính nó.

Tìm kiếm nhị phân là một ví dụ gọn gàng: tìm trong một nửa, rồi một nửa của nửa đó.

#include <stdio.h>

/* returns the index of target, or -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* base case: nothing left */
    }
    int mid = low + (high - low) / 2;       /* avoids overflow on big indices */

    if (a[mid] == target) {
        return mid;                         /* base case: found it */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> index %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Ở đây có hai điều kiện dừng, và điều đó là bình thường: một cho trường hợp tìm thấy, một cho trường hợp hết chỗ tìm. Độ sâu khoảng log₂(n), nên ngay cả một tỷ phần tử cũng chỉ cần ba mươi frame.

Những chỗ khác mà đệ quy là lựa chọn tự nhiên: duyệt cây hoặc danh sách liên kết, duyệt thư mục, phân tích các biểu thức lồng nhau, và các thuật toán sắp xếp chia để trị như quicksort và merge sort. Ở tất cả những chỗ đó, code đệ quy vừa ngắn hơn vừa rõ ràng hơn vòng lặp dùng stack tường minh thay thế nó.

Đệ quy hay vòng lặp?

Use a loop when       the problem is linear - counting, summing, scanning
Use recursion when    the data is nested - trees, nested structures, divide and conquer
Rewrite recursion     if the depth can grow with the input size without bound
Never use recursion   when subproblems overlap, unless you memoize

Hai lưu ý thực tế. Lời gọi đệ quy tốn hơn một lần lặp một chút, vì mỗi lần phải đẩy vào và lấy ra một frame, nên với các vòng lặp đơn giản chạy liên tục, bản lặp thắng cả về tốc độ lẫn bộ nhớ. Và việc gỡ lỗi cũng khác: stack trace từ đệ quy sâu là hàng trăm frame trông y hệt nhau, nên hãy in tham số ngay khi vào hàm (như bộ đếm calls ở trên) khi có gì đó không kết thúc.

Viết hàm đệ quy: danh sách kiểm tra

1. Tìm điều kiện dừng trước tiên. Đầu vào nhỏ nhất là gì, và đáp án của nó là gì? Nếu bạn không gọi tên được nó, bạn không thể viết hàm.
2. Giả định lời gọi đệ quy chạy đúng. Đừng lần theo nó trong đầu; hãy tin factorial(n - 1) trả về (n-1)! và viết một bước biến nó thành đáp án.
3. Kiểm tra mọi nhánh đều thu nhỏ bài toán. Mỗi lời gọi đệ quy phải tiến về điều kiện dừng với mọi đầu vào có thể, kể cả 0 và số âm.
4. Kiểm tra độ sâu. Với dữ liệu thật, đệ quy sẽ sâu khoảng bao nhiêu frame? Hàng nghìn thì ổn; hàng triệu thì không.
5. Kiểm tra sự chồng lấn. Nếu cùng một bài toán con được tính hai lần, bạn cần memoization hoặc một vòng lặp.