Recursion, and the stack
A function that calls itself on a smaller problem, the stopping case that ends the walk, and why one shape of recursion runs out of room.
The same function, on a smaller problem
A recursive function calls itself on something smaller. Counting down from five means counting down from four, which means counting down from three, until the smallest case answers straight away. The trick is not the call; it is trusting that the smaller problem is already solved. That trust is not blind: if the smaller call is correct and the step from it is correct, the whole answer is correct, and the base case is where the argument starts.
Every recursion starts with one question: is this the smallest case? If it is, answer now. If it is not, do one step and hand the rest to the same function. Leave that question out and the function calls itself forever.
The answer travels back up
In (fact (dec n)) the inner call has to answer before the multiplication can happen. Each call waits for the next, and its place in the line is held on the stack. Nothing is wrong with that until the walk gets deep, and then the waiting frames run out of room and the program stops with a stack overflow. Each waiting frame holds the arguments of that call and the place to resume, so the depth of the walk becomes the amount of memory it needs.
The cure is the same idea as recur: make the call the last thing the function does, and hand the running total along as an argument so that nothing is left waiting. It is the same algorithm with the waiting taken out. The accumulator is the part of the answer already known, passed forward so the return path has nothing to add.
Lists and recursion are built for each other
A list is either empty or one value followed by a smaller list, which is exactly the question a recursion asks: answer something for the empty list, otherwise use the first value and ask the same thing about the rest. The empty list is the smallest case, and the pair is the step: first for the value, rest for the smaller problem.
The shape is short enough to remember. Empty case, one step, same question on what is left — and the same three lines solve a surprising amount of real work.
The smaller problem has to be smaller
A recursion ends because each call gets a strictly smaller problem. (dec n) and (rest xs) both make progress; (identity xs) does not, and the function calls itself forever. The stopping test and the smaller step are two halves of the same promise. A recursion that shrinks but never reaches the base case is just as broken as one that never shrinks: the measure has to move toward the case you wrote.
For a list, the measure is length: rest removes one item. For a number, it might be the value, the count of digits, or a quotient. Decide what is shrinking before you write the call, and the base case becomes obvious.
The stack is a place where answers wait
When a function calls itself and still has work to do afterwards, the call cannot finish until the inner one answers. The runtime keeps each unfinished call in a frame, and the frames stack up. That is fine for a handful and fatal for a million. The limit is not a rule of the language but the size of the stack the runtime gave the program, which is why the same function may work for ten thousand items and fail for fifty thousand.
A tail call has no work left afterwards, so the frame does not need to wait. recur makes that explicit and reuses the frame; a plain recursive call in tail position is not automatically optimised in Clojure, so write recur when you mean it.
A walk, a count, and the version that does not wait
(defn fact [n]
(if (zero? n)
1
(* n (fact (dec n)))))
(defn total [xs]
(if (empty? xs)
0
(+ (first xs) (total (rest xs)))))
(defn total-now [xs sum]
(if (empty? xs)
sum
(recur (rest xs) (+ sum (first xs)))))
(println (fact 5))
(println (total [1 2 3 4]))
(println (total-now [1 2 3 4] 0))Down to the smallest case, and back up
Run it and read the four numbers. Then write a `count-up` that prints 1 to 5 by counting up with `recur`, and a `product` that multiplies a list of numbers.
Push a plain recursion deep enough, tens of thousands of passes, and the waiting frames run out: the program ends with a stack overflow rather than an answer. When a walk can carry its running total in an argument, write it with recur — same answer, no waiting.
Three ways a recursion goes wrong. A missing base case calls forever; a base case that the argument never reaches does the same. A recursive call that does not shrink its argument, such as (total xs) instead of (total (rest xs)), also never ends. And a stopping test written for the wrong shape — (empty? n) when n is a number — throws instead of ending the walk.
Try these next
- Write a recursive countdown that prints a number and then calls itself with one less.
- Write a recursive sum over a vector, then a tail version that carries the total.
- Write a recursive function that counts the items in a vector without using
count.
Adding the digits of a number
Run it and check that both versions agree. Then write a `count-digits` that answers how many digits a number has, first the waiting way, then with `recur`.
Check what you learned
One question at a time. A wrong answer explains itself — take another go.
Part 1 of 5
What happens if a recursive function has no stopping case?