Tail recursion in C ++

Question

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

Why is tail recursion better if it even exists?

What other types of recursion exist besides tail recursion?

Answer 1

Simple tail recursive function:

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

Tail recursion is mainly when:

• there is only one recursive call
• this call is the last in function

And this is not “better,” except in the sense that a good compiler can remove recursion by turning it into a loop. This can be faster and will certainly save on stack usage. The GCC compiler can do this optimization.

Answer 2

The tail return in C ++ looks the same as C or any other language.

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

Tail recursion (and the tail call in general) requires clearing the caller's stack frame before making a tail call. For a programmer, tail recursion is like a loop, with return reduced to working like goto first_line; . However, the compiler must determine what you are doing, and if this does not happen, an additional frame stack will still be added. Most compilers support it, but writing a loop or goto usually simpler and less risky.

Non-recursive tail calls may include random branching (e.g. goto in the first line of some other function), which is a more unique means.

Note that in C ++ there cannot be an object with a nontrivial destructor in the scope of the return . Cleaning at the end of the function requires the caller to return back to the caller, eliminating the tail call.

Also note (in any language) that tail recursion requires that the entire state of the algorithm be passed through a list of function arguments at each step. (This is clear from the requirement that the frame of the function stack be deleted before the start of the next call ... you cannot save data in local variables.) In addition, no operation can be applied to the return value of the function before returning the tail.

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

Answer 3

Tail recursion is a special case of tail call. The tail of the call is where the compiler can see that there are no operations that need to be done when returning from the called function - essentially turning the called function into its own. The compiler can often perform several stack fix operations and then go (instead of calling) to the address of the first instruction of the called function .

One of the great things besides eliminating some callbacks is that you also reduce stack usage. On some platforms or in OS code, stacks can be very limited, and on modern computers, such as the x86 processors on our desktop computers, reduces stack usage, which will improve the performance of the data cache.

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

The following is a general way to make a recursive call, which will be more difficult for the 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); } 

It is simple enough that many compilers may still be able to figure it out, but as you can see, there is an addition that should happen after the number returns from the called sum, so simple tail call optimization is not possible.

If you have done this:

 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 could use calls in both functions that are tail calls. Here the main task of the sum function is to move the value and clear the position of the register or stack. Sum_helper does all the math.

Since you mentioned C ++ in your question, I will talk about some special things. C ++ hides from you some things that are not there. Of these destructors, the main thing that will interfere with tail call optimization.

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

In this example, the baz call is not really a tail call, since z should be destroyed after returning from baz. I believe that C ++ rules can make it difficult to optimize even in cases where the variable is not required during the whole time of the call, for example:

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

z can be destroyed after returning from qwerty here.

Another thing is implicit type conversion, which can also happen in C, but can be more complex and common in C ++. For example:

 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 the sum_helper call is not a tail call, because sum_helper returns double, and the sum will need to convert it to int.

In C ++, references to objects that can have different kinds of interpretations, each of which may be a different type conversion, are returned quite often, For example:

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

There is a call here made for cout.operator <as the last statement. cout will return a link to itself (so you can insert many things together into a list separated by a <<symbol), which is then forcibly evaluated as bool, which ends with a call to another cout method, the BOOL () operator. This cout.operator bool () can be called as a tail call in this case, but the <<operator could not.

EDIT:

One thing worth mentioning is that the main reason for optimizing tail optimization in C is that the compiler knows that the called function will save this return value in the same place as the calling function, the return value is saved.

Answer 4

Tail recursion doesn’t actually exist at compiler level in C ++.

Although you can write programs that use tail recursion, you do not get the inherited benefits of tail recursion realized by supporting compilers / interpreters / languages. For example, a schema supports tail recursion optimization, so it basically changes the recursion to iteration. This makes it faster and invulnerable to. C ++ doesn't have that. (least not the compiler I've seen)

Tail recursion optimization seems to exist in both MSVC ++ and GCC. See this question for more details.

Answer 5

Wikipedia has a decent article on tail recursion . In principle, tail recursion is better than regular recursion because it is trivial to optimize it in an iterative loop, and iterative loops are usually more efficient than recursive function calls. This is especially important in functional languages ​​where you do not have loops.

For C ++, it is still useful if you can write recursive loops with tail recursion, as they can be better optimized, but in such cases you can just do iteratively in the first place, so that the gain is not as big as it would be in a functional language.

Answer 6

Tail recursion is a trick that allows you to simultaneously cope with two problems. The first runs a loop when it is difficult to know the number of iterations.

Although this can be worked out with simple recursion, a second problem arises that is related to stack overflow due to the fact that the recursive call is executed too many times. Tail-call is a decision when it is accompanied by “computation and transfer”.

In basic CS, you will learn that a computer algorithm must have an invariant and a termination condition. This is the basis for building tail recursion.

• All calculations occur when passing arguments.
• All results must be passed to function calls.
• The tail of the call is the last call and occurs at the end.

To just say, the return value of your function should not be calculated .

Take, for example, a computation of degree 10, which is trivial and can be written in a loop.

It 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 the execution, for example, 4:

RET p

-, 4.1

-, 3.10

-, 2100

-, 1,1000

-, 0,10000

10000, -, -

It is clear that the compiler just needs to copy the values ​​without changing the stack pointer and when the tail call occurs only in order to return the result.

Tail recursion is very important because it can provide off-the-shelf compilation time estimates, for example. The above can be done.

 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 calculate the 10th power at compile time.

Most compilers have a restriction on nested calls, so a tail trick helps. Obviously, there are no metaprogram loops, so recursion must be used.