Recursion & Tail Recursion

A call is in tail position if nothing remains to do after it returns.

8.1 let rec

let rec factorial n =
  if n <= 1 then 1 else n * factorial (n - 1)

let rec fib n = match n with
  | 0 -> 0
  | 1 -> 1
  | n -> fib (n - 1) + fib (n - 2)

8.2 Mutual recursion

let rec is_even n = if n = 0 then true else is_odd (n - 1)
and is_odd n = if n = 0 then false else is_even (n - 1)

8.3 Tail recursion & accumulators

A call is in tail position if nothing remains to do after it returns. OCaml compiles tail calls into jumps — no stack growth.

Check with the [@tailcall] attribute — the compiler warns if the call isn't a tail call:

(* NOT tail-recursive: multiply after the call *)
let rec sum = function [] -> 0 | x :: xs -> x + sum xs

(* Tail-recursive with accumulator *)
let sum lst =
  let rec go acc = function
    | [] -> acc
    | x :: xs -> go (acc + x) xs
  in
  go 0 lst

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

let rec loop n = if n = 0 then () else (loop [@tailcall]) (n - 1)

8.4 Continuation-passing style (CPS)

Turns any recursion into tail calls:

let rec map_cps f lst k = match lst with
  | [] -> k []
  | x :: xs -> map_cps f xs (fun rest -> k (f x :: rest))

let map f lst = map_cps f lst Fun.id

8.5 Tail-modulo-cons (TMC, OCaml 4.14+)

let[@tail_mod_cons] rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs     (* compiled to be stack-safe *)