Most programming languages have special syntax to express iteration. For example, C and C++ have the keywords for, while, and do. In contrast, Scheme allows iteration to be expressed with recursion.

Here are two ways to compute factorial in Scheme:

  ; version 1 : no tail recursion
  ; nonnegative-number -> positive-number
  (define (fact n)
    (if (zero? n)
        1
        (* n (fact (sub1 n))))) 

  ; version 2 : uses a helper with an accumulator
  ; nonnegative-number -> positive-number
  (define (fact2 n)
    (fact2-helper n 1)) 

  ; nonnegative-number positive-number -> positive-number
  ; recursive call is in tail position
  (define (fact2-helper n accum)
    (if (zero? n)
        accum
        (fact2-helper (sub1 n) (* n accum))))

What's the difference between these two?

In Version 1, the result of the recursive call is used in a larger expression, a multiplication. Therefore, on each recursive call, the Scheme runtime system needs to save some computational context that accepts that result. The number of such required contexts is proportional to the depth of recursion which, in the case of fact, is proportional to its argument n.

In Version 2, the multiplication result is supplied as an argument to the helper. The result of a recursive call to fact2-helper is the result for the enclosing call. Therefore, the runtime system does not need to create a new computational context for the recursive call. Moreover, the values of the arguments n and accum do not need to be saved across recursive calls, so the storage for them can be reused. We say that the recursive call in this instance is a tail call.

A recursive function like fact2-helper provides a ``loop with arguments.'' The if provides the loop termination condition. In C or C++, we could write that loop explicitly:

int fact_c(int n) {
  int accum;

  for (accum = 1; n > 0; n--) {
    accum *= n;
  }

  return accum;
}

We could also have written a recursive function in C or C++ directly, much like our Scheme fact2, but that would be unwise. Most C/C++ compilers will use some amount additional stack space for each recursive call, even if that call is in tail position. Therefore, in C or C++, the run-time behavior of the program is not loop-like, despite the tail calls in the program.

Scheme systems are required to be ``properly tail-recursive.'' Very informally, that means that Scheme systems must provide loop-like behavior for procedures with tail calls. In practice, that means you can write loops with recursive procedures without worrying about overflow of the Scheme runtime stack -- as long as the recursive calls are in tail position.

Often we'd like to write a loop in Scheme without having to use explicit procedure syntax. The Scheme ``named let'' construct does that for us. We could compute the sum of the numbers from 1 to 100 with: