Tail Recursion and Accumulators

Definition of tail recursion

A recursive function is tail-recursive (or iterative) if the recursive call is the last operation in the function — nothing remains to be done after it returns. The computation does not nest; each call’s work is completed before the next call begins.

(* Not tail-recursive: addition happens after the recursive call *)
let rec nsum n =
  if n = 0 then 0
  else n + nsum (n - 1)    (* + happens after nsum returns *)

(* Tail-recursive: nothing after the recursive call *)
let rec summing n total =
  if n = 0 then total
  else summing (n - 1) (n + total)   (* summing is the last thing *)

Tail-recursive functions produce computations resembling those done by while-loops in conventional languages.

Accumulators

An accumulator is an extra argument that carries a running result through recursive calls:

summing 3 0          (* start with accumulator = 0 *)
=> summing 2 3       (* accumulator updated to 3 *)
=> summing 1 5       (* accumulator updated to 5 *)
=> summing 0 6       (* accumulator updated to 6 *)
=> 6                 (* return final accumulator *)

The accumulator replaces the need to “remember” intermediate results on the call stack. Each recursive call updates it and passes it forward.

When to use accumulators (KISS)

The KISS principle (Keep It Simple, Stupid) applies:

• Write straightforward code first, avoiding only gross inefficiency
• Do not add accumulators merely out of habit
• If the program is too slow, profiling tools can pinpoint the cause

For power (binary exponentiation), adding an accumulator makes it iterative but complicates the code. The gain is minute — at most 30 nested calls for 32-bit exponents. Not worth it.

For nsum with n = 10000, the stack overflow risk is real. Worth it.

Recursion vs iteration trade-offs

Recursion	Iteration
Natural for many algorithms	Required in some languages
Can express divide-and-conquer	Can be awkward for tree/graph problems
Stack overhead if not tail-recursive	Constant stack space

Many algorithms are expressed naturally using recursion but only awkwardly using iteration. Dijkstra famously sneaked recursion into Algol-60 by inserting the words “any other occurrence of the procedure name denotes execution of the procedure” — carefully avoiding the word “recursion” to slip it past sceptical colleagues.

Tail recursion and the compiler

Tail-recursive code is only efficient if the compiler detects it and optimises accordingly (tail-call optimisation). OCaml performs this optimisation: a tail-recursive call reuses the same stack frame rather than allocating a new one. The main benefit is space (memory), though iterative code can sometimes also run faster.