Đệ quy & call stack

Bài 11 cho bạn hàm gọi hàm khác. C còn cho một nước đi táo bạo hơn: hàm tự gọi chính nó - gọi là đệ quy (recursion). Nghe vòng vo, nhưng có những bài toán mà định nghĩa của nó VỐN đã đệ quy. Giai thừa là ví dụ kinh điển: 4! = 4 × 3!, và 3! = 3 × 2!… cứ thế nhỏ dần về 1! = 1:

#include <stdio.h>

long giai_thua(int n) {
    if (n <= 1) return 1;          /* dieu kien dung (base case) */
    return n * giai_thua(n - 1);   /* buoc thu nho               */
}

int main(void) {
    printf("4! = %ld\n", giai_thua(4));
    return 0;
}

4! = 24

Mọi hàm đệ quy đúng đắn đều có đủ hai mảnh:

• ▸ĐIỀU KIỆN DỪNG (base case): trường hợp nhỏ tới mức trả lời được ngay, không cần gọi tiếp - ở đây là n <= 1.
• ▸BƯỚC THU NHỎ: lời gọi tiếp theo phải TIẾN VỀ điều kiện dừng - giai_thua(n - 1) nhỏ hơn giai_thua(n).
• ▸Mẹo an toàn: viết điều kiện dừng kiểu "lưới rộng" (n <= 1, không phải n == 1) - lỡ ai gọi giai_thua(0) vẫn không lọt lưới.

Mỗi lời gọi hàm, C tạo một khung (frame) chứa tham số và biến cục bộ của riêng lời gọi đó, đặt lên đỉnh một chồng gọi là call stack. Hàm trả về thì khung bị gỡ xuống. Bấm từng bước mà xem - chọn cả 4 hàm:

long giai_thua(int n) {
    if (n <= 1) return 1;          /* dieu kien dung */
    return n * giai_thua(n - 1);   /* buoc thu nho   */
}

Vị trí của câu lệnh so với lời gọi đệ quy quyết định thứ tự thực hiện. Hai hàm dưới đây chỉ khác nhau chỗ đặt printf - và in ra hai chiều ngược nhau:

#include <stdio.h>

void dem_nguoc(int n) {
    if (n == 0) { printf("Bum!\n"); return; }
    printf("%d\n", n);     /* IN truoc... */
    dem_nguoc(n - 1);      /* ...GOI sau  */
}

void dem_xuoi(int n) {
    if (n == 0) return;
    dem_xuoi(n - 1);       /* GOI truoc... */
    printf("%d\n", n);     /* ...IN sau    */
}

int main(void) {
    dem_nguoc(3);
    printf("---\n");
    dem_xuoi(3);
    return 0;
}

3
2
1
Bum!
---
1
2
3

• ▸In TRƯỚC khi gọi → làm việc trên đường "xuống dốc": 3, 2, 1.
• ▸In SAU khi gọi → mọi việc dồn về đường "lên dốc", lúc các khung lần lượt trả về: 1, 2, 3.
• ▸Xem lại hai preset này trong công cụ Bước 3 để thấy đúng khoảnh khắc mỗi số được in.

Stack hữu hạn. Quên điều kiện dừng là các khung chồng lên vô tận cho đến khi hết chỗ - stack overflow (tràn stack), chương trình sập:

long sau(long n) {
    return 1 + sau(n + 1);   /* QUEN dieu kien dung! */
}

int main(void) {
    return (int)sau(0);
}

Cái giá thứ hai kín đáo hơn: đệ quy đôi như fib tính lại cùng một giá trị nhiều lần - công cụ Bước 3 đếm được fib(4) tốn 9 lời gọi dù chỉ sâu 4 khung. Quy tắc chọn:

• ▸Bài toán tự lồng nhau (cây thư mục, biểu thức lồng biểu thức) → đệ quy mô tả tự nhiên nhất.
• ▸Chuỗi việc thẳng hàng (đếm, cộng dồn, duyệt mảng) → vòng lặp (Bài 10): không tốn khung, không lo tràn.
• ▸Đệ quy đôi kiểu fib chỉ hợp với n nhỏ - n lớn cần kỹ thuật lưu kết quả (khoá DSA) hoặc vòng lặp.