You can turn recursive list processing into a loop by moving work before the next call. This page shows how to identify a tail call and which expressions preserve that position.
Run each complete example in the Playground. For a first walkthrough of named let, start with the recursion guide.
Compare two ways to sum a list
This procedure adds the first item after the recursive call returns.
(define (sum-list xs)
(if (null? xs)
0
(+ (car xs) (sum-list (cdr xs)))))
(sum-list (list 1 2 3))Result
6The call for (1 2 3) waits for the sum of (2 3), then adds 1. The next call waits for the sum of (3), then adds 2. These pending additions accumulate as the list grows.
Move the addition into an argument to perform it before the next call.
(define (sum-list xs)
(let loop ((rest xs) (sum 0))
(if (null? rest)
sum
(loop (cdr rest) (+ sum (car rest))))))
(sum-list (list 1 2 3))Result
6Here, sum is an accumulator, a parameter holding the total so far. Each call computes the next total before calling loop. It returns the result of loop directly.
A call whose result becomes the calling procedure's result directly is in tail position. Lispex reuses the current continuation, the work remaining after that procedure returns. It does not add another pending call for each tail call. This behavior is called proper tail calls.
Repeat ten thousand times
(let loop ((n 10000) (acc 0))
(if (= n 0)
acc
(loop (- n 1) (+ acc 1))))Result
10000Each call decreases n and increases acc. The next call is the last action in the selected if branch. Ten thousand iterations keep the depth of pending calls constant.
The same rule applies to mutual recursion, where procedures call each other.
(letrec ((even-count? (lambda (n)
(if (= n 0) #t (odd-count? (- n 1)))))
(odd-count? (lambda (n)
(if (= n 0) #f (even-count? (- n 1))))))
(even-count? 10000))Result
#tEach procedure returns the other's result directly. Alternating between them preserves the tail calls.
Locate tail positions
Start with the last expression in a procedure body. When a form is itself in tail position, the following parts preserve that position.
| Form | Tail position |
|---|---|
let, let*, letrec, begin | Last expression in the body |
if | Either result branch |
cond, case | Last expression in the selected clause |
and, or | Last operand |
when, unless | Last expression in the body that runs |
do | Recursive step and last result expression |
(apply proc args) | Call to proc |
(call-with-values producer consumer) | Call to consumer |
Tests and call arguments are evaluated before their results can be used. Those positions are not tail positions.
| Expression in a procedure's tail position | Is the call to loop a tail call? |
|---|---|
(if done? answer (loop next)) | Yes. Its result is returned directly. |
(begin (display x) (loop next)) | Yes. It is the last expression. |
(+ x (loop next)) | No. The addition still needs its result. |
(map loop items) | No. map collects the results of its calls to loop. |
(apply loop args) | Yes. apply preserves the tail position. |
For call-with-values, the producer runs before the consumer. Only the consumer call inherits the tail position.
Account for resource limits
Tail calls keep pending call depth constant. The program still spends work on each iteration and may allocate data.
The selected resource profile, a set of execution limits, still applies. Non-tail recursion can reach a depth limit. A tail-recursive loop can reach another limit, such as its work budget.
For the same stated execution conditions, resource limits produce repeatable results. Resource-fault records identify the executor, profile values, and threshold reached. See determinism and resources.