Recursion patterns & tail calls

The call stack Three deep dives Worked example

A loop changes a counter; a recursive function calls itself on a smaller problem until it reaches a case small enough to answer outright. With immutable data and no mutable counter, recursion is how functional code repeats.

F1.06 proved recursion sound through induction: a base case plus a step that shrinks the input. This hub takes the working view and splits into three deep dives. First the shape of a recursive function and the call stack it builds; then tail calls and the accumulator pattern that flatten that stack to constant space; then the patterns that recur — sum, length, reverse, map, filter — each of them a fold. Trace the stack on the right, then take the three pages in order.

Body recursion grows the stack; a tail call keeps it flat

stack depth 1 · body recursion holds every pending frame until sum([]) turns it around.

The call stack

A recursive call does not finish until the call it makes finishes. So calls pile up: each sum(list) waits on sum(tail), pushing a frame onto the stack. The base case sum([]) returns a value outright, and then the stack unwinds — each frame adds its element to the result coming back up.

Step through sum([1, 2, 3, 4]) and watch the stack grow, then unwind.

recursion: a function defined in terms of itself on a smaller input.
base case: the input small enough to answer without recursing.
recursive case: reduce the problem and call the function on the smaller part.
call stack: the frames of calls still waiting on the calls they made.

sum([1, 2, 3, 4]) · grow, then unwind

step 1 / 9

step 1 · call sum([1, 2, 3, 4]) · stack depth 1

F1.06 · induction

A base case and a step that shrinks the input — the same structure that proves a recursion ends.

Elixir

Clauses match the shapes: sum([]) is the base, sum([h | t]) recurses.

Body recursion does its work on the way back up: the stack holds every pending frame until the base case turns it around. That depth is the cost the next page removes.

Three deep dives

This module is three pages. Read them in order: each builds on the last.

F2.04.1

The shape of recursion

Base case, recursive case, and the call stack growing then unwinding as a function runs.

F2.04.2

Tail calls & accumulators

Rewrite with an accumulator so the work happens on the way down and the stack stays flat.

F2.04.3

Recursion patterns

sum, length, reverse, map, and filter written recursively — and why each one is a fold.

Worked example

The recursion the tracer ran, in full. Two clauses: the base case answers the empty list; the recursive case peels off the head and adds it to the sum of the tail.

# sum a list by recursion — two clauses
def sum([]),        do: 0                 # base case
def sum([h | t]),   do: h + sum(t)         # recursive case

sum([1, 2, 3, 4])
# 1 + sum([2, 3, 4])
# 1 + (2 + sum([3, 4]))
# 1 + (2 + (3 + (4 + sum([]))))
# 1 + (2 + (3 + (4 + 0)))  =>  10

Each line of the unwinding is one frame returning. The page ahead shows how to do the same work without holding all those frames at once.