On this page

Tail Recursion, Accumulators, and Stack Safety in OCaml

Published on August 8, 2026

Enrico Hochkoeppler Profile

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​

Found this helpful? Share the knowledge...

... or support this project to keep it alive!

Buy Me a Coffee

Previous

Polymorphic Variants

Next

Lazy Evaluation & Streamed Data