Detailed explanation on the use of tail recursion_PHP tutorial-PHP Tutorial-php.cn

Detailed explanation on the use of tail recursion_PHP tutorial

WBOY

Release： 2016-07-21 15:10:24

Original

1159 people have browsed it

I have seen several articles about tail recursion in the past few days. I didn’t have much idea about tail recursion before, so I went back and studied tail recursion.

The concept of tail recursion
The concept of tail recursion is a subset of the recursion concept. For ordinary recursion, the cost of having to remember the recursive call stack is immeasurable. For example, the first example in the PHP section below uses PHP to write a factorial function, which causes a stack overflow error due to recursion. The purpose of tail recursion is to eliminate the shortcoming of recursive stack consumption.

From a code level, tail recursion can be explained clearly in one sentence:

The last operation of the function is the recursive call

For example, the recursive implementation of the "Fibonacci" sequence in PHP:

Copy the code The code is as follows:

fibonacci.php                                                                                                                                                               > return fibonacci($n - 1) + fibonacci($n - 2); 
} 

var_dump(fibonacci(30)); 

This is Recursive function, but not tail recursive because the last operation of fibonacci is an addition operation. 

Convert to tail recursion:

Copy code

The code is as follows:

function fibonacci2($n, $acc1, $ acc2) { if ($n == 0) { return $acc1; }

return fibonacci2($n-1, $acc2, $acc1 + $acc2);

 } 

fibonacci2 is a tail recursion, which adds two accumulators acc1 and acc2 and gives the initial value. Remember: the idea of ​​converting recursion into tail recursion must be to increase the accumulator and reduce recursive external operations. 
Tail recursion has different applications in different languages. The most commonly used one is functional programming Erlang. Almost all functions that appear recursive are modified to become tail recursive. Let’s talk about the performance and application of tail recursion in several different languages. 

Tail recursion in php
Let’s do an experiment

Normal recursion:

Copy code
The code is as follows:

function factorial($n) { if($n == 0) {

return 1;

 } 
 return factorial($n-1) * $n; 
} 

var_dump(factorial(100000000)); 

Tail recursion:

Copy code
The code is as follows:

function factorial($n, $acc){ if($n == 0) {

Return $acc;

}
return factorial($n-1, $acc * $n);
}

var_dump(factorial(100000000, 1));

Experimental results:

It turns out that
tail recursion has no optimization effect in PHP!

Tail recursion in C

Tail recursion optimization in C is done by the gcc compiler. Adding -O2 when compiling with gcc will optimize tail recursion

We can directly look at the generated assembly code:

(Use gdb, gcc –O2 factorial.c –o factorial; disass factorial)

Assembly generated without -O2:

Assembly added with O2 optimization:

Don’t be too big-headed, I also saw the assembly for the first time, but this code It’s very simple. Just search for the command online and you can roughly understand it:

Copy the code The code is as follows:

function factoral( n, sum) {
 while(n != 0){
 sum = n * sum
 n = n-1
 }
 return sum

}

What gcc does is indeed intelligent optimization.

If you are still interested, you can use -O3 to optimize tail recursion and view the assembly instructions

-O3’s optimization is to directly unroll the loop

Summary

The biggest advantage of modifying general linear recursion into tail recursion is that it reduces the overhead of the recursive call stack. From the PHP example, we can clearly see the impact of recursive overhead on the program. However, not all languages support tail recursion. Even languages that support tail recursion generally optimize tail recursion during the compilation phase. For example, the optimization of tail recursion in C language in the above example. When using tail recursion to optimize code, you must first understand the language's support for tail recursion.