68

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?

Earlz
  • 62,085
  • 98
  • 303
  • 499
neuromancer
  • 53,769
  • 78
  • 166
  • 223
  • 1
    Duplicate: http://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization. Not an identical question, but the answers to that question answer this one. – Steve Jessop Apr 22 '10 at 19:11
  • 4
    Is tail recursion better than what? – nategoose Apr 22 '10 at 19:12
  • @T.E.D. If the author does not say it is homework, please do not tag as homework. (though `[beginner]` can be used of course) – Earlz Apr 22 '10 at 19:16
  • 2
    @Steve - Then it is not an "exact duplicate". The point here is that someone can do an internet search on their question and hit SO. A search on his question would not hit 34135, and the OQ wouldn't recognize it as the same question. – T.E.D. Apr 22 '10 at 19:16
  • 1
    Better than non-tail recursion – neuromancer Apr 22 '10 at 19:17
  • 1
    @T.E.D. http://www.google.com/search?q=tail+recursion+in+c%2B%2B. Second hit. What's your point? "This question covers exactly the same ground as earlier questions on this topic". *Even if* a Google search hits this question and not that one, if this one has been closed a duplicate of the other then the searcher can follow the link. Otherwise we could never make anything a duplicate, just in case some search hit the closed question in preference to the open one. – Steve Jessop Apr 22 '10 at 19:19
  • @T.E.D. (again) anyway, there are plenty of questions on tail-recursion, which show up on Google in various orders according to your exact search. I picked one which talks about optimisation (hence why it's a good thing), and showed a code example in C++ (intended as C, but valid C++ as well). It doesn't say what other kinds of recursion there are, but if you ask three different questions, does a single other question really have to cover all three for it to be better not to have duplicates? The top few results for "tail recursion" in the S.O. search provide the same information between them. – Steve Jessop Apr 22 '10 at 19:31
  • As Alexander Stepanov put it: "There are computer scientists who believe that it is essential that compilers recognize tail recursion and eliminate the recursive call automatically. I belong to a school of thought that thinks it is essential that programmers recognize tail-recursion and learn how to transform it into iteration." good question :) – Maciej Hehl Apr 22 '10 at 19:40
  • @Maciej: at any rate programmers should know whether they're writing in a functional or an imperative style, and act accordingly. It's almost as "unnatural" to rely on a C compiler for tail-recursion as it would be to refuse to rely on a LISP compiler for it. – Steve Jessop Apr 22 '10 at 19:43
  • While tail recursion is allowed in the C and C++ standards, tail recursion optimization is not guaranteed. This means even though all mainstream implementations currently seem to optimize tail calls depending on compiler flags, portable programs cannot count on that. It is therefore unwise to employ a programing style in C/C++ which assumes tail recursion optimization. – Guenther Brunthaler Feb 05 '19 at 21:21

6 Answers6

69

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.

  • So is tail recursion then just when the return statement has the recursive call? – neuromancer Apr 22 '10 at 19:18
  • Not quite. Tail recursion is when the last computed statement is recursive. If, for instance, f(a-1) were assigned to a variable in this example, that would still be tail-recursive. – Joel Apr 22 '10 at 19:21
  • 10
    To clarify Neil's answer, a compiler can usually optimize a tail-recursive function into a loop if the recursive function is the absolute final operation in the function (aside from `return`). That is, Neil's example could be auto-optimized, but if it was modified to end with `return f(a-1) + 1;` then it would not typically be optimized (since the `+1` would be performed after the recursive call). – bta Apr 22 '10 at 19:25
  • 3
    Interestingly, looking at the assembly output, `gcc 4.3` seems to optimize away the recursion in both a naive and a tail-recursive factorial function starting at `-O2`. – Mike Dinsdale Apr 22 '10 at 19:35
  • 1
    @Joel: i don't think it would still be tail-recursive, since the last statement would be the assignment and not the call. unless a very smart compiler could hoist the assignment out of the function; but i doubt it. – Javier Apr 22 '10 at 19:43
  • 2
    @Javier : Usually assignment to a local variable is just an illusion for the programmers sake; just allowing her to use the name. Most any compiler with any level of optimization at all could see x=f(a-1);return x; as the same as the last statement in the example as it would just apply the label x to the location of the value returned by f and would not have any reason to move the value from that location. – nategoose Apr 23 '10 at 14:09
  • @nategoose: i see that a line like `x=f(a-1);return x;` doesn't do any 'real' assignment if `x` is local. that's why i didn't even thought of your initial comment as talking about a local variable. if `x` is a global (or, more likely, something like `*out=f(a-1);return x;`), then i don't think you can keep the tail recursion. – Javier Apr 24 '10 at 12:20
  • LLVM also does tail recursion elimination, gcc does it in O2 or O3 while LLVM does in O1 or O2 or O3 – hadi sadeghi Apr 26 '17 at 12:19
44

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) requires clearing the caller's stack frame before executing the tail call. To the programmer, tail recursion is similar to a loop, with return reduced to working like goto first_line;. The compiler needs to detect what you are doing, though, and if it doesn't, there will still be an additional stack frame. Most compilers support it, but writing a loop or goto is usually easier and less risky.

Non-recursive tail calls can enable random branching (like goto to the first line of some other function), which is a more unique facility.

Note that in C++, there cannot be any object with a nontrivial destructor in the scope of the return statement. The end-of-function cleanup would require the callee to return back to the caller, eliminating the tail call.

Also note (in any language) that tail recursion requires the entire state of the algorithm to be passed through the function argument list 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 );
}
Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
  • 12
    I'm guessing I just got downvoted because of confusion about the functionality of the `countdown` function. Granted it isn't particularly useful, but it is correct. You are allowed to return a void expression from a void function; in this case `return expr;` is equivalent to `expr; return;` **except that it explicitly denotes tail calling.** – Potatoswatter Oct 06 '10 at 21:52
  • You don't need the `else` keyword there, right? – whoan May 13 '22 at 10:14
28

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 (rather than call) to 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 acc;
     }
     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 acc;
     }
     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.

Community
  • 1
  • 1
nategoose
  • 12,054
  • 27
  • 42
  • I know I'm _really_ late to the party here. But to take your second `dharma` example - would introducing an extra scope (with `{ }`) and doing the calculation to find `u`, having `z` go out of scope before the end of the function allow tail recursion in this case? - should this be a question all of its own? – Baldrickk Oct 30 '19 at 16:32
2

Tail recursion is a trick to actually cope with two issues at the same time. The first is executing a loop when it is hard to know the number of iterations to do.

Though this can be worked out with simple recursion, the second problem arises which is that of stack overflow due to the recursive call being executed too many times. The tail call is the solution, when accompanied by a "compute and carry" technique.

In basic CS you learn that a computer algorithm needs to have an invariant and a termination condition. This is the base for building the tail recursion.

  1. All computation happens in the argument passing.
  2. All results must be passed onto function calls.
  3. The tail call is the last call, and occurs at termination.

To simply put it, no computation must happen on the return value of your function .

Take for example the computation of a power of 10, which is trivial and can be written by a loop.

Should look something like

template<typename T> T pow10(T const p, T const res =1)
{
return p ? res: pow10(--p,10*res);
}

This gives an execution, e.g 4:

ret,p,res

-,4,1

-,3,10

-,2,100

-,1,1000

-,0,10000

10000,-,-

It is clear that the compiler just has to copy values without changing the stack pointer and when the tail call happens just to return the result.

Tail recursion is very important because it can provide ready made compile time evaluations, e.g. The above can be made to be.

template<int N,int R=1> struct powc10
{
int operator()() const
{
return  powc10<N-1, 10*R>()();
}
};

template<int R> struct powc10<0,R>
{
    
int operator()() const
{
return  R;
}

};

this can be used as powc10<10>()() to compute the 10th power at compile time.

Most compilers have a limit of nested calls so the tail call trick helps. Evidently,there are no meta programming loops, so have to use recursion.

Community
  • 1
  • 1
g24l
  • 3,055
  • 15
  • 28
1

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.

Community
  • 1
  • 1
Earlz
  • 62,085
  • 98
  • 303
  • 499
  • Whether or not a compiler does or doesn't optimize tail recursion depends on the compiler. gcc does (or can at least). – sepp2k Apr 22 '10 at 19:15
  • Really? I'll have to look into this. I thought it may have broken the C++ spec or something – Earlz Apr 22 '10 at 19:17
  • Generally people writing C don't use recursion, so the optimization is left out. Gcc is the exception here, as far as I know. – Joel Apr 22 '10 at 19:22
  • 3
    @Joel I use recursion heavily in all my C++ code and used to do so when I wrote C. How else do you deal with trees, expression evaluation, parsing etc. etc. –  Apr 22 '10 at 19:33
  • 2
    @Neil: recursive expression evaluation? You want to get yourself a nice shunting yard ;-) – Steve Jessop Apr 22 '10 at 19:48
  • @Neil: Any recursion can be transformed into an iteration (by using a stack). – Nemanja Trifunovic Apr 22 '10 at 20:00
  • 1
    @Nemanja Of course it can, but are you suggesting that C programmers are routinely doing this? Just because something can be done doesn't mean that it is done in practice. –  Apr 22 '10 at 20:10
  • Tree traversal algorithms generally don't admit tail recursive implementations, however. Not claiming we don't use recursion, just that tail recursion is unusual. It would be far more common to see a loop based factorial than the recursive version you see most often in functional languages, for instance. The same for list traversals. – Joel Apr 22 '10 at 20:24
  • 1
    When I write trees I make sure to either use tail recursion or iteration whenever possible. Recursion is much easier for node visitors, but for lookup I typically do iterative. For doing recursive visitors I dream that the compiler is smart enough use a stack depth counter and push/pop iteratively rather than doing real recursion (pushing return addresses). – nategoose Apr 22 '10 at 20:36
0

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.

Jonathan M Davis
  • 37,181
  • 17
  • 72
  • 102
  • That's still not tail-recursive. – sepp2k Apr 22 '10 at 19:18
  • Isn't it easier to write a tail-recursive function than an iterative loop? – neuromancer Apr 22 '10 at 19:21
  • 1
    Whether it's easier to write a tail-recursive function or an iterative loop will likely depend on what you're trying to do and how you think. If you're really used to writing recursive functions or the problem is really easy to define recursively, then the recursive function could be easier to write. However, if you're not good with recursion or if the problem in question can easily be treated iteratively, then it can be easier to write an iterative loop. – Jonathan M Davis Apr 22 '10 at 19:24
  • Careful with the terminology "recursive loop." All loops are recursive. The problem with using this mathematical terminology is that there's no mathematical difference between the concepts. – Potatoswatter Apr 22 '10 at 19:36