Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 40 ยท Functions and Recursion

Tail Recursion and the Stack in OCaml

Learn what a tail call is, why OCaml turns it into a loop, how to rewrite recursion with accumulators, and when stack overflow still matters for List functions.

Recursion has a cost: every call that is still waiting for its result keeps a stack frame in memory. A function that recurses a million times deep can run out of stack. OCaml avoids that problem for a special form of call, the tail call, by reusing the current frame, so a tail-recursive function runs in constant stack space, just like a loop.

What is a tail call?

A call is in tail position if it is the very last thing the function does, so that its result becomes the function's result with nothing left to do.

OCAML
let rec sum_to n =
  if n = 0 then 0
  else n + sum_to (n - 1)       (* NOT a tail call: after returning we still add n *)
OCAML
let rec count_down n =
  if n = 0 then "done"
  else count_down (n - 1)       (* tail call: nothing is left to do afterwards *)

In sum_to, each call must wait for sum_to (n - 1) and then add. For n = 1_000_000 the stack holds a million frames. That still fits in OCaml 5 (its stack limit is large by default, set with the l parameter of OCAMLRUNPARAM), but depth in the hundreds of millions, or infinite recursion, ends with a Stack_overflow exception and costs a lot of memory on the way. OCaml 4.x had a much smaller system-stack limit, so the same code could fail there.

count_down calls itself last. The compiler replaces the call by a jump, so the stack never grows.

Accumulators

To make a function tail-recursive, add a parameter that carries the partial result, the accumulator:

OCAML
let sum_to n =
  let rec go acc k =
    if k = 0 then acc
    else go (acc + k) (k - 1)
  in
  go 0 n

Here go is tail-recursive: after the recursive call returns, nothing else happens. sum_to 10_000_000 works without trouble.

The transformation is mechanical:

  1. Add an accumulator parameter holding "the answer so far".
  2. In the base case, return the accumulator.
  3. In the recursive case, update the accumulator and call yourself in tail position.
  4. Wrap it in a user-facing function that supplies the initial accumulator (go 0 n).

Factorial and Fibonacci

OCAML
let factorial n =
  let rec go acc n =
    if n <= 1 then acc else go (acc * n) (n - 1)
  in
  go 1 n

let fib n =
  let rec go a b k =
    if k = 0 then a else go b (a + b) (k - 1)
  in
  go 0 1 n

fib is now linear instead of exponential (fib 50 = 12586269025). Two accumulators a and b hold two consecutive Fibonacci numbers.

Lists: build backwards, then reverse

Non-tail-recursive list code such as x :: f rest overflows on very long lists. The tail-recursive form accumulates in reverse:

OCAML
let map_tr f lst =
  let rec go acc = function
    | [] -> List.rev acc
    | x :: rest -> go (f x :: acc) rest
  in
  go [] lst

List.rev at the end puts the elements back in order. This is O(n) extra work, but constant stack.

What the standard library does

Historically, List.map was not tail-recursive and could overflow on lists with hundreds of thousands of elements. Since OCaml 5.1, List.map and many others are written to be tail-recursive modulo cons (TRMC): the compiler turns x :: f rest into a loop when you annotate the function with [@tail_mod_cons]. You can do the same in your own code:

OCAML
let[@tail_mod_cons] rec map f = function
  | [] -> []
  | x :: rest -> let y = f x in y :: map f rest

For most functions, though, it is still good practice to know which ones consume stack: List.append (@) on a long left operand, List.fold_right, List.concat and so on on huge lists. List.fold_left is tail-recursive, which is one reason to prefer it.

Checking and enforcing tail position

You can ask the compiler to reject a recursive call that is not in tail position:

OCAML
let rec go acc n =
  if n = 0 then acc else (go [@tailcall]) (n :: acc) (n - 1)

If the annotated call is not a tail call, the compiler emits a warning.

Which calls are tail calls?

  • The branches of if, match and let ... in bodies are in tail position when the whole expression is.
  • Arguments of operators are not: n + f x and x :: f rest have work after the call.
  • A call inside try ... with is not a tail call (the handler must stay on the stack).

When not to bother

If the recursion depth is bounded by something small, such as the depth of a balanced tree (about 20 for a million nodes), plain recursion is fine and often clearer. Reach for accumulators when the depth can be the size of the input.

A stand-in: stack depth

JavaScript engines do not eliminate tail calls, but we can show the effect by counting the depth. The stand-in simulates "stack frames" explicitly: the non-tail version keeps a frame per call, while the accumulator version runs in a loop.

JS Stand-in: pending frames vs a loop

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which call is a tail call?

    A tail call's result is directly the function's result, with nothing left to do after it.
  2. 2. What does an accumulator do?

    The accumulator holds the answer so far, so no work remains after the recursive call.
  3. 3. Why do list-building tail-recursive functions often end with List.rev?

    Prepending is cheap but reverses the order; one final reversal restores it.
  4. 4. Is a call inside try ... with a tail call?

    A try block must keep its handler frame, so calls inside it are not tail calls.

Summary

  • A tail call is the last action of a function; OCaml compiles it into a jump.
  • Tail-recursive functions use constant stack, like loops.
  • Add an accumulator parameter and a go helper to convert ordinary recursion.
  • Build lists in reverse and finish with List.rev, or use [@tail_mod_cons].
  • [@tailcall] asks the compiler to check tail position.

Next: Labeled and optional arguments