Tail recursion in C++

c++ recursion g++ tail-recursion
neuromancer picture neuromancer · Apr 22, 2010 · Viewed 39.8k times · Source

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

anon picture anon · Apr 22, 2010

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.

Related questions

Recursive Fibonacci

I'm having a hard time understanding why #include <iostream> using namespace std; int fib(int x) { if (x == 1) { return 1; } else { return fib(x-1)+fib(x-2); } } int main() { cout << fib(5) << endl; } results in a segmentation …

Read More
What exactly is a reentrant function?

Most of the times, the definition of reentrance is quoted from Wikipedia: A computer program or routine is described as reentrant if it can be safely called again before its previous invocation has been completed (i.e it can be …

Read More
When to use recursive mutex?

I understand recursive mutex allows mutex to be locked more than once without getting to a deadlock and should be unlocked the same number of times. But in what specific situations do you need to use a recursive mutex? I'm …

Read More