Recursion

Three words come up throughout this page, so start with those.

A continuation is the work left to do once the current computation finishes. In (+ 1 (f x)), the moment you call f, the promise to add 1 on the way back is the continuation. Promises take room while they wait.

A tail position is a place where no such promise is left. When a call's result becomes the result of the enclosing expression directly, there is nothing to do on the way back, so the current continuation is handed over instead of a new one being stacked. That is why a recursive call in tail position costs no extra room however long it runs.

A named let is a let with a name written right after it. That name becomes the name you call to run the loop again. Below, that name is loop.

See it run

(let loop ((xs (list 1 2 3 4)) (sum 0))
  (if (null? xs)
      sum
      (loop (cdr xs) (+ sum (car xs)))))

10

null? asks whether a list is empty. It is true for the empty list.

The same loop can be written with do. For each variable, do takes a starting value and the value it becomes next, and then a stopping test with the value to hand back when it stops.

(do ((rest (list 1 2 3 4) (cdr rest))
     (sum 0 (+ sum (car rest))))
    ((null? rest) sum))

10

do settles into the same loop as a named let, so take whichever reads better. Leave out the value after the stopping test and the loop hands nothing back.

Walk through the pattern

1. Find the base case. When xs is empty, the answer already sits in sum.
2. Shrink the remaining work. (cdr xs) removes exactly one item, so every finite proper list reaches the base case.
3. Carry the answer forward. The next accumulator is computed before loop, leaving the recursive call as the final action.

How to reason about it

• Carry accumulators as parameters instead of combining work after the recursive return.
• Tail position survives final if, begin, and/or, cond, case, do, call-with-values, and apply paths.
• Keep the test input small and finite, and distinguish continuation depth from runtime cost.

Check yourself

Add 5 to the input list. What result should the program produce, and does the recursive call remain in tail position?

A common mistake

Tail safety does not make an infinite loop terminate or remove resource budgets.

Keep going

The tail-call manual covers converting a non-tail function and which places stay in tail position. Use the procedure reference when choosing a fold instead.

Proper tail calls · Higher-order procedures