Consider the standard recursive implementation of factorial:
(define factorial
(lambda (n)
(if (zero? n)
1
(* n (factorial (- n 1))))))
What happens on each recursive call?
The key: This procedure computes all of (factorial (- n 1)) for n-1 down to 0 before computing the value of (factorial n)!
If only we could write a procedure that evaluates the (* n ...) part of the computation right away, the we would eliminate the need to save up all those pending computations.
We can do that, with a less straightforward procedure:
(define factorial-aps
(lambda (n answer)
(if (zero? n)
answer
(factorial-aps (- n 1) (* n answer)))))
This procedure evaluates the (* n ...) portion of its work immediately! It computes (factorial n) in reverse order, evaluating (* n running-product) and passing that running product one the recursive call that computes (factorial (- n 1)).
This procedure offers a phenomenal performance improvement, in SPEED but especially in SPACEused. We will look at this performance improvement, and the reasons for it, later in the session.
The formal parameter answer is an accumulator variable. It accumulates the partial results of the computation in much the same way a running product would in a loop.
Notice that using an accumulator variable usually requires us to use an interface procedure, too, because we add the ACCUMULATOR as an EXTRA ARGUMENT to pass on each recursive call. The interface procedure passes the initial value of the accumulator on the first call. This value is usually the identity of the operation being used. Here, that is 1:
(define factorial
(lambda (n)
(factorial-aps n 1)))
By the way, the suffix -aps refers to accumulator passing style, which is the name for this style of programming.
[ A natural extension of this idea is to make the accumulator variable be a procedure whose application to the initial value gives the desired answer. This may seem strange, but realize that we can pass that procedure to any other procedure at any time. When the accumulator is a procedure, we usually refer to it as a continuation, because it is the continuation of the processing to be done. Passing continuations around in -- so-called "continuation passing style" -- makes it possible to implement all sorts of exotic control structures, such as exceptions, threads, backtracking, and the like. Scheme is a minimalist language, in that it tends to provide only a necessary core of operations out of which all other operations can be built. That accounts for its lack of loops, for instance, which can be simulated recursively. Scheme provides support for accessing the current continuation of a computation, because out of that we can implement all the control structures we could desire! ]
Where does the speed up come form? The accumulator variable enables us to control the order of processing. This has the feel of imperative programming, the sort you are used to doing in Java and Ada. Here, we are just doing it through the order of procedure applications! Just as our aps-style solution to factorial given above begins to resemble a loop, our aps-style solution to flatten begins to resemble imperative, sequential programming. That the use of an accumulator variable gives us these two feelings is not a coincidence; they are closely related!
Finally, accumulator passing style often leads to a special case of recursion, one that isn't really recursive at all. Let's finally consider that now...
[ Sorry, but this is still a bit rough, more an outline than lecture notes. ]
Think about our accumulator-passing version of the factorial procedure:
It is iterative: it counts down from n to 0.
It is imperative: its assigns a value to variable on each pass. It assigns only once, though, on each pass.
This starts to look a lot like a for loop...
And at run time, it can be! Consider the state of the calling procedure at the moment it makes its recursive call. The value of the calling procedure is the value of the called procedure. The caller does not need to remember any pending operations or even the values of its formal parameters!
This is tail recursion.
The presence of tail recursion means that the recursive call can be implemented in place, assigning the values passed to the same versions of the formal parameters created for the calling procedure and using a goto to transfer control back to the top of the calling procedure.
In functional programming, we use recursion for all sorts of repetitive behavior. Tail recursion is common, because of the use of accumulator variables to control order of execution and because of the run-time behavior we've just seen. If tail recursion is so common and has such nice run-time behavior that is so nice, it would be nice if our interpreter would optimize this behavior.
By definition, Scheme does. The Scheme language definition specifies that every Scheme interpreter must optimize tail recursion away into a goto!
Accumulator passing style often leads to tail recursive code.
Tail recursion is a topic of much research in the area of programming languages. Java is not properly tail recursive, and making it so would complicate the virtual machine a bit... But it might be worth the effort! [Some Java compilers optimize tail recursion...]