F2.04 · part 3 of 3
Recursion patterns
Write a few recursions over lists and the same shapes keep appearing. Sum, length, reverse, map, and filter all walk the list the same way — and all of them are one idea wearing different clothes: a fold.
Each pattern peels the head, does something with it, and recurses on the tail. The only thing
that changes is what it does with the head and how it starts. That is exactly what
Enum.reduce abstracts: a starting value and a function that folds each element into an
accumulator. F1.07 named this; here every recursion on this page collapses into one. Pick a pattern and see
its recursive form beside its fold.
Five patterns, one fold
The recursive definition on the left and the Enum.reduce on the right compute the
same result. The recursion makes the walk explicit; the fold names the part that varies — the starting
value and the combiner.
Choose a pattern.
- pattern
- a recursion shape that recurs: walk the list, act on the head, recurse on the tail.
- fold
- collapsing a list to a value by combining elements with an accumulator.
- combiner
- the function a fold applies to each element and the accumulator.
- initial value
- what the accumulator starts as — the answer for the empty list.
A recursion and its fold
recursive
as a fold
F1.07 · operators
Sum and product were folds over a function; so is every list walk here.
Elixir
Enum.reduce(list, init, combiner) captures the shape all five share.
Once you see the accumulator and the combiner, every one of these is the same recursion with a different combiner — which is to say, a fold.
Where this goes
That is the whole of F2.04. The shape of a recursion is a base case and a recursive case; tail calls with
an accumulator flatten the stack to constant space; and the recursions that recur are all folds. The next
module makes the fold itself the subject: reduce as the one operation that
map and filter are built from.
Next: F2.05 — map / filter / reduce (folds) — reduce as the universal fold. Back to the F2.04 hub or the F2 overview.