Recursion & call stack — Khi đệ quy phá vỡ giới hạn ngăn xếp

TL;DR: Mỗi lời gọi hàm đẩy một stack frame lên thread stack; khi đệ quy đủ sâu, stack tràn. JVM thread stack mặc định 512KB–1MB — đủ cho khoảng 10.000–20.000 frame tùy kích thước method. JVM không có Tail-Call Optimization (TCO) vì ràng buộc về stack trace integrity và bytecode verifier model; Kotlin/Scala giải quyết bằng cách biến đệ quy đuôi thành vòng lặp ở compile time. Ba pattern chuyển đổi: đệ quy đuôi → accumulator + while; đệ quy cây → bảng DP/biến rolling; đệ quy tổng quát → Deque tường minh trên heap.

Bạn viết hàm tính giai thừa đệ 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 = 20.000, và máy ném ngay lỗi tràn ngăn xếp.

CPython cũng không khá hơn: cùng input đó sẽ gặp lỗi tương tự vì giới hạn mặc định 1.000 frame. JVM mặc định 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 đệ quy thực sự chạy thế nào, 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à tràn ngăn xếp.

2. Stack frame là gì — cơ chế bên dưới

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

• Mảng biến cục bộ: các biến trong hàm và tham số đầu vào.
• Ngăn xếp toán hạng: vùng tính toán trung gian (giá trị tạm khi tính biểu thức).
• Return address: địa chỉ để biết nhảy về đâu khi hàm 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ố biến cục bộ — hàm đơn giản có thể chỉ 32–64 byte, hàm nhiều biến có thể 128 byte hoặc hơn. Công thức đơn giản: khi chiều sâu × kích thước frame vượt giới hạn stack, máy ném lỗi tràn ngăn xếp.

-- Giai thừa đệ quy: mỗi lời gọi đẩy một frame mới lên thread stack.
-- Frame của factorial(n) chứa: tham số n, return address về caller.
factorial(n):
    if n <= 1: return 1               -- base case: return pop frame này
    return n * factorial(n-1)         -- lời gọi đệ quy: push frame mới
    -- CHÚ Ý: n * (...) nghĩa là frame này phải tồn tại cho đến khi
    -- factorial(n-1) trả về. Đó là lý do TCO không áp dụng ở đây.

Time: O(n)  Space: O(n) -- n frame đồng thời trên ngăn xếp

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

[factorial(1)]   -- đỉnh ngăn xếp (lời gọi gần nhất)
[factorial(2)]
[factorial(3)]
[factorial(4)]
[factorial(5)]   -- đáy (lời gọi đầu tiên)
[main]

Runtime 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. Sơ đồ phát triển ngăn xếp — fib(4)

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

graph TD
    F4["fib(4)"]
    F3a["fib(3)"]
    F2a["fib(2)"]
    F1a["fib(1) → 1"]
    F0a["fib(0) → 0"]
    F1b["fib(1) → 1"]
    F2b["fib(2)"]
    F1c["fib(1) → 1"]
    F0b["fib(0) → 0"]

    F4 --> F3a
    F4 --> F2b
    F3a --> F2a
    F3a --> F1b
    F2a --> F1a
    F2a --> F0a
    F2b --> F1c
    F2b --> F0b

Độ sâu ngăn xếp 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 hàm — hàm không cần làm gì thêm với kết quả trả về. Ví dụ:

-- Giai thừa đệ quy đuôi với accumulator.
-- Lời gọi đệ quy là thao tác CUỐI -- không còn gì để tính sau khi nó trả về.
-- Compiler có TCO có thể tái dùng frame hiện tại thay vì push frame mới.
factorialTail(n, acc):
    if n <= 1: return acc
    return factorialTail(n-1, n * acc)  -- vị trí đuôi: kết quả dùng trực tiếp

Time: O(n)  Space: O(n) trên JVM (O(1) nếu có TCO)

Trong version này, factorialTail(n-1, n × acc) là lệnh cuối — hàm không cần giữ lại bất kỳ gì từ frame hiện tại sau khi lời gọi này trả về. Về lý thuyết, compiler có thể tái dùng frame hiện tại thay vì push frame mới — gọi là Tail-Call Optimization (TCO). Nếu có TCO, đệ quy 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: Các công cụ debugger, profiler, và APM agent đề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. Bytecode verifier của JVM: Mô hình verification 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. Chưa có đề xuất nào được merge: Tính đến Java 21, không có đề xuất 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à từ khóa tailrec (Kotlin) khiến compiler biến tail recursion thành vòng lặp trong bytecode trước khi JVM nhìn thấy.

-- Tương đương với những gì Kotlin/Scala làm ở compile time:
-- Chuyển factorialTail() thành vòng lặp thủ công.
factorialIterative(n):
    acc <- 1
    while n > 1:
        acc <- acc * n
        n <- n - 1
    return acc

Time: O(n)  Space: O(1)

Lập trình viên Java phải tự tay làm bước chuyển đổi này.

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

5.1 Đệ quy đuôi — accumulator + vòng lặp while

Bất kỳ hàm đệ quy đuôi nào cũng có thể chuyển cơ học thành vòng lặp while:

-- Trước: đệ quy đuôi -- tràn ngăn xếp ở độ sâu ~10k-20k trên JVM
factorialTail(n, acc):
    if n <= 1: return acc
    return factorialTail(n-1, n * acc)

-- Sau: iteration với accumulator -- độ sâu không giới hạn
factorialIter(n):
    acc <- 1
    while n > 1:
        acc <- acc * n
        n <- n - 1
    return acc

Time: O(n)  Space: O(1)

5.2 Đệ quy cây — bảng DP hoặc biến rolling

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

-- O(2^n) đệ quy thuần túy -- KHÔNG dùng cho n lớn hơn 40
fibNaive(n):
    if n <= 1: return n
    return fibNaive(n-1) + fibNaive(n-2)

Time: O(2^n)  Space: O(n)

-- O(n) time, O(1) space -- hai biến rolling
fibFast(n):
    if n <= 1: return n
    prev <- 0
    curr <- 1
    for i <- 2 đến n:
        next <- prev + curr
        prev <- curr
        curr <- next
    return curr

Time: O(n)  Space: O(1)

5.3 Đệ quy tổng quát — Deque tường minh thay ngăn xếp JVM

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

-- DFS iteration dùng stack tường minh trên heap
-- Tránh tràn ngăn xếp với cây lồng rất sâu (ví dụ 50k cấp từ input không tin cậy).
dfsIterative(root):
    if root = NIL: return
    S <- Stack rỗng
    S.push(root)
    while S không rỗng:
        node <- S.pop()
        process(node)                       -- thăm node
        if node.right != NIL: S.push(node.right)    -- push phải trước
        if node.left  != NIL: S.push(node.left)     -- trái được xử lý trước

Time: O(n)  Space: O(n) -- trên heap thay vì thread stack

6. Pitfall tổng hợp

Pitfall 1: Quên base case — tràn ngăn xếp ngay lập tức.

-- Thiếu base case -- đệ quy vô hạn, tràn ngăn xếp ngay
countDown(n):
    return countDown(n-1)   -- quên: if n = 0: return 0

-- Đã sửa: base case tường minh kết thúc đệ quy
countDownFixed(n):
    if n <= 0: return 0     -- base case
    return countDownFixed(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 hàm lặp lại hàng nghìn dòng.

Pitfall 2: Độ sâu phụ thuộc input từ bên ngoài — cửa cho tấn công từ chối dịch vụ.

Hàm 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 kẻ tấn công có thể gửi JSON lồng 50.000 cấp — mỗi cấp push một frame, máy crash trong mili giây. Nhiều thư viện JSON giới hạn độ lồng mặc định chính xác để ngăn điều này.

-- Giới hạn độ sâu đệ quy khi input đến từ nguồn bên ngoài
flattenJson(node, depth, result):
    if depth > 100:
        throw IllegalArgumentException("Độ lồng JSON vượt giới hạn: " + depth)
    if node là object:
        for each (key, value) trong node:
            flattenJson(value, depth+1, result)
    else:
        result["leaf_" + depth] <- node.value

Time: O(n)  Space: O(depth)

Pitfall 3: Tăng giới hạn stack trông như giải pháp nhưng có giá.

Tăng giới hạn stack từ 512KB lên 8MB giải quyết tràn ngăn xếp tạm thời, nhưng:

• Mỗi thread reserve toàn bộ 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ù.

Giới hạn stack là tham số 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à giới hạn độ sâu: Nhiều thư viện JSON giới hạn độ lồng mặc định (thường 500–1000 cấp). Nếu bạn tự viết recursive parser, hãy thêm bộ đếm độ sâu và ném exception khi vượt ngưỡng — trước khi runtime làm điều đó bằng lỗi tràn ngăn xếp mà không cho bạn cơ hội handle.

Thread với kích thước stack tùy chỉnh: Một số runtime cho phép đặt stack size riêng cho từng 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 giới hạn toàn cục cho tất cả thread.

Virtual Threads (JEP 444 — Java 21): Virtual thread lưu stack trên heap thay vì native thread stack. Khi virtual thread block, runtime 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 stack size. Tuy nhiên, tràn ngăn xếp vẫn có thể xảy ra khi đệ quy quá sâu, chỉ là ngưỡng cao hơn đáng kể.

Reserved Stack Areas (Java 9+): JVM dành riêng một vùng nhỏ ở cuối stack cho critical section code. 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 lỗi tràn ngăn xếp — tránh corrupted state khi đang giữ lock.

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

9. Tóm tắt

• Mỗi lời gọi hàm push một stack frame mới lên thread stack; return pop frame đó.
• Thread stack mặc định 512KB–1MB. Tràn ngăn xếp xảy ra khi chiều sâu × kích thước frame vượt ngưỡng này — thường ở khoảng 10k–20k frame.
• Stack frame chứa: biến cục bộ, tham số, return address, ngăn xếp toán hạng, 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: đệ quy đuôi → accumulator + vòng lặp while; đệ quy cây → DP/biến rolling; đệ quy tổng quát → Deque tường minh trên heap.
• Tăng giới hạn stack 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 đệ quy để tấn công từ chối dịch vụ: luôn giới hạn độ sâu tường minh khi đệ quy phụ thuộc user input.
• Virtual Threads (JEP 444) lưu stack trên heap, giảm áp lực native stack — nhưng tràn ngăn xếp vẫn có thể xảy ra.

10. Tự kiểm tra

countNodes(root):
  if root = NIL: return 0
  return 1 + countNodes(root.left) + countNodes(root.right)

countNodesIter(root):
  if root = NIL: return 0
  count <- 0
  S <- Stack rỗng
  S.push(root)
  while S không rỗng:
      node <- S.pop()
      count <- count + 1              -- đếm node này
      if node.right != NIL: S.push(node.right)
      if node.left  != NIL: S.push(node.left)
  return count

Time: O(n)  Space: O(n) -- trên heap, không bị giới hạn bởi thread stack

Bài tiếp theo: Amortized analysis