Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 38 ยท Continuations and Tail Calls

Tail Calls and Loops

Learn tail position, proper tail calls, named let and why Scheme and Racket have no loop keyword. Includes runnable JavaScript stand-ins that show the stack problem.

Scheme and Racket have no while statement and no for loop in the core language. That surprises people who know C or Java. The reason is a guarantee in the language definition: a call in tail position does not grow the stack. Because of that guarantee, a function that calls itself in tail position is exactly as cheap as a loop, so the language does not need a separate loop construct.

In this lesson you will learn what tail position means, how to write loops as tail calls, how named let packages the pattern, and what happens in a language without the guarantee. Earlier chapters covered recursion on lists; here we make it safe for huge inputs. The next lesson, Accumulators and Trampolines, turns ordinary recursion into tail form.

Racket and Scheme cannot run in our editor. The Racket code below is shown read-only, and I only print its output where it is certain. The runnable blocks are JavaScript stand-ins that model the same ideas, and they are labelled as such.

What is tail position?

A call is in tail position when nothing is left to do after it returns: its result becomes the result of the whole function. Compare two ways to add up the numbers from 1 to n:

RACKET
;; NOT a tail call: after (sum-to (- n 1)) returns, we still add n
(define (sum-to n)
  (if (= n 0)
      0
      (+ n (sum-to (- n 1)))))

;; Tail call: the recursive call is the last thing that happens
(define (sum-to/acc n acc)
  (if (= n 0)
      acc
      (sum-to/acc (- n 1) (+ acc n))))

In the first version each call must wait for the one below it, so the pending additions pile up on the stack. In the second, the call to sum-to/acc is the whole answer of the branch, so the runtime can reuse the current frame. (sum-to/acc 1000000 0) runs in constant stack space and returns 500000500000.

Which positions count as tail positions? In if, both branches (not the test). In cond, the last expression of each clause. In let, begin, when and unless, the last body expression. In and and or, the last operand. Arguments to a function are never in tail position.

Why this matters

Without the guarantee, deep recursion crashes with a stack overflow. Languages like JavaScript (in most engines) and Python behave that way. This stand-in computes the sum recursively and with a loop, and catches the overflow:

JS Stand-in: recursion vs a loop in JavaScript

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

No output.

The loop is fine; the recursion blows the stack. A Scheme programmer gets the loop's behavior while writing the recursive shape, because a proper tail call is a jump with new argument values, not a new stack frame.

Named let: the idiomatic loop

Writing a helper with an accumulator parameter every time is tedious. Racket and Scheme offer named let, which defines a local function and calls it once with the initial values:

RACKET
(define (sum-to n)
  (let loop ([i n] [acc 0])
    (if (= i 0)
        acc
        (loop (- i 1) (+ acc i)))))

Read it as: "start loop with i = n and acc = 0; to continue, call loop again with new values." The name loop is just a convention. Each call to loop in tail position is a jump back to the top, so this is a real loop with no stack growth.

Racket also provides for forms (for/sum, for/list, for/fold) for the common cases, which you will meet later. Under the hood they expand into loops like this one, using macros (Syntax-rules Macros shows how).

Here is a stand-in that imitates named let: a small function namedLet repeatedly applies a step function, which either returns {done: value} or {next: [args]}.

JS Stand-in: a named let as repeated jumps

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

No output.

Mutual recursion and general tail calls

The guarantee covers every tail call, not only self-calls. Two functions can hand control back and forth forever without growing the stack:

RACKET
(define (my-even? n)
  (if (= n 0) #t (my-odd? (- n 1))))

(define (my-odd? n)
  (if (= n 0) #f (my-even? (- n 1))))

(my-even? 1000000) ; => #t, in constant space

This is why state machines are pleasant in Scheme: each state is a function and each transition is a tail call. A parser, a protocol handler, or a game loop can be written as a set of mutually tail-calling functions.

flowchart LR
  A["my-even? n"] -->|"tail call (- n 1)"| B["my-odd? n"]
  B -->|"tail call (- n 1)"| A
  A -->|"n = 0"| T["#t"]
  B -->|"n = 0"| F["#f"]

Each arrow is a jump, not a nested call.

Common mistakes

  • Doing work after the call. (+ 1 (loop ...)) and (cons x (loop ...)) are not tail calls. You can often fix them with an accumulator (next lesson).
  • Tail position inside with-handlers or dynamic-wind. A body wrapped in an exception handler is not in tail position, because the handler must be removed afterwards.
  • Assuming other languages behave the same. Racket and Scheme guarantee it (the Scheme standards require it). JavaScript, Python and Java do not.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In (if test (f x) (g y)), which parts are in tail position?

    Both branches of an if inherit the tail position of the if. The test is never a tail position because the branch still has to run after it.
  2. 2. Why does (+ n (sum-to (- n 1))) risk exhausting memory for huge n?

    The addition happens after the recursive call returns, so every level must be remembered until the base case is reached.
  3. 3. What does named let (let loop ([i 0]) ...) do?

    Named let is shorthand for a local recursive function plus one initial call. Calls to loop in tail position behave like jumps.
  4. 4. Which language guarantees proper tail calls?

    The Scheme standards require proper tail calls, and Racket follows that. Many other languages leave it to the optimizer or do not support it.

Summary

  • A call is in tail position when its result is the function's result and nothing remains to do.
  • Scheme and Racket run tail calls in constant stack space, so loops are written as tail recursion.
  • Named let is the standard idiom for a local loop.
  • Mutual tail calls give you state machines without stack growth.
  • Work after the call (+, cons, with-handlers) breaks tail position.

Next: Accumulators and Trampolines