Recursion — Giải thuật đệ quy và cơ chế Call Stack

TL;DR: Đệ quy (recursion) là kỹ thuật giải quyết bài toán phức tạp bằng cách để phương thức gọi lại chính nó với không gian bài toán thu nhỏ dần, cho đến khi chạm tới trường hợp cơ sở (base case). Mỗi lượt gọi đệ quy tạo thêm một frame trên Call Stack của JVM, do đó cần kiểm soát chặt chẽ để tránh bẫy StackOverflowError.

Như đã tìm hiểu ở bài khai báo method và cơ chế Call Stack, một phương thức có thể gọi các phương thức khác và JVM sẽ chồng các stack frame lên nhau. Nhưng điều gì sẽ xảy ra khi một phương thức gọi lại chính nó? Kỹ thuật này được gọi là đệ quy (recursion) — một phương pháp tư duy mạnh mẽ giúp biểu diễn các bài toán chia để trị, duyệt cây và tìm kiếm một cách ngắn gọn, tự nhiên như công thức toán.

1. Analogy hỏi người phía trước minh họa đệ quy ra sao?

Bạn đứng ở hàng dài chờ mua vé. Muốn biết mình đứng thứ mấy, bạn không đi đếm cả hàng — bạn hỏi người ngay trước mặt: "Anh đứng thứ mấy?". Người đó không biết → hỏi tiếp người trước. Truyền câu hỏi đến người đầu hàng (biết mình thứ 1), rồi đáp án lan ngược về: 1, 2, 3, 4... đến bạn.

2. Hai thành phần bắt buộc của giải thuật đệ quy là gì?

Toán: n! = n × (n-1)!, với 0! = 1.

Dịch thẳng ra Java:

public static long factorial(int n) {
    if (n == 0) return 1;              // base case
    return n * factorial(n - 1);        // recursive case
}

factorial(5);   // 120

Luồng chạy:

Mỗi call tạo 1 stack frame mới. Frame đợi kết quả của frame con, nhân xong mới return.

2.1 Hai phần bắt buộc của mọi đệ quy

1. Base case — điều kiện dừng (ở đây: n == 0). Thiếu base case, đệ quy chạy vô hạn và kết thúc bằng StackOverflowError.
2. Recursive case — gọi lại với input tiệm cận base case (ở đây: n - 1). Nếu input không tiến gần base case (vd factorial(n) gọi lại chính factorial(n)), đệ quy cũng vô hạn.

// BUG — khong tiem can base case
public static int bad(int n) {
    if (n == 0) return 0;
    return 1 + bad(n);   // n khong giam -> infinite recursion
}

3. Cơ chế Call Stack mở rộng và bẫy StackOverflowError hoạt động như thế nào?

Call stack của JVM trên HotSpot 64-bit mặc định khoảng 1 MB mỗi thread (tuỳ JDK, OS — thường trong khoảng 512 KB–1 MB). Mỗi frame chiếm ~50–200 bytes cho method đơn giản. Giới hạn thực tế ~5.000–50.000 frame cho đệ quy chuẩn.

Chạy factorial(100000) ném StackOverflowError rất nhanh. Nhưng vòng lặp for (int i = 0; i < 100000; i++) không vấn đề — vì chỉ 1 frame, không phụ thuộc số vòng.

// Iterative — 1 frame
public static long factorialIter(int n) {
    long r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}

3.1 Đổi stack size với -Xss

JVM flag -Xss2m tăng stack lên 2MB cho mỗi thread. Không phải giải pháp — chỉ delay StackOverflowError thêm vài ngàn frame. Nếu thật sự cần đệ quy sâu, đổi sang iterative hoặc dùng explicit stack (chuyển đệ quy thành loop với Deque<State>).

Thử ngẫmsếp đề xuất thêm -Xss4m vào JVM flags để hết lỗi StackOverflowError trên production. Cách này giải quyết triệt để hay chỉ dời cái ngưỡng đi xa hơn?

4. Tại sao đệ quy Fibonacci rẽ nhánh lại bùng nổ độ phức tạp O(2^n)?

public static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Bài đầy đủ base case (n == 0 → 0, n == 1 → 1) và recursive case tách đôi.

Nhưng cái bẫy perf: mỗi fib(n) gọi fib(n-1) và fib(n-2) → fib(n-2) lại gọi fib(n-3) và fib(n-4)... Cây gọi phình exponentially. fib(40) đã chạy chậm, fib(50) mất phút.

fib(3) tính 2 lần, fib(2) tính 3 lần. Độ phức tạp O(2^n).

Fix: memoization (cache) hoặc iterative:

// Iterative O(n)
public static int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

// Memoization O(n), giu duoc dang de quy
public static int fibMemo(int n, int[] cache) {
    if (n <= 1) return n;
    if (cache[n] != 0) return cache[n];
    return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}

Thử ngẫmfib(3) bị tính 2 lần, fib(2) bị tính 3 lần trong cây gọi ở trên. Với fib(50), số lần một bài toán con nhỏ nhất bị tính lại còn ở mức chấp nhận được không?

5. Tail Recursion trong Java có được tối ưu hóa ở tầng bytecode không?

Tail recursion = recursive call là phép tính cuối cùng trước khi return (không có thao tác nào sau đó). Ngôn ngữ có optimizer TCO (tail call optimization) có thể biến tail call thành loop → không tốn stack frame.

// Tail recursion — call la buoc cuoi
public static long factorialTail(int n, long acc) {
    if (n == 0) return acc;
    return factorialTail(n - 1, acc * n);   // return la recursive call
}

// Khong tail — sau call con phep nhan n *
public static long factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);  // phai nhan sau khi call return
}

Scala, Kotlin, Clojure, Haskell, Scheme... tối ưu tail recursion. Java thì không — JVM giữ chiến lược "mỗi call 1 frame" kể cả với tail call. Lý do lịch sử: stack trace và security model dựa vào cả chain frame, TCO làm mất thông tin debugging.

Hệ quả: trong Java, viết tail form không tiết kiệm stack. Nếu cần perf, đổi iterative.

6. Khi nào nên dùng đệ quy và khi nào nên chuyển sang vòng lặp?

✅ Dùng khi:

• Bài toán tự nhiên định nghĩa đệ quy: duyệt cây (filesystem, DOM, AST), chia để trị (merge sort, quick sort, binary search), backtracking (tìm đường, sudoku).
• Độ sâu đệ quy nhỏ và đoán được — thường depth proportional log(n) cho cây cân bằng.
• Code đệ quy đọc rõ hơn hẳn iterative.

❌ Tránh khi:

• Độ sâu không bị chặn (vd depth = n cho list).
• Bài toán có công thức iterative đơn giản (tổng dãy, count, search tuyến tính).
• Trong hot path và đệ quy có overhead (vd tạo object trong mỗi frame).

Ví dụ — duyệt thư mục

public static void listFiles(File dir, int depth) {
    if (!dir.isDirectory()) return;
    for (File f : dir.listFiles()) {
        System.out.println("  ".repeat(depth) + f.getName());
        if (f.isDirectory()) {
            listFiles(f, depth + 1);   // de quy vao sub-dir
        }
    }
}

Cây thư mục thực tế hiếm khi sâu quá 20 level, nên đệ quy ở đây an toàn và dễ đọc. Viết iterative phải tự quản Deque<File> — dài gấp đôi, khó đọc.

7. Kỹ thuật đệ quy tương hỗ (mutual recursion) hoạt động ra sao?

A gọi B, B gọi A — vẫn hợp lệ:

public static boolean isEven(int n) {
    if (n == 0) return true;
    return isOdd(n - 1);
}

public static boolean isOdd(int n) {
    if (n == 0) return false;
    return isEven(n - 1);
}

Cảnh báo: không có TCO → mỗi gọi chiếm frame. isEven(1000000) stack overflow. Đây là ví dụ minh hoạ hơn là pattern production.

Thử ngẫmisEven/isOdd đệ quy qua lại minh hoạ ý tưởng nhưng không dùng được ở production. Kiểm tra chẵn lẻ cho 1 triệu số trong một vòng lặp — cách viết nào ở bài này còn đứng vững?

8. Các bẫy lỗi thường gặp nhất khi lập trình đệ quy là gì?

❌ Nhầm 1: Quên base case.

int count(List<?> xs) { return 1 + count(xs); }   // infinite

✅ Luôn có if (base condition) return ...; ở đầu method.

❌ Nhầm 2: Recursive case không tiệm cận base.

int f(int n) { if (n == 0) return 0; return f(n + 1); }   // n tang, khong bao gio 0

✅ Đảm bảo mỗi call argument tiến gần base case (giảm, chia đôi, v.v.).

❌ Nhầm 3: Exponential blowup do trùng subproblem.

fib(n) = fib(n-1) + fib(n-2);   // O(2^n)

✅ Memoize với int[] / Map, hoặc đổi iterative.

❌ Nhầm 4: Tưởng Java optimize tail call.

long factTail(int n, long acc) { ... }   // van ton frame

✅ Với input lớn, phải iterative.

❌ Nhầm 5: Side effect trong đệ quy gây kết quả khó đoán.

void visit(Node n) {
    sharedList.add(n.value);   // thu tu add phu thuoc DFS order
    for (Node c : n.children) visit(c);
}

✅ Nếu cần thứ tự cụ thể, return collection thay vì side-effect vào biến ngoài.

9. Tài liệu Deep Dive Oracle quy định gì về JVM Stacks?

Liên kết khoá học khác

• Khoá Thuật toán — bài 02.2 Recursion & Call Stack — call stack frame, tail call, StackOverflowError dưới góc độ memory và JVM internals.
• Khoá Thuật toán — bài 03.3 Amortized Analysis — amortized analysis cho recursive algorithm với memoization để đánh giá chi phí thực tế.

10. Điểm cốt lõi cần nhớ về giải thuật đệ quy là gì?

• Đệ quy yêu cầu hai phần bắt buộc: trường hợp cơ sở (base case) và bước đệ quy tiệm cận (recursive case).
• Mỗi lượt gọi đệ quy tiêu tốn một stack frame; không kiểm soát độ sâu sẽ dẫn tới lỗi tràn bộ nhớ StackOverflowError.
• Java và JVM hiện tại không tự động tối ưu đệ quy đuôi (TCO); vì vậy các bài toán có chiều sâu lớn cần chuyển sang vòng lặp.
• Với các bài toán rẽ nhánh như Fibonacci, cần áp dụng kỹ thuật lưu bộ nhớ đệm (memoization) để tránh độ phức tạp hàm mũ O(2^n).

11. Tự kiểm tra kiến thức về đệ quy như thế nào?

Bài tiếp theo: Scope, shadowing, và lifetime của biến