PHP and Recursion_PHP Tutorial-PHP Tutorial-php.cn

PHP and Recursion_PHP Tutorial

WBOY

Release： 2016-07-13 17:52:19

Original

1289 people have browsed it

In programming, recursion is a very common concept. Proper use of recursion can improve the readability of the code, but it may also cause some problems.

The following uses Factorial as an example to illustrate the use of recursion. The implementation language is PHP:

function factorial($n) {
If ($n == 0) {
Return 1;
}

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

var_dump(factorial(100));

?>
If XDebug is installed, you may encounter the following error:

Fatal error: Maximum function nesting level of ’100′ reached, aborting!

Note: This is a protection mechanism of XDebug and can be set through the max_nesting_level option.

Even if the code can run normally, as long as we continue to increase the parameters, sooner or later the program will report an error:

Fatal error: Allowed memory size of … bytes exhausted

Why? To put it simply, recursion causes stack overflow. There are several methods that can be used to avoid this problem, such as using tail calls to eliminate the impact of recursion on the stack.

The following uses Lua as the description language to illustrate the meaning of tail calls. The code is as follows:

function factorial(n)
If (n == 0) then
return 1
End

return factorial(n - 1) * n
end

print(factorial(100))
This code will also encounter stack overflow problems. How to use tail call to do it? Let's first look at the definition of tail call: If a function does nothing else after executing a function call, it is called a tail call. To put it figuratively, it means directly returning a function call. Tail calls do not return the original function, so there is no need for an additional stack to retain the data of the calling function. After the above code is changed to tail call, it will look like the following code:

function factorial(n, accumulator)
Accumulator = accumulator or 1

if (n == 0) then
return accumulator
End

return factorial(n - 1, accumulator * n)
end

print(factorial(100))
Note: For an introduction to tail calling in Lua, please refer to: Proper Tail Recursion.

Mirroring the cat and the tiger, we use PHP to implement a tail call version of factorial:

function factorial($n, $accumulator = 1) {
If ($n == 0) {
return $accumulator;
}

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

var_dump(factorial(100));

?>
Unfortunately, after testing, I discovered that PHP does not support tail calls at all! Fortunately, the sky is the limit. Read carefully the introduction to tail calls in Wikipedia, and you will find that the concept of Trampoline is mentioned in it. To put it simply, we use higher-order functions to eliminate recursion. Based on this theoretical basis, we can rewrite the above tail call code as follows:

function factorial($n, $accumulator = 1) {
If ($n == 0) {
return $accumulator;
}

return function() use($n, $accumulator) {
return factorial($n - 1, $accumulator * $n);
};
}

function trampoline($callback, $params) {
$result = call_user_func_array($callback, $params);

while (is_callable($result)) {
$result = $result();
}

return $result;
}

var_dump(trampoline('factorial', array(100)));

?>
It looks good, but I have to apologize to everyone. The use of recursion to implement factorial in this article is actually a joke. In fact, it only needs to use a loop. This is specifically mentioned in "Code Encyclopedia":

function factorial($n) {
$result = 1;

for ($i = 1; $i <= $n; $i++) {
$result *= $i;
}

return $result;
}

var_dump(factorial(100));

?>
There are many other ways to avoid stack overflow problems caused by recursion. For example, in Python, you can use decorators and exceptions to eliminate tail calls, which gives people a unique feeling:

Tail Call Optimization Decorator (Python recipe)
In addition, the father of Python’s blog post about why tail calls are not supported in Python is also interesting:

Tail Recursion Elimination
Final Words on Tail Calls
Okay, let’s stop writing this. Unless it can improve code readability, there is no need to use recursion; when absolutely necessary, it is best to consider using techniques such as Tail Call or Trampoline to avoid potential stack overflow problems.

Author:: Lao Wang