Recursion — method gọi chính nó

Method gọi method khác — chuyện thường. Nhưng method gọi chính nó thì sao? Nghe tròn tròn kỳ lạ, nhưng đệ quy (recursion) là cách tự nhiên diễn giải nhiều bài toán: giai thừa, Fibonacci, duyệt cây, tìm kiếm trong thư mục, parse biểu thức. Code gần như đọc giống công thức toán.

Cái bẫy: mỗi lần gọi lại là một stack frame mới. Quên điều kiện dừng → StackOverflowError. Bài này giải thích cơ chế, viết đệ quy an toàn, khi nào nên đổi sang iterative, và vì sao Java chưa tối ưu tail recursion như Scala/Kotlin.

1. Analogy — hỏi người phía trước

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. Ví dụ đầu tiên — giai thừa

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ế bên dưới — stack lớn lên

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>).

4. Đệ quy rẽ nhánh — Fibonacci

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);
}

5. Tail recursion — và vì sao Java không tối ưu

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 dùng đệ quy?

✅ 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. Đệ quy gián tiếp (mutual recursion)

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.

8. Pitfall tổng hợp

❌ 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. 📚 Deep Dive Oracle

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. Tóm tắt

• Đệ quy = method gọi chính nó với input nhỏ hơn, có base case để dừng.
• Mỗi call tạo 1 stack frame mới. Stack có giới hạn (~512KB–1MB mặc định), nên đệ quy sâu sẽ ném StackOverflowError.
• Fibonacci đệ quy naive là O(2^n) — memoize hoặc iterative để về O(n).
• Java không optimize tail call. Viết tail form không tiết kiệm stack.
• Dùng đệ quy khi depth nhỏ và bài toán tự nhiên đệ quy (cây, chia để trị).
• Dùng iterative khi depth lớn hoặc không dự đoán được.
• Mutual recursion hợp lệ nhưng cùng rule: depth nhỏ mới an toàn.
• -Xss tăng stack size chỉ delay problem, không giải quyết gốc.

11. Tự kiểm tra

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