Repetition without loops
Look through the core of R7RS for a while or for statement and you will not find one. (There is a do form, which this lesson covers, but it is defined in terms of something simpler.) Scheme expresses repetition with a procedure that calls itself: recursion.
In many languages that would be a poor idea. Each call uses a slot on the call stack, and a loop of a million iterations written as recursion would use a million slots and crash. Scheme avoids this with a guarantee written into its standard: a call in tail position, a call whose result is simply returned, does not use any additional stack. A procedure that calls itself in tail position runs in constant space, exactly like a loop. Recursion in Scheme is looping.
That guarantee, called proper tail recursion, is one of Scheme's most important ideas. Guy Steele argued in a 1977 MIT memo that a procedure call in tail position can be compiled as a simple jump with arguments, which made the case that procedure calls need not be expensive. Since then the idea has spread: several functional languages guarantee it, and some compilers for other languages perform it as an optimisation, but Scheme was the first widely known language to require it of every implementation.
Processes, tail position and the guarantee
Definition— Recursive process
A computation in which work is deferred: each call must wait for an inner call to finish and then do something with its result. The amount of pending work, and so the memory used, grows with the input.
Definition— Iterative process
A computation whose entire state fits in a fixed number of variables, carried from one step to the next as arguments. Nothing is deferred; each call simply hands over to the next.
Definition— Tail position
An expression is in tail position if its value is returned directly as the value of the enclosing procedure, with nothing left to do afterwards. In (if test a b) both a and b are in tail position if the if is; so is the last expression of a lambda body, let body, cond clause, when, and or or.
Definition— Proper tail recursion
R7RS requires that an implementation support an unbounded number of active tail calls in bounded space. In practice: a tail call replaces the current call instead of stacking on top of it.
Both kinds of process can come from recursive procedures. The distinction is in what the procedure leaves behind:
(import (scheme base) (scheme write))
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
(define (factorial-iter n)
(define (loop i acc)
(if (> i n)
acc
(loop (+ i 1) (* acc i))))
(loop 1 1))
(write (factorial 20)) (newline)
(write (factorial-iter 20)) (newline)
(write (= (factorial 200) (factorial-iter 200))) (newline)
(define (count-up-to n)
(let loop ((i 0) (total 0))
(if (> i n)
total
(loop (+ i 1) (+ total i)))))
(write (count-up-to 1000000)) (newline)
(write (count-up-to 10000000)) (newline)2432902008176640000
2432902008176640000
#t
500000500000
50000005000000In factorial, the recursive call sits inside (* n ...): after it returns, a multiplication is still pending. Evaluating (factorial 4) builds up a chain of deferred work:
(factorial 4)
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 (* 1 (factorial 0)))))
(* 4 (* 3 (* 2 (* 1 1))))
24In factorial-iter, the call (loop (+ i 1) (* acc i)) is in tail position: its result is the result. The state is entirely in i and acc:
(loop 1 1) → (loop 2 1) → (loop 3 2) → (loop 4 6) → (loop 5 24) → 24The extra parameter acc, an accumulator, carries the partial result forward instead of leaving work behind. count-up-to adds ten million numbers with the same technique and the same constant memory as a for loop in C.
Here is what happens to a recursive process when it gets deep. This program sums the numbers from n down to 1 with the multiplication-style pattern:
(define (sum-to n) (if (= n 0) 0 (+ n (sum-to (- n 1)))))
(write (sum-to 100000)) (newline)
(write (sum-to 1000000)) (newline)5000050000
ERROR: out of stack spaceA hundred thousand pending additions fit; a million exceed Chibi-Scheme's stack limit. Other implementations draw the line in different places (some grow the stack until memory runs out), but none can make the pending work disappear. The tail-recursive version never has any.
Named let, do, and recursion over numbers
Writing a separate helper for every loop gets tedious, so Scheme offers named let: a let with a name that becomes a local procedure you can call in tail position to go round again. It is the most common way to write a loop in Scheme. R7RS also provides do, a loop with explicit variables, step expressions and an exit test.
(import (scheme base) (scheme write))
(define (collatz-steps n)
(let loop ((n n) (steps 0))
(cond ((= n 1) steps)
((even? n) (loop (quotient n 2) (+ steps 1)))
(else (loop (+ (* 3 n) 1) (+ steps 1))))))
(write (map collatz-steps '(1 6 7 27 97))) (newline)
(do ((i 1 (+ i 1)))
((> i 5))
(write (list i (* i i) (* i i i)))
(newline))
(write (do ((vec (make-vector 5))
(i 0 (+ i 1)))
((= i 5) vec)
(vector-set! vec i (* i 10))))
(newline)
(define (digits n)
(let loop ((n n) (acc '()))
(if (< n 10)
(cons n acc)
(loop (quotient n 10) (cons (remainder n 10) acc)))))
(write (digits 2026)) (newline)
(write (digits 9876543210123)) (newline)(0 8 16 111 118)
(1 1 1)
(2 4 8)
(3 9 27)
(4 16 64)
(5 25 125)
#(0 10 20 30 40)
(2 0 2 6)
(9 8 7 6 5 4 3 2 1 0 1 2 3)- In
collatz-steps,loopis bound to a procedure of two arguments, initially called withnand0. Eachcondbranch either returns or callsloopin tail position. dotakes a list of(variable init step)specifications, then a list holding the exit test and the result expressions, then a body run for its effects. The firstdoprints a table; the second fills a vector and returns it.dois most natural with mutable data such as vectors; with lists, namedletusually reads better.digitsbuilds a list of digits from the right, usingconsto push each one on the front of the accumulator (lesson 4 explainscons). Because the digits come out in reverse order, pushing them onto the front puts them back in the right order, with no reversal needed.
The cost of different shapes
Recursion also produces processes of other shapes, and their costs differ dramatically.
(import (scheme base) (scheme write))
(define calls 0)
(define (fib n)
(set! calls (+ calls 1))
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
(define (fib-iter n)
(let loop ((a 0) (b 1) (k n))
(if (= k 0)
a
(loop b (+ a b) (- k 1)))))
(write (fib 25)) (display " computed with ") (write calls) (display " calls") (newline)
(write (fib-iter 25)) (newline)
(write (fib-iter 100)) (newline)
(define (fast-expt base n)
(cond ((= n 0) 1)
((even? n) (let ((half (fast-expt base (quotient n 2))))
(* half half)))
(else (* base (fast-expt base (- n 1))))))
(write (fast-expt 3 40)) (newline)
(write (= (fast-expt 7 123) (expt 7 123))) (newline)
(define (my-gcd a b)
(if (= b 0)
a
(my-gcd b (remainder a b))))
(write (list (my-gcd 1071 462) (gcd 1071 462) (lcm 4 6))) (newline)75025 computed with 242785 calls
75025
354224848179261915075
12157665459056928801
#t
(21 21 12)(set! changes the value of an existing variable; here it counts calls. Lesson 5 discusses assignment properly.)
Tree recursion. The naive fib calls itself twice per step, so its calls form a tree. Computing the 25th Fibonacci number took 242,785 calls, and the count grows by a factor of about 1.618 (the golden ratio) for each increase of n by one: the time is exponential in . fib-iter carries the last two values forward and needs only steps, so (fib-iter 100) is instant and, thanks to exact integers, exactly right.
Logarithmic recursion. fast-expt computes by squaring: when is even.
Theorem— Fast exponentiation is logarithmic
(fast-expt b n) performs at most multiplications for .
Proof
Each step that does not return immediately performs exactly one multiplication, so count the steps. Let be the number of halving steps (even ) and the number of decrementing steps (odd ). Halving an even number shortens its binary representation by exactly one digit, while subtracting 1 from an odd number greater than 1 only clears its last digit and keeps its length. A number with binary digits therefore reaches 1 after exactly halvings. After a decrement the number is even (or 0, where the recursion stops), so two decrements are never consecutive, and the sequence of steps ends with the decrement from 1 to 0. Hence , and the total is .
∎
So needs seven multiplications instead of 39. Implementations typically compute exact integer powers in expt with the same idea.
Euclid's algorithm, my-gcd, is tail-recursive and logarithmic in the smaller argument: the remainders shrink at least as fast as the Fibonacci numbers grow, backwards. R7RS provides gcd and lcm directly.
| Procedure | Shape | Time | Space |
|---|---|---|---|
factorial | linear recursive | ||
factorial-iter | linear iterative | ||
fib | tree recursive | exponential | |
fib-iter | linear iterative | ||
fast-expt | logarithmic recursive | ||
my-gcd | logarithmic iterative |
(For exact big integers, each multiplication itself costs more as the numbers grow; the table counts steps.)
Tail calls between procedures
The guarantee covers every tail call, not only a procedure calling itself. Two or more procedures can hand control back and forth forever without growing the stack, which makes state machines very natural to write.
(import (scheme base) (scheme write))
(define (even-count? lst) (if (null? lst) #t (odd-count? (cdr lst))))
(define (odd-count? lst) (if (null? lst) #f (even-count? (cdr lst))))
(write (even-count? (make-list 1000000 'x))) (newline)
(define (green n) (if (= n 0) 'stopped-at-green (amber (- n 1))))
(define (amber n) (if (= n 0) 'stopped-at-amber (red (- n 1))))
(define (red n) (if (= n 0) 'stopped-at-red (green (- n 1))))
(write (list (green 0) (green 1) (green 2) (green 3000001))) (newline)#t
(stopped-at-green stopped-at-amber stopped-at-red stopped-at-amber)even-count? and odd-count? take turns walking a list of a million elements, each a tail call to the other. The three traffic-light procedures cycle through three million transitions. Each state is a procedure, each transition a tail call: no loop variable, no explicit state field, and constant memory. Interpreters, parsers and protocol handlers are often written this way in Scheme.
How to think recursively
Experienced Scheme programmers write recursive procedures almost mechanically, by following a short recipe.
- Find the smallest case and answer it directly. For a number that is usually 0 or 1; for a list, the empty list. This is the base case.
- Make the problem smaller. Decide how to reduce a larger input to a smaller one of the same kind: subtract 1, halve, take the
cdrof a list, look at a subtree. - Trust the recursion. Assume the procedure already works on the smaller input, and ask only: given that answer, how do I build the answer for the whole? This step feels like cheating at first. It is exactly the inductive step of a proof by induction, and it is valid for the same reason.
- Check the shape of the process. If the input can be large and the recursive call is not in tail position, add an accumulator (or a named
let) so the state travels forward instead of piling up.
Applied to "count the digits of a non-negative integer": the smallest case is a number below 10, which has one digit. A larger number becomes smaller by dropping its last digit with quotient. Trusting the recursion, the count for n is one more than the count for (quotient n 10). The input is never large enough (a number with a million digits is unusual) for the deferred additions to matter, so the simple version is fine:
(define (count-digits n)
(if (< n 10)
1
(+ 1 (count-digits (quotient n 10)))))Notice how the recursion follows the structure of the data. A natural number is either small or "a smaller number plus a digit", so the procedure has one case for each. This idea, that the shape of a procedure should mirror the shape of the data it consumes, is the backbone of the design method taught in How to Design Programs (htdp.org), a textbook built on Racket, Scheme's best-known descendant. You will see it again in the next lesson, where lists, whose definition is itself recursive, make it especially clear.
Common mistakes
Misconception
"Recursion is always slower than a loop." A tail call in Scheme compiles to essentially the same jump as a loop. What costs memory is deferred work, not recursion as such. Write an accumulator, and the recursive procedure is a loop.
Misconception
Thinking a call is in tail position because it is the last thing on the line. In (+ 1 (count (cdr lst))) the recursive call is written last, but + still has to add 1 after it returns, so it is not a tail call. Ask: "when this call returns, is there anything left to do?"
Misconception
Forgetting the base case, or a step that reaches it. A recursion must make the problem smaller each time and stop at the smallest case. (collatz-steps 0) never reaches 1, so it loops forever: check that every input you allow is on a path to a base case. Proof by induction (on the size of the input) is the mathematical twin of this reasoning.
Misconception
Believing every tree recursion must be rewritten. Tree recursion is often the clearest way to express a problem (walking a tree, generating combinations). It is only fib's repeated recomputation of the same subproblems that is wasteful; remembering results (memoisation) or carrying state forward fixes it.
Exercises
1. Recursion and proper tail calls
Warm-upHumanIs the recursive call in this procedure a tail call?
(define (len lst)
(if (null? lst)
0
(+ 1 (len (cdr lst)))))
2. Recursion and proper tail calls
CoreComputationalWith the lesson's naive tree-recursive fib, how many times is fib called in total when you evaluate (fib 5), counting the first call?
3. Recursion and proper tail calls
Warm-upComputationalUsing the lesson's digits procedure, what does (write (digits 305)) print?
4. Recursion and proper tail calls
CoreComputationalHow many multiplications does the lesson's fast-expt perform to compute (fast-expt 2 16)?
5. Recursion and proper tail calls
CoreComputationalWhat does this print?
(write (let loop ((i 0) (acc '()))
(if (= i 4)
acc
(loop (+ i 1) (cons i acc)))))
6. Recursion and proper tail calls
Warm-upComputationalWhat is (my-gcd 84 36), using the lesson's Euclid procedure?
7. Recursion and proper tail calls
StretchHumanWhich of the calls to g, h, p and k are in tail position? List their names.
(define (f x)
(cond ((< x 0) (g x))
((= x 0) (+ 1 (h x)))
(else (and (p x) (k x)))))
8. Recursion and proper tail calls
StretchComputationalWhat does this do loop return?
(do ((i 0 (+ i 1))
(s 0 (+ s i)))
((= i 5) s))
Further reading and resources
- R7RS-small, section 3.5: Proper tail recursionThe precise definition of tail position and the guarantee every implementation must meet.
- The Lambda PapersIncludes Steele's 1977 memo arguing that procedure calls can be as cheap as jumps.
- Structure and Interpretation of Computer Programs, section 1.2 · Harold Abelson and Gerald Jay Sussman with Julie SussmanThe classic discussion of the shapes of processes that procedures generate.