I was putting together some of what I though were hard interview questions for advanced programmers (lots of experience or CS education) and I decided to do one on Tail Recursion. This one is kind of hard unless you are used to functional programming languages (then its a snap). For my purposes an explanation relevant to C/C++ is required to make it fit our language domain here. My questions will be, in order:
To refresh my own memory, I went to Google which sent me to Wikipedia (4) and pulled up the entry on tail recursions. I found an explanation and even a C code example, but I have to say the example is overly complicated to the point it detracts from the topic at hand.
I hate bad examples in programming literature. Some bad examples are simply wrong, or so wrong they are not even wrong (1,7,8). But that's not what I am talking about here. Another class of bad examples are those that are correct but for some reason fail to convey the proper information. Some are so adorned with scaffolding that they obscure the issue in question (See Microsoft DirectX SDK sample code). As a C/C++ programmer, I find another problem when I am trying to stay current on 'advanced' or 'modern' programming language issues (2) . Many of the examples I run into are presented in Lisp and I am immediately stumped (3). Others just could be a little better, as in this case. In the Wikipedia article on tail recursion the first example is in Scheme. So no help there. Then the second example is in C, but although it is short, it has some extraneous stuff in it that obscures the issue. It has mallocs and pointers to pointers, which means you have to think through all that before you get to the meat. So I went to my code editor and tried to come up with a simpler example that would make sense to a POCP (plain old C programmer) without the extra stuff (with the side effect that I wouldn't look too stupid when I asked the question in an interview).
Note: when I say 'C', I mean C AND C++, they are equivalent here. I'm not using any objects , templates or protected abstract virtual base pure virtual private destructors (9).
In computer science, tail recursion is a special case of recursion that can be transformed into an iteration, figure out by David H. D. Warren (4). Some functions are more easily expressed as a recursion than as an iteration. The code looks better and makes more sense. But the drawback of a recursion can be an overflowed (overflown?) stack if you aren't careful. And in C, doing something recursively usually takes longer than doing the equivalent iteration. So ideally you want to express something as a recursion but have it transformed to an iteration where possible. If you are lucky, your compiler will do the transform but if not, you might have to do it yourself. Of course, don't worry about it at all until you know you need it. Otherwise its a Premature Optimization (11).
Tail recursion optimization is a special case of tail call optimization (6), which applies to all functions, not just recursive functions. Tail call optimization is pretty simple. If you have a function that at its very end calls another function, you can skip the call and associated stack operations and do a 'goto' or jump to the beginning of the next function. The arguments that the called function needs are set up by the compiler (or programmer!) in local variables or registers and the called subroutine sees them the same way it would if it was entered conventionally. Then the called function returns back the caller's caller. For non-recursive functions, this buys you a little, but not all that much. But for recursive functions, which may have hundreds, thousands or millions of calls, the savings may add up. But the main purpose of tail recursion optimization is not to save the effort of making the call, but to eliminate the recursion altogether, so you don't get stack overflows. Scheme will already do that for you, but we are using C. Crap. Anyway, read up some more on tail recursion and tail recursion optimization (5). I don't need to reexplain it. But if you are a C programmer, skip the examples and come back here.
We will look at one of the simplest recursive functions I can think of. It takes a value and a count, and returns the sum of the value added together 'count' times. Oh, thats multiplication. but never mind that, it illustrates the point. The function is called 'sum' or some variation thereof. I am going to start with an ersatz Test Driven Development (TDD) style. Here is a program that defines 4 different versions of 'sum': sum1, sum2, sum3 and sum4. I call them and print the results to check if they work. Also, just as a spec, say that a negative count returns 0 to keep things simple.
#include "stdio.h"
int sum1(int val,int count)
{
return 0;
}
int sum2(int val,int count)
{
return 0;
}
int sum3(int val,int count)
{
return 0;
}
int sum4(int val,int count)
{
return 0;
}
int main(int argc,char *argv[])
{
int a;
int b;
int c;
int d;
a = sum1(1,5);
b = sum2(1,5);
c = sum3(1,5);
d = sum4(1,5);
printf("a=%d b=%d c=%d d=%d\n",a,b,c,d);
return 0;
}
Compile it and run. it prints the value 0 for each function. That satisfies the TDD requirement to fail. The results are obviously wrong.
Here is a simple recursive version of 'sum'
int sum1(int val,int count)
{
int s;
if (count <= 0) {
// nothing left
s = 0;
}
else {
// add one instance of 'val' to the result
// of calling sum1 with one less count
s = val + sum1(val,count-1);
}
return s;
}
Since the summing is taking place in increments, where is the intermediate sum being stored? Somewhere there is are intermediate terms of 1, 2, 3 and 4 before the final result of 5 is computed. Where are they? In sum1, the memory that contains the intermediate values of the sum are located on the stack, implicitly, in the return values of the intermediate calls. In fact, there is a copy of the intermediate data in every stack frame. Its turtles all the way down. This is good functional programming style, but in C maybe inefficient and dangerous. Dangerous? Why? Because in C and C++ you don't know how far down your stack goes. You don't have a general way to limit your recursion depth and give up before segfaulting on a stack overflow.
Compile and run now. It prints '5' for sum1, while the others are still wrong. So continue.
sum1 is NOT tail recursive, simply because it has some stuff after the recursive call to sum1 at the end. You don't even need to worry too much about what exactly is after the recursive call. Anything will do. If your function looks anything like this, it is not tail recursive:
int some_func(....)
{
...do stuff
...do stuff
some_func(...)
...do anything
}
To be tail recursive (and for tail recursion optimization to work), you need your function to look like this:
int some_func(....)
{
...do stuff
...do stuff
...do stuff
some_func(...)
}
You need to have the recursive call to itself as the last thing on the line with nothing following. Soon you will see the magic that happens if you can get to this point.
This is the hard step. We have to restructure 'sum1' to have pure tail recursion. We do that using the technique described in (4), Tail recursion modulo cons. Ouch, there's that Lisp stuff again. What the heck is 'modulo cons'? Either learn Lisp or accept that it means something to someone. Just do the following very mechanical procedure. Take your original recursive function and split it into two parts, the original (the stub) and a pure tail recursive function, the 'cons' function, (from Lisp, short for constructor, not to be confused with the OOP C++ constructor). The stub still has the same signature that the clients will call, so the outside world doesn't see anything different. Privately, the stub does two things: it provides an 'accumulator' of some sort and it calls the cons function, passing it the original parameters plus the accumulator. What is an accumulator? Besides being what the Lisp guy always talks about when discussing lexical closures (10), in our case, since we don't have closures in C, it is just any variable or set of variables and operations needed to maintain the intermediate state of the compution, which would have been done implicitly on the stack in the recursive version. In my example it is just an int variable initialized to zero. In the Wikipedia example, it is a linked list head on which the pure recursive body builds up the result. To me, using a linked list with mallocs and pointers to pointers just obscures what you really want to demonstrate. It makes the code look difficult for no good reason.
// original function is changed to a stub that calls
// the pure tail recursive version
// has the pure tail recursion
int sum2(int val,int count)
{
// set up an accumulator 'x' which will hold the
// intermediate results
int x = 0;
// call the stub, passing it the original parameters
// plus a pointer to the accumulator
sum2_cons(val,count,&x);
// return the value of x
return x;
}
The tricky part is structuring the cons function. Just remember the last thing it has to do is do a recursive call to itself. Nothing else is allowed. Here is what I ended up with for this example:
// set up a pure tail recursive constructor
int sum2_cons(int val,int count,int *accumulator)
{
// quit if no counts left
// important to quit here. not allowed to quit at the end
// and if you don't quit you'll get a segfault when the stack overflows
if (count <= 0) return 0;
// sum into the accumlator. remember, the accumulator can be anything that
// holds the intermediate state of whatever you are constructing
*accumulator += val;
// call back into itself.
// now we have tail recursion. nothing happens after
// the recursive call. the recursion will still
// end when the count argument goes to 0
sum2_cons(val,count-1,accumulator);
}
You may get a compiler warning that not all code paths in sum2_cons return a value. The compiler just isn't smart enough to figure out what is going on. You can ignore the warning, or if that bugs you, put a return statement after the call to sum2_cons. it will never get there and doesn't hurt. But please put a comment or people will wonder 'how did he expect it to get to this point?'.
The conversion is mechanical, and there is a definite design pattern. The design pattern for the cons function is always:
void cons_func(args...,accumlator)
{
check termination condition
construct one element into the accumulator
call self recursively
}
The design patter for the stub function is always
void original(args...)
{
declare an accumulator
call cons_func passing original args + the accumulator
return value of accumulator
}
Again, the accumulator is anything you need. Our case is simple, but a more complex case might need several variables, or maybe an object that encapsulates the state and operations (thereby simulating a lexical closure).
Thats all great so far but there is still recursion, and although the intermediate results are no longer on the stack, there is still one stack frame for every recursive call, so not a lot is gained. Here is where the magic happens and it is incredibly simple. Because the cons function is now pure tail recursive, we can make it iterative. Here is the design pattern:
void cons_func(args...,accumlator)
{
check termination condition
construct one element into the accumulator
// call self recursively
change value of 'args' to be what they would in the called recursive
function
jump to the beginning of the function (not CALL, JUMP!)
}
Here is the implementation of sum3, which is sum2, transformed to an interative solution. Only the 'cons' function is changed. The original stub is left alone.
// set up an iterative constructor
int sum3_cons(int val,int count,int *accumulator)
{
LOOP:
// quit if no counts left
// important to quit here. not allowed to quit at the end
// and if you don't quit you'll get an infinite loop instead of a segfault
if (count <= 0) return 0;
// sum into the accumlator. remember, the accumulator can be anything that
// holds the intermediate state of whatever you are constructing
*accumulator += val;
// now, instead of the recursive call back into itself,
// change the arguments as required to make them the same value they would
// have been in the recursive call, and jump back to the beginning
count--;
goto LOOP; // yes yes a goto is considered harmful, but this is a good use of it
}
Voila!, the function is now iterative. You can call it at will without fear of overflying your stack. The only addition a responsible programmer might add would be some checks to avoid accumulator overflow. Here, you would get integer overflow. The Wikipedia example might run out of heap space in the mallocs. Whatever.
Ok, for those of you who simply can't stand to have a goto in your program, sum4 is a trivial change to remove the goto, changing it to a for loop.
// set up an iterative constructor without the hideous GOTO
int sum4_cons(int val,int count,int *accumulator)
{
// quit if no counts left
// if you don't quit you'll get an infinite loop instead of a segfault
while(count > 0) {
// sum into the accumlator. remember, the accumulator can be anything that
// holds the intermediate state of whatever you are constructing
*accumulator += val;
// now, instead of the recursive call back into itself,
// change the arguments as required and jump back to the beginning
count--;
}
return 0;
}