Tail Recursion | oCamlCase

How recursion uses memory

Every function call pushes a new frame onto the call stack. When a recursive function calls itself, it adds another frame on top of the previous one. If the recursion goes deep enough, the stack runs out of space and the program crashes with a stack overflow.

Consider factorial. When computing factorial 5, the function calls factorial 4, which calls factorial 3, and so on. Each call waits for the one beneath it to finish, then multiplies the result by n. All those pending multiplications are sitting on the stack at once.

The key observation is that factorial cannot return until its recursive call returns, because it still has work to do: multiplying n by the result. This pending work is what keeps the stack frame alive. The recursion is not in tail position because the last operation is the multiplication, not the recursive call itself.

factorial.ml

let rec factorial (n : int) : int =
  if n = 0 then 1
  else n * factorial (n - 1)

(* factorial 5 evaluates as:
   5 * factorial 4
   5 * (4 * factorial 3)
   5 * (4 * (3 * factorial 2))
   5 * (4 * (3 * (2 * factorial 1)))
   5 * (4 * (3 * (2 * 1)))
   Each pending multiplication stays on the stack. *)

What makes a call tail-recursive

A recursive call is in tail position if it is the very last thing the function does. No further computation happens after the call returns. The result of the recursive call is returned directly, with nothing piled on top of it.

countdown is tail recursive. When it calls countdown (n - 1), that is the final operation. There is nothing left to do after the call comes back, so the current stack frame is no longer needed.

Practical rule

If you return the result of a recursive call without doing anything else to it, the call is in tail position. If you wrap the result in another operation, it is not.

The difference between n * factorial (n-1) and countdown (n-1) is that the first wraps the result in a multiplication. The second returns the result directly. That distinction is everything.

countdown.ml

let rec countdown (n : int) : unit =
  if n = 0 then print_endline "done"
  else countdown (n - 1)

(* countdown (n-1) is the last thing this function does.
   Nothing happens after it returns.
   The recursive call is in tail position. *)

(* compare with factorial:
   n * factorial (n-1)
   The multiplication happens AFTER the call.
   The call is NOT in tail position. *)

Tail call optimization

When a recursive call is in tail position, the OCaml compiler can optimize it into a jump rather than a new stack frame. Because there is nothing left to do in the current frame, it can be reused for the next call. This means a tail-recursive function runs in constant stack space regardless of how deep the recursion goes.

countdown 1_000_000 will run fine if countdown is tail recursive. The same depth with a non-tail-recursive function would crash.

The accumulator pattern

Many functions that are not naturally tail recursive can be made tail recursive by introducing an accumulator: an extra argument that carries the growing result through each call. Instead of building the result on the way back up the call stack, you build it on the way down.

The trick is to pass the work-in-progress result as an argument. When the base case is reached, you return the accumulator instead of starting a chain of pending computations. The call to helper is always in tail position because it simply passes the updated accumulator forward.

Good practice

Name the inner helper aux or loop, and expose a clean interface by wrapping it in an outer function that supplies the initial accumulator value.

acc_factorial.ml

(* Tail-recursive factorial using an accumulator *)
let factorial n =
  let rec loop acc k =
    if k = 0 then acc
    else loop (acc * k) (k - 1)
  in
  loop 1 n

(* factorial 5:
   loop 1  5  ->
   loop 5  4  ->
   loop 20 3  ->
   loop 60 2  ->
   loop 120 1 ->
   loop 120 0 -> 120
   Stack stays flat throughout. *)

Divergence: hanging vs crashing

Tail recursion does not make a function correct. It only protects the stack. A tail-recursive function without a base case will still run forever, but it will hang instead of crashing. That distinction is worth understanding.

A non-tail-recursive function without a base case grows the stack on every call and eventually crashes with a stack overflow. A tail-recursive one without a base case loops forever at a flat stack depth. Both diverge, but only one takes the program down with it.

diverge.ml

(* Tail recursive: loops forever, stack stays flat *)
let rec p (x : int) : int = p x

(* Not tail recursive: grows stack, eventually crashes *)
let rec q (x : int) : int = 0 + q x

(* Correctness requires a base case.
   Tail recursion only addresses stack safety, not termination. *)

Two separate concerns

A base case ensures termination (correctness). A tail call ensures constant stack usage (efficiency). You need both. A tail-recursive function with no base case is efficient and wrong. A non-tail-recursive function with a base case is correct and potentially unsafe for large inputs.