Tail recursion

Stack, heap and the cost of evaluation

ITT8060 Advanced Programming · Autumn 2026

Tallinn University of Technology

Full prose version: notes.html

ITT8060

Resources of a computation

Two questions about any evaluation:

Computation time — the number of individual computation steps.

Space — the maximal memory needed during the evaluation to represent expressions and bindings.

Plan for today:

recursion has a cost → accumulating parameters → the stack/heap model → iteration in general → continuations.

ITT8060

let rec fact x =
  match x with
  | 0 -> 1
  | n -> n * fact (n - 1)

Factorial (I)

What resources are needed to compute \(\mathtt{fact}(N)\)?

Every recursive call sits inside a multiplication —

each pending n * … must be remembered.

ITT8060

fact N
~> N * fact (N-1)
~> N * ((N-1) * fact (N-2))
~> ...
~> N * ((N-1) * ((N-2) *
     (... (3 * (2 * 1)) ...)))
~> ...
~> N!

Factorial (II)

The chain of pending multiplications grows as deep as the recursion.

Time: proportional to \(N\) — fine.

Space: proportional to \(N\) — is this satisfactory?

ITT8060

naiveRev [x1; x2; ...; xn]
~> naiveRev [x2; ...; xn] @ [x1]
~> (naiveRev [x3; ...; xn] @ [x2]) @ [x1]
~> ...
~> ((...(([] @ [xn]) @ [xn-1]) @ ...)
      @ [x2]) @ [x1]

Naive reversal

let rec naiveRev lst =
  match lst with
  | []      -> []
  | x :: xs -> naiveRev xs @ [x]

@ is linear in its first argument, so the nested appends cost \(1 + 2 + \cdots + (n-1)\) steps.

Space \(\sim n\): satisfactory. Time \(\sim n^2\): not satisfactory.

ITT8060

Accumulating parameters

carry the temporary result along

ITT8060

More general functions

Efficient solutions come from more general functions with an extra argument:

\[\mathtt{factA}(n, m) = n! \cdot m \qquad (n \ge 0)\]

\[\mathtt{revA}([x_1, \ldots, x_n],\, ys) = [x_n, \ldots, x_1]\ @\ ys\]

The originals are the special cases:

\[n! = \mathtt{factA}(n, 1) \qquad \mathtt{rev}\,[x_1,\ldots,x_n] = \mathtt{revA}([x_1,\ldots,x_n], [\,])\]

\(m\) and \(ys\) are accumulating parameters: they hold the temporary result during the evaluation.

ITT8060

let rec factA (x, m) =
  match x with
  | 0 -> m
  | n -> factA (n - 1, n * m)

Declaration of `factA`

factA(5, 1)
~> factA(4, 5)
~> factA(3, 20)
~> ...
~> factA(0, 120)
~> 120

Space demand: constant.

Time demand: proportional to \(n\).

ITT8060

let rec revA (lst, ys) =
  match lst with
  | []      -> ys
  | x :: xs -> revA (xs, x :: ys)

Declaration of `revA`

revA([1;2;3], [])
~> revA([2;3], 1 :: [])
~> revA([3],   [2; 1])
~> revA([],    [3; 2; 1])
~> [3; 2; 1]

Space and time: proportional to \(n\), the length of the first list.

@ has been replaced by ::.

ITT8060

Tail-recursive functions

factA and revA are tail-recursive:

the recursive call is the last function application evaluated in the body — e.g. factA(3, 20), revA([3], [2;1]).

Consequence: only one set of bindings for the argument identifiers is needed during the whole evaluation.

Compare with fact: nothing is waiting to the left of the call.

ITT8060

> let xs16 = List.replicate 1000000 16;;
> #time;;  // toggle in F# Interactive

> for i in xs16 do fact i |> ignore;;
Real: 00:00:00.051, CPU: 00:00:00.046

> for i in xs16 do
    factA (i, 1) |> ignore;;
Real: 00:00:00.024, CPU: 00:00:00.031

> for i in xs16 do () ;;
Real: 00:00:00.012, CPU: 00:00:00.015

Measurements: factorial

#time reports elapsed time, CPU time and garbage collections.

The for loop alone costs ~12 ms —

the real gain of factA is much better than the visible factor 2.

ITT8060

> let xs20000 = [1 .. 20000];;

> naiveRev xs20000;;
Real: 00:00:07.624, CPU: 00:00:07.597,
GC gen0: 825, gen1: 253, gen2: 0

> revA (xs20000, []);;
Real: 00:00:00.001, CPU: 00:00:00.000,
GC gen0: 0, gen1: 0, gen2: 0

Measurements: reversal

7.6 seconds versus 1 millisecond.

Look at the GC columns: the naive version had 825 + 253 collections;

revA reclaimed nothing.

Reducing @ to :: did that. To see why — memory management.

ITT8060

Stack and heap

where values actually live

ITT8060

let xs = [5; 6; 7]
let ys = 3 :: 4 :: xs
let zs = xs @ ys
let n = 27

Memory management

Primitive values (int, …) live on the stack, in the current stack frame.

Composite values (lists) are built from cons cells on the heap; the stack holds references into it.

What does memory look like after these four bindings?

ITT8060

No unnecessary copying

ys = 3 :: 4 :: xs — not copied: its chain continues into xs.

zs = xs @ ys — fresh cells for the elements of xs only; the last one links to the ys chain.

Safe because lists are immutable — and exactly why @ is linear in its first argument.

ITT8060

Operations on the stack: push

let zs = let xs = [1; 2]
         let ys = [3; 4]
         xs @ ys

Evaluating the local declarations pushes frame sf1: bindings for xs, ys and the auxiliary entry result for the value of the whole let-expression.

ITT8060

Operations on the stack: pop

The top frame is popped when the let-expression completes; zs receives the result.

The cells marked † are now unreachable — obsolete.

ITT8060

Sharing across calls

let ws = [6; 7]
let addFive zs = 5 :: zs
let vs = addFive ws

zs in sf1 points at the same cells as the caller's ws;

the result is one fresh cell linking into the existing chain.

Imperative runtimes need copy-on-write to share safely.

Immutable lists share for free — no one can write.

ITT8060

Operations on the heap: garbage collection

The garbage collector reclaims obsolete cells behind the scenes, managing the heap in three generations by age: gen0 (youngest), gen1, gen2.

Design bet: objects die young.

naiveRev xs20000;;
GC gen0: 825, gen1: 253, gen2: 0

The churn stayed in the young generations — the bet pays off.

ITT8060

> let rec bigList n =
    if n = 0 then []
    else 1 :: bigList (n-1);;
> bigList 120000;;
val it: int list = [1; 1; 1; ...]
> bigList 130000;;
Process is terminated due to
StackOverflowException.

> let rec bigListA n xs =
    if n = 0 then xs
    else bigListA (n-1) (1 :: xs);;
> bigListA 12_000_000 [];;
val it: int list = [1; 1; 1; ...]
> bigListA 13_000_000 [];;
System.OutOfMemoryException: ...

The limits

Stack: ~\(1.2 \cdot 10^5\) frames.

Heap: ~\(1.2 \cdot 10^7\) cells — two orders of magnitude more.

bigListA does not exhaust the stack. Why?

Its call is a tail call — the same frame is reused.

That is the entire secret.

ITT8060

Iterative functions

tail recursion in general

ITT8060

let rec iterate p f h z =
  if p z then iterate p f h (f z)
  else h z

Iteration, precisely

A function is iterative if it is an instance of this shape, for a predicate p, step function f and finishing function h.

factA iterates \(f(n, m) = (n-1,\ n \cdot m)\).

revA iterates \(g(x :: xs,\ ys) = (xs,\ x :: ys)\).

ITT8060

iterate p f h v
~> iterate p f h (f v)        [z ↦ v]
~> iterate p f h (f (f v))    [z ↦ f v]
~> ...
~> h (fⁿ v)     when p (fⁿ v) = false

Evaluating an iteration

Observe the desirable properties:

\(n\) recursive calls, but at most one binding of z active at any stage —

— and therefore one stack frame suffices.

The compiler turns this into a loop.

ITT8060

Iteration vs while loops

let factW n =
  let mutable ni = n
  let mutable r = 1
  while ni > 0 do
    r  <- r * ni
    ni <- ni - 1
  r

> for i in 1..1000000 do
    factA (16, 1) |> ignore;;
Real: 0.024 s, GC gen0: 0

> for i in 1..1000000 do
    factW 16 |> ignore;;
Real: 0.048 s, GC gen0: 9

Every while loop corresponds to a tail-recursive function, and vice versa — and measured, the tail-recursive version is not slower than the loop.

(Modern style: let mutable — ref/!/:= are deprecated.)

ITT8060

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

Fibonacci (I)

Straight from the definition — and hopeless:

fib 4
~> fib 3 + fib 2
~> (fib 2 + fib 1) + fib 2
~> ((fib 1 + fib 0) + fib 1)
     + fib 2
~> ...

The two calls recompute each other's work.

fib 44 needs around \(10^9\) base-case evaluations.

ITT8060

let rec itfib (n, a, b) =
  if n <> 0 then itfib (n - 1, a + b, a)
  else a

Fibonacci (II)

Two accumulators — the last two Fibonacci numbers:

itfib(n, 0, 1)
~> itfib(n-1, F₁, F₀)
~> itfib(n-2, F₂, F₁)
~> ...
~> itfib(0, Fₙ, Fₙ₋₁)  ~>  Fₙ

Invariant after \(k\) steps: arguments are \((n-k,\ F_k,\ F_{k-1})\).

The invariant is the correctness proof.

ITT8060

Continuations

when accumulators are not enough

ITT8060

type BinTree<'a> =
  | Leaf
  | Node of BinTree<'a> * 'a * BinTree<'a>

let rec count t =
  match t with
  | Leaf            -> 0
  | Node (tl, _, tr) ->
      count tl + count tr + 1

Try it: countA : int -> BinTree<'a> -> int with countA n t = n + count t — the inner call still grows the stack. (Hansen & Rischel, Ex. 9.8)

Limits of accumulating parameters

Whatever accumulator you add, the body still makes two recursive calls —

— and one of them cannot be in tail position.

ITT8060

let rec bigListC n c =
  if n = 0 then c []
  else bigListC (n - 1)
        (fun res -> c (1 :: res))

Continuations

A continuation c is a function for the rest of the computation.

Base case: feed the result to c.

Recursive case: the continuation of bigListC (n-1) is fun res -> c (1 :: res).

Both the recursive call and the calls of c are tail calls.

ITT8060

> bigListC 16_000_000 id;;
Real: 00:00:08.586, CPU: 00:00:08.314,
GC gen0: 80, gen1: 60, gen2: 3
val it: int list = [1; 1; 1; ...]

Trading stack for heap

The pending work that used to sit in stack frames now sits in closures on the heap.

Slower than bigList — but it can build lists that bigList cannot (recall: bigList overflowed at 130 000).

ITT8060

let rec countC t c =
  match t with
  | Leaf -> c 0
  | Node (tl, _, tr) ->
    countC tl (fun vl ->
      countC tr (fun vr ->
        c (vl + vr + 1)))

Tail-recursive count

Both calls of countC are tail calls; the call of c is a tail call.

The stack does not grow.

> let t =
    Node(Node(Leaf,1,Leaf), 2,
         Node(Leaf,3,Leaf));;
> countC t id;;
val it: int = 3

countC handles bigger trees than count — count is faster on trees that fit.

ITT8060

Summary and recommendations

Loops in imperative languages = a special case of recursion: tail-recursive (iterative) functions.

Have iterative functions in mind when efficiency matters: avoid huge chains of pending operations, and inadequate @ in recursive declarations.

Memory management: stack (frames, primitives), heap (cons cells, closures), generational garbage collection.

Continuations turn arbitrary recursion tail-recursive — trading stack for heap.

None of this replaces the algorithmic idea: iterative functions do not substitute for good algorithms and data structures.

ITT8060

Tail recursion

Stack, heap and the cost of evaluation

Resources of a computation

Factorial (I)

Factorial (II)

Naive reversal

Accumulating parameters

carry the temporary result along

More general functions

Declaration of factA

Declaration of revA

Tail-recursive functions

Measurements: factorial

Measurements: reversal

Stack and heap

where values actually live

Memory management

No unnecessary copying

Operations on the stack: push

Operations on the stack: pop

Sharing across calls

Operations on the heap: garbage collection

The limits

Iterative functions

tail recursion in general

Iteration, precisely

Evaluating an iteration

Iteration vs while loops

Fibonacci (I)

Fibonacci (II)

Continuations

when accumulators are not enough

Limits of accumulating parameters

Continuations

Trading stack for heap

Tail-recursive count

Summary and recommendations

Declaration of `factA`

Declaration of `revA`