Tail recursion in C++

Question

Can someone show me a simple tail-recursive function in C++?

Why is tail recursion better, if it even is?

What other kinds of recursion are there besides tail recursion?

Answer 1

A simple tail recursive function:

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

Tail recursion is basically when:

• there is only a single recursive call
• that call is the last statement in the function

And it's not "better", except in the sense that a good compiler can remove the recursion, transforming it into a loop. This may be faster and will certainly save on stack usage. The GCC compiler can do this optimisation.

Answer 2

Tail recusion in C++ looks the same as C or any other language.

void countdown( int count ) {
    if ( count ) return countdown( count - 1 );
}

Tail recursion (and tail calling in general) by definition clears the function's stack frame before executing the next call. Tail recursion is the same as a loop, almost a mere stylistic difference. Most compilers support it, but loops are both easier and less risky.

Tail calls can enable random branching (like goto to the first line of a function), which is a more unique facility.

Note that in C++, if you have objects to be destroyed, the end-of-function cleanup might preclude this.

EDIT: Since there seems to be some confusion here, note that tail recursion requires that the state of the algorithm be entirely passed into the function's arguments at each step. (This is clear from the requirement that the function's stack frame be eliminated before the next call begins… you can't be saving any data in local variables.) Furthermore, no operation can be applied to the function's return value before it's tail-returned.

int factorial( int n, int acc = 1 ) {
    if ( n == 0 ) return acc;
    else return factorial( n-1, acc * n );
}

Answer 3

Tail recursion does not exist really at compiler level in C++.

Although you can write programs that use tail recursion, you do not get the inherit benefits of tail recursion implemented by supporting compilers/interpreters/languages. For instance Scheme supports a tail recursion optimization so that it basically will change recursion into iteration. This makes it faster and invulnerable to stack overflows. C++ does not have such a thing. (least not any compiler I've seen)

Apparently tail recursion optimizations exist in both MSVC++ and GCC. See this question for details.

Answer 4

Wikipedia has a decent article on tail recursion. Basically, tail recursion is better than regular recursion because it's trivial to optimize it into an iterative loop, and iterative loops are generally more efficient than recursive function calls. This is particularly important in functional languages where you don't have loops.

For C++, it's still good if you can write your recursive loops with tail recursion since they can be better optimized, but in such cases, you can generally just do it iteratively in the first place, so the gain is not as great as it would be in a functional language.

Answer 5

Tail recursion is a special case of a tail call. A tail call is where the compiler can see that there are no operations that need to be done upon return from a called function -- essentially turning the called function's return into it's own. The compiler can often do a few stack fix-up operations and then jump to (rather than call) the address of the first instruction of the called function.

One of the great things about this besides eliminating some return calls is that you also cut down on stack usage. On some platforms or in OS code the stack can be quite limited and on advanced machines like the x86 CPUs in our desktops decreasing the stack usage like this will improve data cache performance.

Tail recursion is where the called function is the same as the calling function. This can be turned into loops, which is exactly the same as the jump in the tail call optimization mentioned above. Since this is the same function (callee and caller) there are fewer stack fixups that need to be done before the jump.

The following shows a common way to do a recursive call which would be more difficult for a compiler to turn into a loop:

int sum(int a[], unsigned len) {
     if (len==0) {
         return 0;
     }
     return a[0] + sum(a+1,len-1);
}

This is simple enough that many compilers could probably figure it out anyway, but as you can see there is an addition that needs to happen after the return from the called sum returns a number, so a simple tail call optimization is not possible.

If you did:

static int sum_helper(int acc, unsigned len, int a[]) {
     if (len == 0) {
        return 0;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(int a[], unsigned len) {
     return sum_helper(0, len, a);
}

You would be able to take advantage of the calls in both functions being tail calls. Here the sum function's main job is to move a value and clear a register or stack position. The sum_helper does all of the math.

Since you mentioned C++ in your question I'll mention some special things about that. C++ hides some things from you which C does not. Of these destructors are the main thing that will get in the way of tail call optimization.

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    return z.baz();
}

In this example the call to baz is not really a tail call because z needs to be destructed after the return from baz. I believe that the rules of C++ may make the optimization more difficult even in cases where the variable is not needed for the duration of the call, such as:

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    int u = z.baz();
    return qwerty(u);
}

z may have to be destructed after the return from qwerty here.

Another thing would be implicit type conversion, which can happen in C as well, but can more complicated and common in C++. For instance:

static double sum_helper(double acc, unsigned len, double a[]) {
     if (len == 0) {
        return 0;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(double a[], unsigned len) {
     return sum_helper(0.0, len, a);
}

Here sum's call to sum_helper is not a tail call because sum_helper returns a double and sum will need to convert that into an int.

In C++ it is quite common to return an object reference which may have all kinds of different interpretations, each of which could be a different type conversion, For instance:

bool write_it(int it) {
      return cout << it;
}

Here there is a call made to cout->operator<< as the last statement. cout will return a reference to itself (which is why you can string lots of things together in a list separated by << ), which you then force to be evaluated as a bool, which ends up calling another of cout's methods, operator bool(). This cout->operator bool() could be called as a tail call in this case, but operator<< could not.

EDIT:

One thing that is worth mentioning is that a major reason that tail call optimization in C is possible is that the compiler knows that the called function will store it's return value in the same place as the calling function would have to ensure that its return value is stored in.