LetItCrash

Recursion: the pattern that calls itself

LLM-authored, human-reviewed

Foundations

A recursive function calls itself. It sounds paradoxical. In practice, it is one of the most useful shapes in programming. The recursion exercises on this site use it, and so does everything around them: map and filter from the refactoring exercises are recursion with familiar names, the lambda calculus’s self-application is recursion stripped to its bones, and induction - the subject of its own article - proves recursion correct. This article focuses on the shape: what a recursive function is, how it runs, and why it terminates.

The shape: a base case and a step

Every recursive function has two parts. They are always the same two parts:

def sum([]), do: 0
def sum([head | tail]), do: head + sum(tail)

The first clause is the base case: what to do at the smallest input, where no recursive call is needed. The sum of no elements is 0, so this clause returns it directly. The second clause is the recursive step: how to reduce the problem to a smaller one. Summing a non-empty list means adding the head to the sum of the tail - a smaller list.

The reduction is the whole point. A correct recursive function does three things: it has a base case, it recurses on a smaller input, and the step combines the smaller answer into the full answer. Miss the base case and the function recurses forever. Recurse on an input of the same size and it makes no progress. Combine the results incorrectly and the answer is wrong. The language, data structure, and problem all sit on that skeleton.

The call stack you can’t see

When sum([1, 2, 3]) runs, the second clause calls sum([2, 3]), which calls sum([3]), which calls sum([]). Four invocations of sum are waiting at that point. Each has computed its head, called itself, and paused until the inner call returns. The sum([]) call reaches the base case and returns 0. The stack then unwinds in reverse: sum([3]) computes 3 + 0 = 3, sum([2, 3]) computes 2 + 3 = 5, and sum([1, 2, 3]) computes 1 + 5 = 6.

The work happens twice, in opposite directions. The way down chooses the sub-problems; the way back combines their answers. Most recursion mistakes occur in one of those halves. The trace exercises on this site make the stack visible: you predict each next call and what each call returns on the way up. The function “Build a new list with map” and its siblings in the refactoring exercises are recursion in disguise. The trace exercises show the recursion underneath.

The same four calls drawn twice: on the left, the stack growing as sum calls itself; on the right, the stack shrinking as each call returns its answer - the way down and the way back.

Termination is descent

Why does sum finish? Every recursive call uses a strictly smaller list. The tail has one fewer element than the whole list, and a list can be peeled only so many times before it reaches [] and the base case. Termination is not an extra feature; it follows from recursing on smaller inputs. When a function recurses without descending - factorial(n - 1) with no base at 0, or a call on the same argument - it runs forever because nothing brings it to a base case.

The recursion exercises make the descent explicit. list_length/1 peels the head and adds one to the length of the tail. member/2 peels the head and asks the tail, with a decision: if the head is the thing we seek, return true; otherwise keep peeling. reverse/1 is the interesting one - it descends to the empty list and builds the answer entirely on the way back:

def reverse([]), do: []
def reverse([head | tail]), do: reverse(tail) ++ [head]

Reversing [1, 2, 3] descends to [], then the way back appends heads in reverse order: [3], then [3, 2], then [3, 2, 1]. The skeleton stays the same, but the base case does the real work and the step combines results on the way up. Identify which half does the work - the way down, the way back, or both. That is the skill the harder recursion exercises teach.

Structural recursion: following the shape of the data

The recursion above follows the shape of a list. A list is either empty or a head and a tail. Those are exactly the two clauses. The pattern match [head | tail] and the empty pattern [] are not arbitrary choices; they are the list’s anatomy, and the recursion walks through it. This is structural recursion. It makes the exercises feel inevitable: there is one obvious recursive function for “add up the elements” because the list has one obvious anatomy. The induction article proves why this works for every list. Here, the key point is simpler: the shape of the data dictates the shape of the code.

Mutual recursion: two functions trading calls

Most recursion is one function calling itself. The exercises also use the two-function form: each function calls the other, and each carries its own base case.

def is_even(0), do: true
def is_even(n), do: is_odd(n - 1)

def is_odd(0), do: false
def is_odd(n), do: is_even(n - 1)

is_even does not reach a base case on its own for odd numbers; it hands off to is_odd, which hands back, until one base case fires. It is the same descent as before, spread across two functions. The reasoning is unchanged: each call shrinks the input, so the pair terminates. The trace drills show this shape with functions like isEven and isOdd calling each other.

The higher-order functions are recursion with names

The refactoring exercises taught you that loops become map, filter, reduce, and friends. The recursion exercises show that these functions are recursive too. map means “apply the callback to the head, map the tail” with the empty list as its base case, and reduce uses the same skeleton with an accumulator. When you write a.map(x => x * 2), you are writing recursion with the recursive function already written and named. The two practices teach the same skill from opposite ends: refactoring says “your loop has a name”; recursion says “here is what the name runs”.

Why this matters here

Recursion is the substrate of this site. The higher-order functions from the refactoring exercises are recursion. The lambda calculus’s self-application - (\x. x x)(\x. x x) - is recursion with nothing else left, and the fixed-point exercises there are recursive definitions run. Induction proves that recursion is correct. Elixir, the language the site teaches, is built on it: the Enum functions are recursion, the pattern matching the recursion exercises use is how Elixir expresses the base-case/step skeleton, and learning to write sum/1 by hand teaches you how the functions you call every day actually work. Read the recursion article’s sibling on induction for the proof side of the same shape: the base case, the step, and the guarantee that covers every input.

Where to go next

Related exercises

← Back to articles

Exercises