Recursion & call stack — Khi đệ quy phá vỡ JVM

Bạn viết hàm factorial(n) đệ quy — gọn, đúng, trông như toán học. Test với n = 10, n = 100 đều ổn. Rồi một ngày cần xử lý input từ API bên ngoài, n = 20000, và JVM ném ngay:

Exception in thread "main" java.lang.StackOverflowError

CPython cũng không khá hơn: cùng input đó sẽ gặp RecursionError: maximum recursion depth exceeded vì giới hạn mặc định 1.000 frame. JVM mặc định -Xss khoảng 512KB đến 1MB tùy platform — đủ cho khoảng 10.000 đến 20.000 frame tùy kích thước method. factorial(20000) vượt xa ngưỡng đó.

Bài này giải thích recursion thực sự chạy thế nào trên JVM, vì sao đệ quy đẹp lý thuyết nhưng nguy hiểm production, và khi nào nên chuyển sang iteration.

1. Analogy — Chồng đĩa ghi nhớ tạm

Hình dung mỗi lần gọi hàm, bạn lấy một tờ giấy, ghi xuống "mình đang tính gì, số nào đã biết, sau khi xong thì quay về đâu", rồi đặt tờ đó lên một chồng giấy trên bàn. Khi hàm trả về, bạn lấy tờ trên cùng ra, đọc lại, và tiếp tục làm việc còn dở.

Mỗi cuộc gọi đệ quy là thêm một tờ. Khi gọi 20.000 lần liên tiếp trước khi có tờ nào được lấy ra, chồng giấy đổ — đó là StackOverflowError.

2. Stack frame là gì — cơ chế JVM

Mỗi khi một method được gọi, JVM cấp phát một stack frame trên thread stack. Frame đó chứa:

• Local variable array: các biến cục bộ và tham số của method.
• Operand stack: vùng tính toán trung gian (intermediate values khi evaluate expression).
• Return address: địa chỉ bytecode để JVM biết nhảy về đâu khi method trả về.
• Frame pointer: con trỏ liên kết frame hiện tại với frame của caller.

Kích thước mỗi frame phụ thuộc số local variable — method đơn giản có thể chỉ 32–64 byte, method nhiều biến có thể 128 byte hoặc hơn. JVM cấp cho mỗi thread một vùng stack riêng, kích thước mặc định từ 512KB đến 1MB tùy platform và JVM implementation (HotSpot trên Linux x64 mặc định 512KB). Công thức đơn giản: khi depth × frame_size vượt -Xss, JVM ném StackOverflowError.

// Recursive factorial — each call pushes one new frame onto the thread stack.
// Frame for factorial(n) holds: parameter n, return address back to caller.
public long factorial(int n) {
    if (n <= 1) return 1;           // base case: return pops this frame
    return n * factorial(n - 1);    // recursive call: push new frame before compute
    // NOTE: n * (...) means this frame must stay alive until factorial(n-1) returns.
    // That is why TCO is not possible here — result is used AFTER the recursive call.
}

Với factorial(5), call stack lúc sâu nhất trông như sau:

[factorial(1)]   <-- top of stack (most recent call)
[factorial(2)]
[factorial(3)]
[factorial(4)]
[factorial(5)]   <-- bottom (first call)
[main]

JVM unwind từ trên xuống: factorial(1) trả về 1, frame bị pop; factorial(2) nhận 1, tính 2 * 1 = 2, pop; và cứ thế đến factorial(5).

3. Stack growth diagram — fib(4)

Hàm Fibonacci đệ quy tạo ra cây gọi phức tạp hơn, vì mỗi call sinh ra hai nhánh con:

fib(4)
├── fib(3)
│   ├── fib(2)
│   │   ├── fib(1)  --> 1
│   │   └── fib(0)  --> 0
│   └── fib(1)      --> 1
└── fib(2)
    ├── fib(1)      --> 1
    └── fib(0)      --> 0

Độ sâu stack tối đa bằng chiều cao cây — với fib(n) là n frame. Nhưng số lần gọi tổng cộng là O(2^n) — đây là lý do fib(50) thực tế không thể chạy bằng đệ quy thuần túy.

4. Tail recursion và vì sao JVM không có TCO

Tail call là khi lời gọi đệ quy là thao tác cuối cùng trong method — method không cần làm gì thêm với kết quả trả về. Ví dụ:

// Tail-recursive factorial with accumulator.
// The recursive call is the LAST operation — nothing left to compute after it returns.
// A TCO compiler could reuse the current frame instead of pushing a new one.
public long factorialTail(int n, long acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc); // tail position: result used directly
}

Trong version này, factorialTail(n - 1, n * acc) là lệnh cuối — method không cần giữ lại bất kỳ gì từ frame hiện tại sau khi call này trả về. Về lý thuyết, compiler có thể reuse frame hiện tại thay vì push frame mới — gọi là Tail-Call Optimization (TCO). Nếu có TCO, recursion sâu tùy ý mà không cần thêm stack space.

JVM không thực hiện TCO, vì ba lý do cụ thể:

1. Stack trace integrity cho debugging: StackWalker API (Java 9+, JEP 259), debuggers, profilers, và APM agents (Datadog, New Relic) đều phụ thuộc vào frame đầy đủ. Nếu TCO xóa frame, stack traces trong observability tools bị hỏng — bạn mất hoàn toàn thông tin "hàm được gọi từ đâu".

2. JVM bytecode verifier: Bytecode verification model của JVM giả định mỗi method invocation có frame riêng. TCO đòi hỏi thay đổi sâu ở cấp bytecode spec, không chỉ JIT optimization.

3. JEP còn bỏ ngỏ: JEP 270 (Reserved Stack Areas, Java 9), JEP 444 (Virtual Threads, Java 21) đều liên quan đến stack management nhưng không giải quyết TCO. Tính đến Java 21, không có JEP nào được merge để thêm TCO vào JVM. Scala và Kotlin giải quyết bằng cách rewrite ở compile time: annotation @tailrec (Scala) và tailrec modifier (Kotlin) khiến compiler biến tail recursion thành loop trong bytecode trước khi JVM nhìn thấy.

// Java equivalent of what Kotlin/Scala @tailrec does at compile time:
// Manual rewrite of factorialTail() into a loop.
public long factorialIterative(int n) {
    long acc = 1;
    while (n > 1) {
        acc *= n;
        n--;
    }
    return acc;
}

Java dev phải tự tay làm bước này.

5. Ba pattern chuyển đổi đệ quy sang iteration

5.1 Tail recursion — accumulator + while loop

Bất kỳ tail-recursive function nào cũng có thể cơ học thành while loop:

// Before: tail-recursive, fails with StackOverflow at ~10k-20k depth on JVM
public long factorialTail(int n, long acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);
}

// After: iterative with accumulator, unlimited depth
public long factorialIter(int n) {
    long acc = 1;
    while (n > 1) { acc *= n--; }
    return acc;
}

5.2 Tree recursion — DP table hoặc rolling variables

Fibonacci: thay vì cây gọi O(2^n), dùng bảng kết quả đã tính:

// O(2^n) naive recursion — do NOT use for n > 40
public long fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// O(n) time, O(1) space — rolling two variables
public long fibFast(int n) {
    if (n <= 1) return n;
    long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

5.3 General recursion — explicit Deque thay JVM stack

Khi recursion không thuộc dạng tail hay tree đơn giản (ví dụ duyệt cây DOM, parse JSON lồng sâu), dùng Deque làm stack tường minh. Heap của JVM lớn hơn nhiều so với thread stack (heap thường vài GB, stack chỉ 512KB–1MB) — nên OOM trên heap khó xảy ra hơn nhiều so với StackOverflowError.

// Iterative DFS using explicit stack on heap — avoids StackOverflowError
// on deeply nested tree structures (e.g., 50k levels from untrusted input).
public void dfsIterative(TreeNode root) {
    if (root == null) return;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        process(node);                          // visit node
        if (node.right != null) stack.push(node.right); // push right first
        if (node.left  != null) stack.push(node.left);  // left processed first
    }
}

6. Pitfall tổng hợp

Pitfall 1: Quên base case — StackOverflow ngay lập tức.

// Missing base case — infinite recursion, immediate StackOverflowError
public int countDown(int n) {
    return countDown(n - 1); // forgot: if (n == 0) return 0;
}

// Fixed: explicit base case terminates recursion
public int countDown(int n) {
    if (n <= 0) return 0;     // base case
    return countDown(n - 1);
}

Đây là lỗi phổ biến nhất và dễ nhất để debug: stack trace sẽ hiển thị cùng một method lặp lại hàng nghìn dòng.

Pitfall 2: Depth phụ thuộc input từ bên ngoài — cửa cho DoS.

Method flattenJson(node) đệ quy hoạt động tốt với JSON thông thường sâu vài chục cấp. Nhưng attacker có thể gửi JSON lồng 50.000 cấp — mỗi cấp push một frame, JVM crash trong mili giây. Jackson mặc định giới hạn MAX_DEPTH = 1000 chính xác để ngăn điều này.

// Guard recursion depth when input comes from external sources
public void flattenJson(JsonNode node, int depth, Map<String, Object> result) {
    if (depth > 100) {                     // explicit depth limit
        throw new IllegalArgumentException("JSON nesting exceeds limit: " + depth);
    }
    if (node.isObject()) {
        node.fields().forEachRemaining(entry ->
            flattenJson(entry.getValue(), depth + 1, result)
        );
    } else {
        result.put("leaf_" + depth, node.asText());
    }
}

Pitfall 3: Tăng -Xss trông như giải pháp nhưng có giá.

Tăng -Xss từ 512KB lên 8MB giải quyết StackOverflowError tạm thời, nhưng:

• Mỗi thread reserve toàn bộ Xss stack (thực tế là virtual memory, nhưng vẫn ảnh hưởng đến memory map).
• Server với 1.000 thread concurrent: 1.000 × 8MB = 8GB reserved stack space — trong khi 1.000 × 512KB chỉ 500MB.
• Hậu quả: ít thread hơn có thể chạy đồng thời, hoặc cần nâng RAM để bù.

-Xss là parameter cần cân nhắc cẩn thận, không phải knob để vặn thoải mái.

7. Ứng dụng thực tế

JSON/XML parser và depth limit: Jackson 2.15+ giới hạn nesting depth qua StreamReadConstraints (mặc định 500 cấp). Cấu hình tường minh:

JsonMapper mapper = JsonMapper.builder()
    .streamReadConstraints(StreamReadConstraints.builder().maxNestingDepth(100).build())
    .build();

Nếu bạn tự viết recursive parser, hãy thêm depth counter và ném IllegalArgumentException khi vượt ngưỡng — trước khi JVM làm điều đó bằng StackOverflowError mà không cho bạn cơ hội handle.

Thread với custom stack size: Thread constructor có overload Thread(ThreadGroup, Runnable, String, long stackSize) — tham số cuối đặt stack size tính bằng byte cho thread đó. Hữu ích khi bạn biết một thread cụ thể cần xử lý đệ quy sâu, thay vì tăng global -Xss cho toàn JVM.

JEP 444 Virtual Threads (Java 21): Virtual thread lưu stack trên heap thay vì native thread stack. Khi virtual thread block, JVM serialize frame xuống heap object ("continuation") và giải phóng native thread. Điều này có nghĩa virtual thread stack có thể grow động trên heap — ít áp lực hơn so với platform thread với fixed -Xss. Tuy nhiên, StackOverflowError vẫn có thể xảy ra khi recursion quá sâu, chỉ là ngưỡng cao hơn đáng kể.

JEP 270 Reserved Stack Areas (Java 9+): JVM dành riêng một vùng nhỏ ở cuối stack cho critical section code (đánh dấu bằng @ReservedStackAccess). Khi thread stack gần đầy, JVM cho phép code trong critical section tiếp tục dùng vùng reserved thay vì ném ngay StackOverflowError — tránh corrupted state khi đang giữ lock.

Spring @Transactional và in-class recursion: Khi một method gọi chính nó (self-call) trong cùng class, Spring AOP proxy không intercept được vì lời gọi đi thẳng qua this, bỏ qua proxy. Nếu method đó có @Transactional, recursion sẽ không tạo nested transaction như mong đợi. Đây là behavior đáng chú ý khi kết hợp đệ quy với AOP — sẽ đề cập chi tiết hơn trong khóa Spring.

8. 📚 Deep Dive tài liệu gốc

9. Tóm tắt

• Mỗi method call push một stack frame mới lên thread stack; return pop frame đó.
• JVM thread stack mặc định 512KB–1MB (-Xss). StackOverflowError xảy ra khi depth × frame_size vượt ngưỡng này — thường ở khoảng 10k–20k frame.
• Stack frame chứa: local variables, parameters, return address, operand stack, frame pointer.
• JVM không có TCO vì debugging, stack trace integrity, và bytecode verifier model. Scala/Kotlin giải quyết bằng compile-time rewrite (@tailrec/tailrec), Java phải tự tay convert.
• Ba pattern chuyển đổi: tail recursion → accumulator + while loop; tree recursion → DP/rolling variables; general recursion → explicit Deque trên heap.
• Tăng -Xss giải quyết triệu chứng nhưng tốn memory mỗi thread — không phải giải pháp mặc định.
• Input từ bên ngoài có thể khai thác recursion để DoS: luôn giới hạn depth tường minh khi recursion phụ thuộc user input.
• Virtual Threads (JEP 444) lưu stack trên heap, giảm áp lực native stack — nhưng StackOverflowError vẫn có thể xảy ra.

10. Tự kiểm tra

public int countNodes(TreeNode root) {
  if (root == null) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

public int countNodesIter(TreeNode root) {
  if (root == null) return 0;
  int count = 0;
  Deque<TreeNode> stack = new ArrayDeque<>();
  stack.push(root);
  while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      count++;                               // count this node
      if (node.right != null) stack.push(node.right);
      if (node.left  != null) stack.push(node.left);
  }
  return count;
}

Bài tiếp theo: Amortized analysis