- Courses
- 💻Programming Languages
- 🐫OCaml (WIP)
- Functional Design Idioms
- Tail Recursion, Accumulators & Stack Safety
On this page
Tail Recursion, Accumulators, and Stack Safety in OCaml
Published on August 8, 2026
By Enrico Hochkoeppler
Web Developer & TutoriaLibre Founder
A recursive call is in tail position when it's the very last action a function performs on a given branch — nothing happens to its result afterward, because there's nothing left to do once it returns. This distinction determines whether a recursive function can run safely on arbitrarily large input, or whether it risks exhausting the call stack once its input grows large enough, and understanding it precisely is what makes the difference between a function that merely works and one that genuinely scales.
What Tail Position Actually Means
Compare two ways of writing the same factorial function:
let rec factorial n =
if n <= 1 then 1
else n * factorial (n - 1)
The recursive call factorial (n - 1) here is not in tail position — its result still has to be multiplied by n before the branch is finished, which means something is left pending after the recursive call returns. Contrast this with a version where the recursive call is genuinely the last thing that happens:
let rec factorial_tail acc n =
if n <= 1 then acc
else factorial_tail (n * acc) (n - 1)
In factorial_tail, once the recursive call is made, there is nothing left for the current invocation to do — its own result is whatever the recursive call eventually returns, with no further computation wrapped around it. That's the entire definition of a tail call: the recursive call is the final action, not one step feeding into a later one.
Why Non-Tail Recursion Can Exhaust the Stack
Every function call needs a stack frame to keep track of where to resume once that call returns, along with whatever local state that particular call still needs. In factorial, each pending multiplication (n * factorial (n - 1)) means the current call's frame has to stay alive on the stack until the recursive call beneath it finishes — the frame can't be discarded early, because there's still a multiplication waiting to use its result. For deep enough recursion, this pending chain of frames grows one for every recursive call, and a large enough input eventually exhausts the available stack space entirely, producing a stack overflow.
factorial_tail doesn't have this problem, because there's genuinely nothing left for a frame to hold onto once its recursive call is made — nothing about the current call is still needed after that point. Compilers capable of recognizing this can reuse the exact same stack frame for the next call instead of allocating a new one on top of it, effectively turning the recursion into an ordinary loop under the hood. OCaml performs exactly this optimization automatically for genuine tail calls, which is what makes factorial_tail capable of running on inputs factorial would eventually crash on.
The Accumulator Pattern
factorial_tail's extra acc parameter is the general technique for converting a non-tail-recursive function into a tail-recursive one: identify whatever computation would otherwise happen after the recursive call returns, and thread it forward instead, as an additional argument that carries the "work so far." The base case then simply returns the accumulator directly, since by the time the base case is reached, the accumulator already holds the complete answer.
The same conversion applies to a genuinely common case where the naive version has two separate problems at once: reversing a list.
let rec rev = function
| [] -> []
| h :: t -> rev t @ [h]
This isn't tail-recursive, for the same reason factorial wasn't — the result of rev t still needs @ [h] applied to it afterward. It also has a second, independent problem: @ itself walks its entire left-hand list to append something to the end, making this version of rev quadratic in time, on top of not being stack-safe. An accumulator fixes both issues simultaneously:
let rev_tail lst =
let rec go acc = function
| [] -> acc
| h :: t -> go (h :: acc) t
in
go [] lst
Here, acc accumulates the reversed list directly, one element prepended at a time, and prepending with :: is a constant-time operation, unlike appending with @. go's recursive call is in tail position — nothing happens to its result afterward — which makes this version both linear-time and stack-safe on lists of any length a program is likely to encounter.
A Quick Self-Check for Tail Position
Looking at a recursive call and asking one direct question is usually enough to determine whether it's a tail call: once this call returns, is there anything at all left to do in the current branch? If the answer is genuinely nothing — the call's result is returned immediately, exactly as-is — it's a tail call. If the result gets used in a multiplication, prepended to a list built afterward, wrapped in a constructor, or passed to another function, it isn't, and the call is holding open a stack frame that a tail call wouldn't need.
A Note on Constructor-Wrapped Recursive Calls
A recursive call of the shape h :: recurse rest — building a list by prepending to a recursive call's eventual result — looks similar to the multiplication case above, and traditionally wasn't stack-safe for exactly the same reason. More recent OCaml compilers can specially recognize this particular pattern, called tail modulo cons: since a constructor like :: can have its cell allocated immediately with a placeholder, filled in once the recursive call underneath it eventually completes, the compiler can avoid growing the stack for calls of this specific shape, without needing them rewritten into the accumulator style at all. This is a genuinely useful compiler capability, and the standard library has adopted it in places, but it applies to a specific, narrow pattern rather than to non-tail recursion generally — the accumulator technique remains the reliable, general-purpose tool for every other case where a recursive call isn't naturally in tail position.
When the Conversion Isn't Worth Making
Rewriting a function into accumulator-passing style is a real trade-off, not a pure improvement: it usually reads less directly than the naive version, and it isn't automatically justified for every recursive function on principle. A function that's only ever going to run on small, bounded inputs — recursing over a handful of items rather than potentially millions — will never come close to exhausting the stack in its naive form, and rewriting it purely for theoretical stack safety adds complexity without a practical benefit. The conversion earns its place specifically when a function might reasonably be applied to large, unbounded, or user-controlled input sizes, where a stack overflow is a genuine risk rather than a hypothetical one.
Key Takeaways
- A recursive call is in tail position when it's the last action performed on its branch, with nothing left to do once it returns; this is what allows a compiler to reuse a single stack frame instead of growing the stack with every call.
- A non-tail-recursive function keeps a pending stack frame alive for every call still waiting on further computation, which is exactly what causes deep recursion on large input to overflow the stack.
- The accumulator pattern converts a non-tail-recursive function into a tail-recursive one by threading the "work so far" forward as an extra argument, with the base case returning that accumulator directly.
- A simple self-check for tail position: is there genuinely nothing left to do once this particular recursive call returns? If something still wraps around its result, it isn't a tail call.
- Tail modulo cons lets modern OCaml compilers treat certain constructor-wrapped recursive calls, like building a list with
::, as stack-safe without an accumulator rewrite, though it applies to that specific pattern rather than to non-tail recursion in general. - Converting a function to tail-recursive style is worth doing when it might run on genuinely large or unbounded input; for small, bounded recursion, the naive version is often clearer with no real practical downside.
Found this helpful? Share the knowledge...
... or support this project to keep it alive!
Previous
Polymorphic Variants
Next
Lazy Evaluation & Streamed Data
- What Tail Position Actually Means
- Why Non-Tail Recursion Can Exhaust the Stack
- The Accumulator Pattern
- A Quick Self-Check for Tail Position
- A Note on Constructor-Wrapped Recursive Calls
- When the Conversion Isn't Worth Making
- Key Takeaways
