Recursion is the workhorse of functional programming — but not all recursive declarations use machine resources equally well. In this lecture we make the cost of evaluation visible, and we meet the two standard techniques for taming it: accumulating parameters and continuations. On the way we look at how F# manages memory with a stack and a heap, because that is where the difference between a recursive and a tail-recursive function becomes concrete.
This matters beyond F#: when you review code — your own, a colleague's, or code produced by an AI assistant — "it compiles and the tests pass" says nothing about whether it survives a million-element list. Knowing why a recursive function overflows the stack, and how to see it in the shape of the code, is exactly the kind of invariant thinking this course is about.
Consider the factorial function:
let rec fact x =
match x with
| 0 -> 1
| n -> n * fact (n - 1)
What resources are needed to compute \(\mathtt{fact}(N)\)?
Following the evaluation shows the problem. Each recursive call happens
inside a multiplication, so every pending n * … has to be remembered:
|
Time and space are proportional to \(N\): the chain of pending multiplications grows as long as the recursion is deep. Is this satisfactory? For time, yes — \(N!\) needs \(N\) multiplications. For space: no, and we will see why it matters.
let rec naiveRev lst =
match lst with
| [] -> []
| x :: xs -> naiveRev xs @ [ x ]
Evaluation of naiveRev [x1; x2; ...; xn]:
|
Space demand is proportional to \(n\) — satisfactory. But the running
time of @ is linear in the length of its first argument, so the
nested appends cost \(1 + 2 + \cdots + (n-1)\) steps: time is
proportional to \(n^2\). Not satisfactory.
Efficient solutions are obtained from more general functions, whose specifications carry an extra argument:
\[\mathtt{factA}(n, m) = n! \cdot m \quad\text{for } n \ge 0\]
\[\mathtt{revA}([x_1, \ldots, x_n],\, ys) = [x_n, \ldots, x_1]\ @\ ys\]
The original functions are the special cases \(n! = \mathtt{factA}(n, 1)\) and \(\mathtt{rev}\,[x_1,\ldots,x_n] = \mathtt{revA}([x_1,\ldots,x_n], [\,])\). The parameters \(m\) and \(ys\) are called accumulating parameters: they hold the temporary result during the evaluation.
let rec factA (x, m) =
match x with
| 0 -> m
| n -> factA (n - 1, n * m)
let rec revA (lst, ys) =
match lst with
| [] -> ys
| x :: xs -> revA (xs, x :: ys)
Now the evaluation stays flat — no pending operations pile up:
|
factA runs in constant space; revA in time and space proportional
to the length of the first list. The results agree with the originals:
let reversed = revA ([ 1; 2; 3 ], [])
|
The declarations of factA and revA are tail-recursive:
factA(3, 20), revA([3], [2;1]);
Compare the traces above with the fact trace: there is nothing to the
left of the recursive call waiting to be finished.
#time toggleF# Interactive has a #time toggle that reports wall-clock time, CPU
time and garbage collections. Reversing a 20000-element list:
|
Seven seconds versus one millisecond — and note the GC columns: the
naive version made the garbage collector reclaim over a thousand
generations of dead cells; revA reclaimed none. Replacing append
(@) by cons (::) is what did it. To see why, we need the memory
model.
int) live on the stack, in the
current stack frame.
let xs = [ 5; 6; 7 ]
let ys = 3 :: 4 :: xs
let zs = xs @ ys
let n = 27
Reading the picture (from the bindings above):
ys = 3 :: 4 :: xs did not copy the cells of xs — its chain
simply continues into them. Cons reuses; this is safe because lists
are immutable.
zs = xs @ ys had to make fresh cells for the elements of xs
(the copies of 5, 6, 7 at z1–z3), and the last one links to the
ys chain. Append copies its first argument — that is exactly why
its running time is linear in the first argument's length.
Evaluating a let-expression with local declarations pushes a new
stack frame:
|
The evaluation of the local declarations is initiated by pushing a
new stack frame sf1 holding xs, ys and the auxiliary entry
result for the value of the whole let-expression:
When the evaluation completes, the top frame is popped and zs in
sf0 receives the result:
The cells marked with † are now obsolete — nothing on the stack can reach them.
The same mechanics explain why passing lists around and "modifying" them
is cheap. Consider a caller with ws = [6; 7] invoking
let addFive zs = 5 :: zs
While addFive runs, its frame sf1 holds the parameter zs — pointing
at the same cells as the caller's ws — and the result: one fresh
cell containing 5, linking straight into the existing chain:
Nothing was copied. Where imperative runtimes need tricks like
copy-on-write to make sharing safe, immutable lists get the same effect
for free: sharing is always safe because no one can write. When sf1
is popped, the caller's vs refers to [5; 6; 7] — two of whose cells
it already owned as part of ws.
The memory management system reclaims obsolete cells behind the scenes.
The .NET garbage collector partitions the heap into three
generations — gen0, gen1, gen2 — by age, with gen0 the
youngest. The design bet is that objects die young, and the #time
output above shows it paying off: naiveRev's churn happened almost
entirely in gen0/gen1.
The stack is big:
|
The heap is much bigger:
|
About \(1.2 \cdot 10^5\) stack frames versus \(1.2 \cdot 10^7\) heap cells.
The iterative bigListA does not exhaust the stack — its recursive
call is a tail call, so the same frame is reused. This is the concrete
payoff of tail recursion, and the reason the compiler can turn it into a
loop.
Tail-recursive functions are also called iterative functions: the evaluation just iterates a step function. The general shape can itself be written as a (higher-order, tail-recursive) function:
let rec iterate p f h z =
if p z then iterate p f h (f z) else h z
For suitable predicate p, step function f and finishing function
h, an iterative function repeats f until p says stop:
|
Two desirable properties: after \(n\) steps there have been \(n\) recursive
calls, at most one binding of z is active at any stage — and one
stack frame suffices. factA and revA are instances:
let factA' n = iterate (fun (x, _) -> x <> 0) (fun (x, m) -> (x - 1, x * m)) snd (n, 1)
let revA' xs =
iterate
(fun (l, _) -> not (List.isEmpty l))
(fun (l, ys) -> (List.tail l, List.head l :: ys))
snd
(xs, [])
Every while loop corresponds to a tail-recursive function, and vice
versa. The imperative counterpart of factA, in modern F# style with a
mutable local (the older ref/!/:= style is deprecated):
let factW n =
let mutable ni = n
let mutable r = 1
while ni > 0 do
r <- r * ni
ni <- ni - 1
r
Measurements show the tail-recursive version is not slower:
|
There is no performance argument for writing the loop imperatively — use whichever states the algorithm more clearly, and prefer the version with fewer moving parts.
The declaration straight from the mathematical definition is correct — and hopeless:
let rec fib x =
match x with
| 0 -> 0
| 1 -> 1
| n -> fib (n - 1) + fib (n - 2)
|
The two recursive calls recompute each other's work; fib 44 needs
around \(10^9\) base-case evaluations. An iterative version carries two
accumulators — the last two Fibonacci numbers:
let rec itfib (n, a, b) =
if n <> 0 then itfib (n - 1, a + b, a) else a
let fib30 = itfib (30, 0, 1)
|
The invariant is worth writing down (types and invariants are the course theme, after all): after \(k\) steps the arguments are \((n-k,\, F_k,\, F_{k-1})\), so when the counter reaches \(0\) the first accumulator holds \(F_n\). That one-line argument is the correctness proof.
Accumulating parameters do not make every recursion tail-recursive. Consider counting the nodes of a binary tree:
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
Whatever accumulator you add, the body must still make two recursive calls, and one of them will not be in tail position. Something more general is needed.
A continuation is a function standing for the rest of the computation. Instead of returning a result, a continuation-based function passes the result on:
let rec bigListC n c =
if n = 0 then c []
else bigListC (n - 1) (fun res -> c (1 :: res))
c.bigListC n receives
the list res built by the recursive call and passes 1 :: res
onward.
Both the recursive call and the calls of c are tail calls — the
stack does not grow. The pending work that used to sit in stack frames
now sits in closures on the heap: continuations trade stack for heap.
|
Slower than the plain version — but it can build lists the plain version cannot.
For the tree, one continuation per recursive call does the trick:
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)))
let countedNodes =
countC (Node(Node(Leaf, 1, Leaf), 2, Node(Leaf, 3, Leaf))) id
|
Both calls of countC and the call of c are tail calls, so the stack
does not grow: countC handles trees that overflow count — at the
price of allocating closures, so count remains faster on trees that
fit.
@ in recursive
declarations.
Reading: Hansen & Rischel, chapter 9. Exercise 9.8 there asks you to
declare countA : int -> BinTree<'a> -> int with
countA n t = n + count t using an accumulating parameter — do it, and
see exactly which of the two recursive calls still refuses to be a tail
call. That discovery is the whole argument for continuations.