27 September 2006
Tail Recursion in PHP
There are two types of recursion in the world: tail recursive and non-tail recursive. Non-tail recursive is the more obvious of the two and is used frequently. For instance, when dealing with any kind of hierarchical data (that which is expressed in a tree data structure) a recursive call is likely used to construct the structure and often, another is used to operate on it. Though recursion is not the simplest concept in PHP, it is fairly obvious: given a set of data, a recursive function will operate on as much of it as it knows how and than calls itself again with a subset or derivative of the original data. This process continues until the function has determined a final result.
Recursion has one large downside. On each function call, the current functions environment must be stored somewhere, in order to resume the calling function once the callee is finished. On most processors in most languages, the environment is called the stack. The problem is the stack has a finite size. It can generally hold many iterations of recursion, but there is a limit. In most languages, there are two major factors which govern the maximum number of calls which can be made: limitations in the host language and limitations in the physical amount of memory required to store the environment.
As an interpreted language, PHP is largely immune from the physical memory issue. A setting in PHP.ini controls the maximum quantity of memory a script can consume, and the stack is counted in that number. But in most cases with native code, the stack is separate from the total memory on a machine. PHP’s only issue isn’t even technically one of recursion. Instead, it is an imposed limit in the design of the interpreter. Every nested (recursive or otherwise) function call counts towards a limit of 2000 nested calls. PHP will mysteriously die if that count is ever reached.
In most languages, the solution is to use tail recursion. Tail recursion is really both an optimization and an exploit on how code is executed. Many recursive functions’s final action is to again call itself with modified arguments, and to return that result. An intelligent compiler which recognizes the traits of tail recursion can simply warp the arguments a function passes into the argument a function receives and restart execution. For instance, in this pseudo-code:
function add (x, y) {
if (y > 0) {
add (++x, –y)
} else {
return x;
}
}
Could become:
function add (x, y) {
function_start:
if (y > 0) {
x++; y–; goto function_start;
} else {
return x;
}
}
PHP does not allow this.
If PHP 6 introduces a goto (which is currently planned) it becomes possible. But in PHP 5 and earlier, it is simply not possible. However, in a round-about way, tail-recursion is possible. It requires writing a fairly substantial intermediary layer, though. Using a device called a trampoline, a function could return a function which needs to be called. Observe:
function add ($x, $y) {
if ($y > 0) {
return array (”add”, $x + 1, $y - 1);
} else {
return $x;
}
}
$f = array (”add”, 6, 5);
do {
$func = $f[0];
$f = $func($f[1], $f[2]);
} while (is_array ($f));
It’s hardly pretty (though implicit evaluation improves this drastically over other methods) but it’s not awful and makes some things in PHP possible that would otherwise require writing an extension in another language.
Might a work around for the lack of goto’s (as referred to in one of the examples) be…
function add_2 ($x, $y)
{
$f_start=’add_2′; // To be the same as –> function_start: Like a goto.
if ($y > 0)
{
++$x;
–$y;
echo “About to recurse! Our values are (\$x, \$y) | ($x, $y).\n”;
$f_start($x, $y);
}
else
{
echo $x.”\n”;
return $x;
}
}
?
I threw in the echo statements to make sure it was working.