Recursion instead of loops

The same function, on a smaller problem

A recursive function calls itself, but on something smaller than what it was given. Counting down from five means counting down from four, which means counting down from three, and so on until the work is trivial. The trick is not the calling — it is trusting that the smaller problem is already solved.

Every recursion has one question at the top: is this the smallest case? If it is, answer straight away and stop. If it is not, do one step of work and hand the rest to the same function. Leave that question out and the function calls itself forever.

Three lines that walk any list

Lists and recursion are a perfect pair, because a list is either empty or it is one value followed by a smaller list. That is the whole shape of a walk: answer 0 for the empty list, otherwise use the first value and ask the same question about the rest.

Notice that the answer comes back through the call: the sum of a list is its first value plus the sum of the rest. Nothing is stored along the way — each call waits for the answer of the next one, and the additions happen on the way back up.

The calls that are still waiting

When (total xs) calls itself, the outer call cannot finish until the inner one answers. Each waiting call keeps its own xs and its own place in the addition, and the pile of them is the call stack.

That is why the additions happen on the way back up. The deepest call answers 0, the next adds the last value, and the answer travels outward one step at a time. Printing inside the function shows the descent; the final value shows the ascent.

A tail call is different: if the recursive call is the last thing the function does, nothing is left waiting. The next chapter uses that shape for loops, and it is why a loop can run far longer than a deep recursion.

Trust the smaller answer

The mental move in recursion is to assume the call on the smaller value already works. You do not trace every level; you check the stopping case and check that one step plus the smaller answer gives the right whole.

For total, the claim is: the sum of a list is its first value plus the sum of the rest. If the rest is handled correctly, the whole is correct, and the empty list is the one case you check by hand.

That is also how to debug one. Print the argument at the top of the function and see whether it is shrinking toward the stopping case; if it is not, the recursive call is passing the wrong value.

Two walks, one shape

(define (sum xs)
  (if (null? xs)
      0
      (+ (car xs) (sum (cdr xs)))))

(define (found? x xs)
  (cond ((null? xs) #f)
        ((equal? x (car xs)) #t)
        (else (found? x (cdr xs)))))

(print (sum (list 1 2 3 4 5)))
(print (sum (list)))

(print (found? 3 (list 1 2 3)))
(print (found? 9 (list 1 2 3)))

The base case is the whole proof

A recursion is correct when two things hold: the base case answers correctly for the smallest input, and each step turns a correct answer for the smaller input into a correct answer for the whole. That is a proof by induction, and it is also a practical checklist. Test the base case by hand, then test one step.

Most broken recursions fail the second condition rather than the first. The base case is usually obvious; the step is where the argument stops shrinking, or where the combination is wrong. Printing the argument at the top shows which.

Depth has a cost

Every waiting call holds a frame, and the frames add up. A recursion a hundred thousand levels deep can exhaust the stack even when the logic is right. The named let in the next chapter avoids the pile by making the recursive call the last thing the body does.

Try these next

• Write (define (count xs) ...) that answers how many values a list holds.
• Write (define (sum-squares xs) ...) using (* (car xs) (car xs)).
• Add a display of the argument at the top of factorial and watch the descent.