Tail Recursion
From CS315
Written by Brandon Streiff
Tail recursion is an optimization used in order to get recursively-written functions to use up the same space as their iteratively-written cousins.
Contents |
Functional Languages
First, a history lesson: There are several different 'styles' of programming languages; Java, for instance, is object-oriented, and it borrows a lot from imperative languages such as C (C++ is sort of a cross between the two). The philosophy of their design is based upon a model of computation developed by Alan Turing known as a Turing machine. (You'll learn more about Turing machines in Automata Theory). There's another model of computation, pioneered by Turing's advisor Alonzo Church, called the Lambda calculus. In the Lambda calculus, you don't have a distinction between data and code-- everything is a function; you apply functions to other functions and get functions back that you use as a representation of data.
Now, the cool thing is that Turing machines and the Lambda calculus are equivalent models of computation. (This is the Church-Turing thesis.) While Turing machines are more analogous to a computer language involving pushing bits around (see: C.), a computer language that deals entirely in functions is just as powerful. Hence, we have functional languages, such as Scheme, LISP, and Haskell.
Ordinary Recursion
The thing about functional languages is that they use recursion heavily. For instance, if you wanted to take the sum of a list of integers in Haskell, you could write:
sumList [] = 0 sumList (x:xs) = x + (sumList xs)
(Every list in Haskell is a linked list comprised of 'cons cells'; that is, each cell in a linked list is conceptually a data element (x, in the above) connected to the remaining elements in the list (xs, in the above). Haskell also does a sort of 'pattern matching' for arguments, so in the above, if the parameter is an empty list, the function returns zero, otherwise, it recurses.))
Now, the trouble with functional languages and recursion is that we need to run them on real hardware. To do recursion on real hardware, we use stack frames. So to compute the above, we have, for instance, for: sumList [1,2,3,4]
sumList 1:[2,3,4] ⇒ 1 + (sumList [2,3,4]) sumList 2:[3,4] ⇒ 2 + (sumList [3,4]) sumList 3:[4] ⇒ 3 + (sumList [4]) sumList 4:[] ⇒ 4 + (sumList []) sumList [] ⇒ 0
It's clear that looking at this, we need to keep the stack frame of the caller around, since when we invoke the recursive call, we're not yet done with the caller. Each caller has to call sumList, retrieve its value, and then add a number to it. Thus this implementation takes linear time (we go through all the elements) and linear space (there's a stack frame for each element).
Tail recursion
But what if we wrote our sumList in such a way that we didn't need to keep these additional stack frames around?
sumList2 [] v = v sumList2 (x:xs) v = sumList2 xs (v + x)
Now let's look at the execution of sumList2 [1,2,3,4] 0:
sumList2 1:[2,3,4] 0 ⇒ sumList2 [2,3,4] (0 + 1)
⇒ sumList2 [2,3,4] 1
sumList2 2:[3,4] 1 ⇒ sumList2 [3,4] (1 + 2)
⇒ sumList2 [3,4] 3
sumList2 3:[4] 3 ⇒ sumList2 [4] (3 + 3)
⇒ sumList2 [4] 6
sumList2 4:[] 6 ⇒ sumList2 [] (6 + 4)
⇒ sumList2 [] 10
sumList2 [] 10 ⇒ 10
What's the important thing we notice here? When we make the recursive call, we don't need to maintain the state of the caller anymore! If we don't need to maintain the state of the caller anymore, then we don't need to keep the caller's stack frame around-- thus we can just reclaim the space. This new approach is still linear time, but now uses constant space.
The key point is that the recursive call is in tail-call position-- the result of the recursive call is the return value of the function. If we're just returning the value of this call to our caller, we can just skip the middle-man and have the recursive call return its value to the caller. To achieve this, we usually have to put additional variables into the parameter list for the function; notice how we've added a parameter to store the result of our addition.
Other languages
People who come up with imperative languages discovered that this was a pretty clever trick-- after all, you often find yourself writing recursive implementations of algorithms in imperative languages (common things that tend to be recursive: tree traversals and sorting algorithms), because they're a lot cleaner to write that way-- so they added this same tail-call optimization.
So, now, let's look at the two above list-summing algorithms in Java. The parameters we pass are a little different (instead of a linked-list as in Haskell, we pass an array and an index), but otherwise equivalent.
public class ListSummer {
public static int sumList(int[] l, int i) {
if (i >= l.length)
return 0;
else
return l[i] + sumList(l, i+1);
}
public static int sumList2(int[] l, int i, int v) {
if (i >= l.length)
return 0;
else
return sumList2(l, i+1, v+l[i]);
}
}
Understandably, ListSummer.sumList() requires a new stack frame for each invocation. But if you try ListSummer.sumList2() you'll find that the JVM allocates a new stack frame here too! The reason is actually pretty simple but unfortunate: The JVM doesn't handle tail-recursion at all. Quite a few people would like to see it added, actually, but there's some contention on adding it due to things like being able to pretty-print stack traces in exceptions. Alas.
Still, you should be aware of what tail-recursion is, because other languages, such as C/C++, do support it (with gcc, compile with -O1 or above), and other languages, such as Scheme or Haskell, pretty much require it.
