Thuật Toán Đệ Quy & Cây Gọi Hàm

1. Bản chất vấn đề & trực giác thuật toán (the core problem & intuition)

Trong các bài toán lập trình cơ bản, chúng ta quen thuộc với tư duy lặp tuần tự (for, while): xử lý từng phần tử lần lượt từ đầu đến cuối. Tuy nhiên, trong thế giới cấu trúc dữ liệu và giải thuật nâng cao, rất nhiều bài toán mang bản chất tự đồng dạng (Self-Similarity): Để giải một bài toán quy mô $N$, ta có thể giải bài toán tương tự nhưng ở quy mô nhỏ hơn $N-1$ hoặc $N/2$, sau đó kết hợp kết quả lại.

Khái niệm đệ quy (recursion):

Đệ quy là kỹ thuật lập trình trong đó một hàm tự gọi lại chính nó (trực tiếp hoặc gián tiếp) với các tham số đại diện cho bài toán con nhỏ hơn.

Mỗi hàm đệ quy chuẩn mực bắt buộc phải có đủ 2 thành phần cốt lõi:

1. Điểm Dừng (Base Case / Anchor): Trường hợp bài toán đơn giản nhất đã biết trước đáp án mà không cần gọi tiếp đệ quy. Điểm dừng có nhiệm vụ ngắt chuỗi lời gọi vô tận.
2. Bước Đệ Quy (Recursive Case / Reduction Step): Thu nhỏ quy mô bài toán bằng cách gọi lại chính hàm đó với tham số tiến dần về phía Base Case.

2. Mô phỏng từng bước hoạt động của Call Stack (visual step-by-step simulation)

Để hiểu đệ quy, lập trình viên không được nhìn code như một vòng lặp phẳng, mà bắt buộc phải hình dung hoạt động của Ngăn xếp cuộc gọi (Call Stack) qua hai pha riêng biệt:

• Pha Xuôi (Winding Phase): Các hàm được gọi liên tiếp và đẩy đè lên nhau trên đỉnh ngăn xếp (Stack Frame Push).
• Pha Ngược (Unwinding Phase): Khi chạm Base Case, các hàm lần lượt tính xong kết quả, trả về (Return) và được giải phóng khỏi ngăn xếp (Stack Frame Pop).

Ví dụ 1: Mô phỏng hàm tính giai thừa fact(4)

long long fact(int n) {
    if (n <= 1) return 1;          // Base Case
    return n * fact(n - 1);        // Recursive Step
}

Bảng mô phỏng từng bước ngăn xếp (Call Stack trace):

| 3 | Gọi fact(2) | [fact(2)] -> [fact(3)] -> [fact(4)] | Đang đợi fact(1) |

| 4 | Gọi fact(1) | [fact(1)] -> [fact(2)] -> [fact(3)] -> [fact(4)] | Chạm Base Case: Trả về 1 |

| 5 | Unwind fact(2) | [fact(2)] -> [fact(3)] -> [fact(4)] | fact(2) = 2 * 1 = 2 |

| 6 | Unwind fact(3) | [fact(3)] -> [fact(4)] | fact(3) = 3 * 2 = 6 |

| 7 | Unwind fact(4) | [fact(4)] | fact(4) = 4 * 6 = 24 | | 8 | Kết thúc | Stack rỗng | Đáp án: 24 |

Ví dụ 2: So sánh vị trí lệnh in (winding vs unwinding)

Quan sát sự khác biệt khi đặt lệnh cout trước vs sau lời gọi đệ quy:

// Dạng A: In trong Winding Phase (Trước khi gọi đệ quy)
void printBackward(int n) {
    if (n == 0) return;
    cout << n << " ";           // In ngay khi vào hàm
    printBackward(n - 1);
}
// Gọi printBackward(3) -> Output: 3 2 1

// Dạng B: In trong Unwinding Phase (Sau khi gọi đệ quy)
void printForward(int n) {
    if (n == 0) return;
    printForward(n - 1);
    cout << n << " ";           // In khi hàm quay lui trở về
}
// Gọi printForward(3) -> Output: 1 2 3

Quy luật vàng (winding vs unwinding):

• Các thao tác viết trước lời gọi đệ quy sẽ thực thi theo thứ tự từ ngoài vào trong ($N \to 1$).
• Các thao tác viết sau lời gọi đệ quy sẽ thực thi theo thứ tự từ trong ra ngoài ($1 \to N$), khi stack bắt đầu rút lui (Unwind).

3. Lý thuyết cốt lõi & bất biến thuật toán (core invariants)

3.1. Khái niệm stack frame & phân tích an toàn bộ nhớ (stack safety)

• Khi một hàm được gọi, mô hình thực thi của chương trình tạo ra một Stack Frame (Activation Record) lưu trữ trạng thái thực thi riêng biệt: tham số truyền vào, các biến cục bộ và địa chỉ trả về (Return Address) theo quy ước gọi (Calling Convention / ABI).
• Vùng nhớ ngăn xếp (Stack Memory) có kích thước hữu hạn và giới hạn cụ thể phụ thuộc vào môi trường thực thi, hệ điều hành và cấu hình của từng Online Judge.
• Độ sâu đệ quy (Recursion Depth) vs Kích thước Stack Frame:
• Để đánh giá an toàn bộ nhớ của hàm đệ quy, ta phải xem xét đồng thời Độ sâu đệ quy tối đa (Maximum Depth) và Dung lượng bộ nhớ tiêu thụ trên mỗi Frame. Nếu mỗi frame chứa mảng cục bộ lớn hoặc đệ quy vượt quá giới hạn bộ nhớ stack, chương trình sẽ gặp lỗi tràn ngăn xếp (Stack Overflow / Segmentation Fault).

Lưu ý kỹ thuật về tail recursion trong C++:

Trong lý thuyết ngôn ngữ, Đệ quy đuôi (Tail Recursion) là hàm đệ quy mà lời gọi hàm là câu lệnh cuối cùng. Tuy nhiên, chuẩn ngôn ngữ C++ không bắt buộc trình biên dịch phải tối ưu hóa đệ quy đuôi (Tail-Call Optimization - TCO) trong mọi cờ biên dịch thi đấu. Do đó, học sinh không được chủ quan giả định đệ quy đuôi sẽ luôn tự biến thành vòng lặp $\mathcal{O}(1)$ bộ nhớ. Luôn phân tích độ sâu stack cẩn trọng!

3.2. Hệ thống phân loại thuật ngữ đệ quy (recursion taxonomy)

1. Đệ quy Tuyến tính (Linear Recursion - 1 nhánh gọi / Frame): * Trong mỗi Stack Frame chỉ thực hiện đúng 1 lời gọi đệ quy con. Cây gọi hàm là một đường thẳng đơn tuyến. * Ví dụ: * Giai thừa $N!$: Độ sâu $N$, thời gian $\Theta(N)$, Stack Space $\Theta(N)$. * Thuật toán Euclid $\gcd(A, B)$: Độ sâu $\Theta(\log(\min(A, B)))$, thời gian $\Theta(\log(\min(A, B)))$. Lũy thừa nhị phân powerRec(A, B/2) (khi lưu biến tạm half): Độ sâu $\Theta(\log B)$, thời gian $\Theta(\log B)$. Lưu ý:* Mặc dù quy mô bài toán giảm theo cấp số nhân ($B \to B/2$), cấu trúc cây gọi hàm vẫn là đường thẳng 1 nhánh đơn tuyến.

2. Đệ quy Phân nhánh (Branching / Tree Recursion - $\ge 2$ nhánh gọi / Frame): * Trong mỗi Stack Frame xuất hiện từ 2 lời gọi đệ quy con trở lên, làm bùng nổ không gian trạng thái tạo thành cây nhị phân hoặc cây đa phân. * Ví dụ: * Tháp Hà Nội: $T(N) = 2T(N-1) + 1 \implies \Theta(2^N)$ bước, Độ sâu $N$. * Cây chia đôi tìm Min/Max: $T(N) = 2T(N/2) + \mathcal{O}(1) \implies \Theta(N)$ thao tác, Độ sâu $\Theta(\log N)$. * Fibonacci đệ quy thuần túy $F(N) = F(N-1) + F(N-2)$.

3.3. Độ phức tạp toán học của fibonacci đệ quy & cầu nối sang quy hoạch động

Xét cây gọi hàm khi tính $F(5)$ bằng đệ quy phân nhánh:

• Phân tích độ phức tạp tiệm cận chính xác: Số lời gọi hàm thỏa mãn hệ thức truy hồi $T(N) = T(N-1) + T(N-2) + 1$. Bằng phương trình đặc trưng $r^2 - r - 1 = 0$, ta chứng minh được số phép tính thực tế tăng theo cấp số nhân chính xác: $$\Theta(\varphi^N) \quad \text{với} \quad \varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618 \text{ (Tỉ lệ vàng)}$$ Chặn trên $O(2^N)$ là một cận trên lỏng (Upper Bound).

• Hiện tượng Overlapping Subproblems: Để tính $F(5)$, hàm $F(3)$ bị tính lại 2 lần, $F(2)$ bị tính lại 3 lần. Với $N = 40$, số lượng lời gọi đã lên tới hàng trăm triệu theo mô hình Fibonacci ($\Theta(\varphi^N)$), minh họa rõ hiện tượng bùng nổ thời gian.

• Bài học sư phạm: Đệ quy thuần túy rất đẹp nhưng sẽ bị tê liệt khi không gian trạng thái có các bài toán con trùng lặp. Việc lưu lại kết quả đã tính vào bảng nhớ (Memoization) sẽ được học bài bản ở Module 05: Quy hoạch động (Dynamic Programming).

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Thiếu Base Case hoặc Base Case không bao giờ chạm tới (Infinite Recursion): * Viết if (n == 0) nhưng tham số truyền vào là số âm $\implies$ Gọi đệ quy vô tận cho tới khi sập ngăn xếp. * Cách phòng chống: Luôn chặn cận bằng dấu <= (ví dụ if (n <= 1) return 1;).

2. Khai báo mảng lớn cục bộ bên trong hàm đệ quy: * Viết int temp[100000]; trong hàm đệ quy sẽ khiến mỗi Stack Frame tốn hàng trăm KB bộ nhớ $\implies$ Tràn stack chỉ sau vài chục lời gọi. * Cách phòng chống: Dùng biến toàn cục hoặc truyền tham chiếu const vector<int> &a.

3. Bẫy Gọi Lặp Lại Đệ Quy (Recursive Call Duplication): * Trong bài lũy thừa nhị phân, nếu viết return power(a, b/2) * power(a, b/2); thì từ đệ quy tuyến tính $\mathcal{O}(\log B)$ sẽ bị nổ thành cây đệ quy phân nhánh $\Theta(B)$ thao tác. * Quy tắc vàng: Không có Memoization, hai lời gọi hàm giống nhau là hai lần tính toán hoàn toàn độc lập. Tính 1 lần vào biến tạm: long long half = power(a, b/2, m); return (half * half) % m;.

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

# include <bits/stdc++.h>
using namespace std;

// 1. In dãy số 1..N và N..1 chuẩn Winding / Unwinding
void printForward(int n) {
    if (n <= 0) return;
    printForward(n - 1);
    cout << n << " ";
}

void printBackward(int n) {
    if (n <= 0) return;
    cout << n << " ";
    printBackward(n - 1);
}

// 2. Lũy thừa nhị phân đệ quy O(log B) an toàn với M <= 10^9
long long powerRec(long long a, long long b, long long m) {
    if (b == 0) return 1 % m;
    long long half = powerRec(a, b / 2, m);
    long long res = (1LL * (half % m) * (half % m)) % m;
    if (b % 2 == 1) res = (1LL * res * (a % m)) % m;
    return res;
}

// 3. Tháp Hà Nội chuẩn Theta(2^N)
void solveHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 0) return;
    solveHanoi(n - 1, from_rod, aux_rod, to_rod);
    cout << from_rod << " -> " << to_rod << "\n";

    solveHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 4;
    cout << "Day so 1..N: ";
    printForward(n);
    cout << "\n";

    cout << "Day so N..1: ";
    printBackward(n);
    cout << "\n";

    cout << "2^10 mod 1000 = " << powerRec(2, 10, 1000) << "\n";
    return 0;
}