Skip to content
LumenaryAcademy
Foundations 60 min

Recursion and proper tail calls

How Scheme repeats without loop statements, why its tail calls never run out of stack, and how to tell a recursive process from an iterative one.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

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.

DefinitionsH

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:

scheme
(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)
text
2432902008176640000
2432902008176640000
#t
500000500000
50000005000000

In 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:

text
(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))))
24

In 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:

text
(loop 1 1)  →  (loop 2 1)  →  (loop 3 2)  →  (loop 4 6)  →  (loop 5 24)  →  24

The 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:

scheme
(define (sum-to n) (if (= n 0) 0 (+ n (sum-to (- n 1)))))
(write (sum-to 100000)) (newline)
(write (sum-to 1000000)) (newline)
text
5000050000
ERROR: out of stack space

A 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.

Worked examplesH

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.

scheme
(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)
text
(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, loop is bound to a procedure of two arguments, initially called with n and 0. Each cond branch either returns or calls loop in tail position.
  • do takes 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 first do prints a table; the second fills a vector and returns it. do is most natural with mutable data such as vectors; with lists, named let usually reads better.
  • digits builds a list of digits from the right, using cons to push each one on the front of the accumulator (lesson 4 explains cons). Because the digits come out in reverse order, pushing them onto the front puts them back in the right order, with no reversal needed.
ComputationC

The cost of different shapes

Recursion also produces processes of other shapes, and their costs differ dramatically.

scheme
(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)
text
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 nn. fib-iter carries the last two values forward and needs only nn steps, so (fib-iter 100) is instant and, thanks to exact integers, exactly right.

Logarithmic recursion. fast-expt computes bnb^n by squaring: bn=(bn/2)2b^{n} = (b^{n/2})^2 when nn is even.

Theorem— Fast exponentiation is logarithmic

(fast-expt b n) performs at most 2⌊log⁡2n⌋+12\lfloor \log_2 n \rfloor + 1 multiplications for n≥1n \ge 1.

Proof

Each step that does not return immediately performs exactly one multiplication, so count the steps. Let hh be the number of halving steps (even nn) and dd the number of decrementing steps (odd nn). 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 ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 binary digits therefore reaches 1 after exactly h=⌊log⁡2n⌋h = \lfloor \log_2 n \rfloor 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 d≤h+1d \le h + 1, and the total is h+d≤2⌊log⁡2n⌋+1h + d \le 2\lfloor \log_2 n \rfloor + 1.

∎

So 3403^{40} 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.

ProcedureShapeTimeSpace
factoriallinear recursiveO(n)O(n)O(n)O(n)
factorial-iterlinear iterativeO(n)O(n)O(1)O(1)
fibtree recursiveexponentialO(n)O(n)
fib-iterlinear iterativeO(n)O(n)O(1)O(1)
fast-exptlogarithmic recursiveO(log⁡n)O(\log n)O(log⁡n)O(\log n)
my-gcdlogarithmic iterativeO(log⁡n)O(\log n)O(1)O(1)

(For exact big integers, each multiplication itself costs more as the numbers grow; the table counts steps.)

Worked examplesH

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.

scheme
(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)
text
#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.

ExplanationH

How to think recursively

Experienced Scheme programmers write recursive procedures almost mechanically, by following a short recipe.

  1. 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.
  2. Make the problem smaller. Decide how to reduce a larger input to a smaller one of the same kind: subtract 1, halve, take the cdr of a list, look at a subtree.
  3. 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.
  4. 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:

scheme
(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 misconceptionsH

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

Exercises

1. Recursion and proper tail calls

Warm-upHuman

Is the recursive call in this procedure a tail call?

(define (len lst)
  (if (null? lst)
      0
      (+ 1 (len (cdr lst)))))
Choose one

2. Recursion and proper tail calls

CoreComputational

With 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-upComputational

Using the lesson's digits procedure, what does (write (digits 305)) print?

4. Recursion and proper tail calls

CoreComputational

How many multiplications does the lesson's fast-expt perform to compute (fast-expt 2 16)?

5. Recursion and proper tail calls

CoreComputational

What 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-upComputational

What is (my-gcd 84 36), using the lesson's Euclid procedure?

7. Recursion and proper tail calls

StretchHuman

Which 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)))))

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

8. Recursion and proper tail calls

StretchComputational

What does this do loop return?

(do ((i 0 (+ i 1))
     (s 0 (+ s i)))
    ((= i 5) s))

Further reading and resources