Skip to main content

Tail Calls and Iteration as Disguised Recursion

What This Concept Is​

A tail call is a procedure call whose result is immediately returned by the caller -- there is no pending work after it. In

(define (loop n)
  (if (= n 0) 'done (loop (- n 1))))

the call (loop (- n 1)) is in tail position: whatever it returns, loop returns. Contrast with

(define (factorial n)
  (if (= n 0) 1 (* n (factorial (- n 1)))))

-- the recursive call is not in tail position: its result must be multiplied by n before returning.

A language implementation that performs tail-call optimization (TCO) reuses the current stack frame for a tail call rather than pushing a new one. In Scheme, TCO is mandatory (R5RS and beyond). That single guarantee is why SICP can say, in §1.2, that every iterative process you would write with a while loop in C is expressible as a tail-recursive procedure -- and will run in constant space.

SICP distinguishes recursive procedure (the source text calls itself) from recursive process (the runtime actually grows a call chain). A tail-recursive procedure generates an iterative process; a non-tail-recursive procedure generates a recursive process.

Why It Matters Here​

  • Language design lens. Scheme chooses to make loops a library rather than a primitive (do, named let are macros). That choice is paid for by mandatory TCO.
  • Interpreter design (Concepts 10-12). SICP's explicit-control evaluator (§5.4.2) is careful about tail recursion: the evaluator itself must not grow its state for tail calls, or it would impose a stack limit on interpreted programs.
  • Portability of code. A C programmer who writes while and a Scheme programmer who writes tail-recursion are doing the same thing; neither runs out of stack. A Python or Java programmer writing naive recursion will -- those languages do not guarantee TCO.

A working mental model of tail calls is also the single best preparation for Concept 10: the evaluator's apply is almost always in tail position.

Concrete Example​

Iterative factorial as tail recursion (SICP §1.2.1):

(define (fact n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max)
  (if (> counter max)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max)))

fact-iter is tail-recursive. In Scheme, (fact 10000) runs in constant space.

Contrast with the recursive process:

(define (fact2 n)
  (if (= n 0) 1 (* n (fact2 (- n 1)))))

fact2 is structurally recursive but the process is linearly recursive: the call chain grows with n, because each caller is waiting to multiply.

Python does not guarantee TCO, so the equivalent blows up:

import sys; sys.setrecursionlimit(10**6)
def fact_iter(p, c, m):
    if c > m: return p
    return fact_iter(p * c, c + 1, m)   # crashes for big m

The Pythonic equivalent is a loop:

def fact(n):
    p = 1
    for i in range(1, n + 1):
        p *= i
    return p

This is the Scheme claim reversed: in Python, loops are idiomatic and tail calls are not the story.

C also lacks guaranteed TCO, though many compilers will apply it at -O2 when the tail call is visible. Never rely on it for correctness.

Common Confusion / Misconception​

  1. "Tail-recursive" = "fast." No -- it is about space. A recursive process can be identical in time complexity to an iterative process; the cost it pays is stack frames.
  2. "Last call is tail call." The syntactically last expression is not always in tail position. (lambda () (+ 1 (f x))) has f x in a non-tail position -- the + is still waiting.
  3. "All Schemes optimize tail calls equally." Standard Scheme requires TCO on every tail call; many other languages optimize only some cases (Scala self-tail-calls, for example) or none (CPython).
  4. Mutual recursion still counts. (a -> b -> a -> …) is properly tail-recursive if each call is in tail position -- TCO applies to tail calls whether or not they are self-calls. This is why state-machine style encodings of automata can be written as groups of tail-recursive procedures.

How To Use It​

  • In Scheme, Racket, OCaml, and the ML family: write loops as tail-recursive procedures; do not worry about stack.
  • In Python, Java, C#: use loops for long iteration; if the algorithm is naturally recursive and depth can grow, rewrite to iterative or use an explicit stack.
  • In C: write loops; rely on TCO only when the call target is statically visible and you have profiled.
  • When writing an interpreter: evaluate the last expression of a begin in the caller's continuation, so that a user program's tail call becomes a tail call in your own evaluator.

Check Yourself​

  1. Classify each as tail or non-tail position: (a) (if p (f x) (g x)) (b) (let ((v (f x))) v) (c) (+ 1 (f x)) (d) (begin (log x) (f x))
  2. Why does factorial as written in SICP §1.2 not run in constant space?
  3. In what sense are while and tail recursion the same thing?

Mini Drill or Application​

Write sum-list both ways in Scheme:

  • (define (sum-list xs) (if (null? xs) 0 (+ (car xs) (sum-list (cdr xs))))) -- recursive process
  • (define (sum-list xs) (helper xs 0)) with helper tail-recursive

Run both on a long list and describe, in one line each, the space they use. Then write the Python equivalent and explain why the tail-recursive Python version is not safe for long lists.

Read This Only If Stuck​