Diagnosing Stack_overflow in OCaml: From Symptom to Fix

Your OCaml program passes every unit test, then dies on real data with an uncaught Stack_overflow. The useful takeaway: this is almost never a logic bug. It means a recursive call is consuming one stack frame per level, and your input is deeper than the stack. OCaml guarantees that a function's self tail-call compiles into a loop, so the fix is usually to find the one call that is not in tail position and restructure it.

Recognizing the condition

The classic signature is an uncaught Stack_overflow exception raised deep inside a recursive function, triggered only by large inputs: long lists, deep trees, or deeply nested ASTs. Small inputs work fine, which is why it slips through tests. In bytecode (ocamlc) the interpreter raises it at its configured stack limit. In native code (ocamlopt) on Linux it is raised via a guard page on the native thread stack. On platforms without guard-page support, a native overflow may abort the process instead of raising the exception, so a hard crash and a clean exception can be the same bug on different targets.

Cause and diagnostic table

Ordered checks

1. Reproduce minimally. Build the smallest input that triggers it and confirm the failure threshold grows with input size. If depth does not matter, you have a logic bug (infinite recursion), not a stack-depth problem.
2. Mark tail positions. For each recursive call, ask: does anything happen to the result after the call returns? 1 + len t and x :: map f t are both non-tail because the addition and the cons happen after the recursive call.
3. Run the bytecode build. Bytecode raises Stack_overflow reliably at its configured limit, which makes it a more predictable diagnostic environment than native code.
4. Get a backtrace. Rebuild with -g and run with OCAMLRUNPARAM=b in the environment (for bytecode; for native builds, compile with -g and check your version's manual for backtrace support). The backtrace should name the recursive function. Exact runtime parameters vary by release, so confirm against the manual for your installed compiler.
5. Vary the stack limit. On Linux, raise the shell's stack limit with ulimit -s (run in your shell; affects subsequently launched processes; requires no special permissions for raising a soft limit up to the hard limit). If a larger stack pushes the failure to proportionally larger inputs, the diagnosis is confirmed: bounded stack, unbounded depth.

Fixes tied to findings

Non-tail list recursion: accumulate and reverse

The canonical case. This overflows on a multi-million-element list:

let rec len = function
  | [] -> 0
  | _ :: t -> 1 + len t   (* addition after the call: non-tail *)

Move the work into an accumulator so the recursive call is the last thing evaluated:

let len xs =
  let rec aux acc = function
    | [] -> acc
    | _ :: t -> aux (acc + 1) t   (* self tail-call: compiles to a loop *)
  in
  aux 0 xs

For transformations, accumulate results onto a list (cheap cons) and call List.rev once at the end, or use List.fold_left, which is tail-recursive. One caution: the tail-recursion status of individual Stdlib list and array functions has changed across releases, so check the documentation for the exact version you deploy rather than assuming.

Deep trees: CPS or an explicit worklist

Tree walks often cannot be made tail-recursive with a simple accumulator because there are two recursive calls. Convert to continuation-passing style (each call passes a function describing what to do next, so every call is in tail position), or replace the call stack with an explicit heap-allocated worklist:

let rec sum_worklist stack acc =
  match stack with
  | [] -> acc
  | Leaf :: rest -> sum_worklist rest acc
  | Node (l, n, r) :: rest -> sum_worklist (l :: r :: rest) (acc + n)

The worklist lives on the heap, so depth is bounded by memory, not the thread stack.

Mutual recursion: merge or trampoline

If the cycle spans functions (a calls b calls a), merge them into one function driven by a variant describing the current state, or use a trampoline: functions return a thunk (a suspended next step) instead of calling each other, and a driver loop forces the thunks one at a time in constant stack.

Genuinely deep data

If the data is legitimately millions of levels deep, restructure the algorithm to process it incrementally, or run the work on a thread created with a larger stack where your platform allows it. Raising limits buys headroom but does not scale.

Escalation criteria

Escalate beyond a simple rewrite when: overflow happens at shallow depths (suggests a hidden non-tail wrapper or recursion inside a library — instrument with a depth counter); the overflow survives a correct tail-recursive rewrite (look for non-tail calls inside stdlib or third-party functions and check their docs for your version); or you get a segfault instead of Stack_overflow in native code (points to C stubs, FFI, or missing guard-page support — a memory-level problem, not an OCaml recursion problem).

Finally, do not catch Stack_overflow and retry. The handler runs with the stack nearly exhausted, and the exception can surface far from the true recursion site. Treat it as a design signal: bound the recursion depth or restructure the algorithm.

Verifying the fix

Re-run the minimal reproducer at the original failing size and at several times that size; a tail-recursive version's memory usage should stay flat as input grows. Re-run with OCAMLRUNPARAM=b to confirm no backtrace appears, and test both bytecode and native builds on each target OS, since stack limits and overflow detection differ between them.