Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 38 ยท Continuations and Tail Calls

Accumulators and Trampolines

Turn non-tail recursion into tail recursion with accumulators, see how reverse fixes list building, and learn trampolines for languages without tail-call support.

Most recursion you first write is not tail recursive: you compute the answer of the smaller problem, then combine it with something. To use the constant-space loop from the previous lesson, you can often add an extra parameter, an accumulator, that carries the partial result down the calls. When the base case is reached, the accumulator already holds the answer.

This lesson shows the accumulator technique on numbers and lists, explains why accumulated lists come out reversed, and then introduces the trampoline, a trick to get the same safety in a language that has no tail-call guarantee.

From pending work to an accumulator

Take factorial. The textbook version waits for the recursive result before multiplying:

RACKET
(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

The pending work is "multiply by n". Instead of leaving it for later, do it now and pass the product along:

RACKET
(define (fact n)
  (let loop ([n n] [acc 1])
    (if (= n 0)
        acc
        (loop (- n 1) (* acc n)))))

(fact 5) ; => 120

The recipe is always the same: (1) find the work that happens after the recursive call; (2) make it a parameter; (3) return the accumulator in the base case; (4) start it with the identity of the operation (0 for +, 1 for *, '() for list building). Racket's integers are arbitrary precision, so (fact 1000) works and stays stack-safe.

Because multiplication of whole numbers is associative, order does not matter. For operations where order matters, such as subtraction, check that the accumulator version computes the same thing before you switch.

Building lists: the reversed result

With lists the accumulator has a twist. cons adds to the front, so the last element processed ends up first:

RACKET
(define (my-map f lst)
  (let loop ([rest lst] [acc '()])
    (if (null? rest)
        (reverse acc)
        (loop (cdr rest) (cons (f (car rest)) acc)))))

The final reverse restores the order. It costs one extra pass, which is still linear. Racket's own map handles long lists safely without you thinking about it (the implementation is free to use stack or heap), but the accumulate-then-reverse pattern is everywhere in Scheme code you will read.

The stand-in below models the pattern with JavaScript arrays and shows the reversed intermediate result:

JS Stand-in: accumulate, then reverse

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The accumulator has a cost: clarity

Accumulator versions are less readable than the direct definition. Experienced Schemers write the direct version when the data is small and shallow, and the accumulator version when inputs may be huge. Structural recursion on a tree is usually written directly, because the depth of a balanced tree is small, even if the tree has millions of nodes.

Trampolines: tail calls without language support

Suppose you are working in a language such as JavaScript that does not guarantee tail calls, but you want the same style. A trampoline moves the "jump" out of the language and into a small driver loop:

  1. Instead of making the recursive call, the function returns a thunk, a zero-argument function describing the next step.
  2. A driver, the trampoline, keeps calling the returned thunk until it gets something that is not a function.

The stack never grows beyond one step, because each step returns before the next begins. In JavaScript:

JS Stand-in: a trampoline

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Now isEven(100000) takes 100,000 bounces and returns true without any stack growth. The price is speed: allocating a thunk per step is slower than a real jump. Scheme systems get the same effect for free, and some compilers that target languages without tail calls (for example, Scheme-to-JavaScript compilers) use exactly this trick internally.

sequenceDiagram
  participant D as Driver loop
  participant F as isEven / isOdd
  D->>F: isEven(3)
  F-->>D: Bounce(isOdd 2)
  D->>F: run thunk
  F-->>D: Bounce(isEven 1)
  D->>F: run thunk
  F-->>D: Bounce(isOdd 0)
  D->>F: run thunk
  F-->>D: false

Each call returns before the next starts, so the stack stays flat.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What should the accumulator start with when you convert a +-based recursion?

    The accumulator starts with the identity of the combining operation: 0 for addition, 1 for multiplication, the empty list for cons.
  2. 2. Why does accumulating a list with cons usually need a final reverse?

    Each cons places the newest element at the front, so the first element processed ends up last. reverse restores the original order.
  3. 3. What does a trampoline's driver loop do?

    The function returns a description of the next step instead of making a nested call; the driver runs those steps one after another in a flat loop.
  4. 4. When is a trampoline needed in Racket?

    Racket makes proper tail calls itself. Trampolines are for hosts such as JavaScript that lack the guarantee.

Summary

  • An accumulator parameter turns pending work into an argument so the recursive call becomes a tail call.
  • Start it with the identity value of the operation and return it in the base case.
  • Accumulating with cons builds the list backwards, so finish with reverse.
  • A trampoline returns thunks and lets a driver loop run them, giving stack-safe recursion in languages without tail calls.
  • In Racket you rarely need trampolines; the guarantee is built in.

Next: call/cc and Escapes