Tail Recursion does not work #248
Description
The code in https://gist.github.com/beberlei/4145442 changes the recursive call in line 49 to be a call to the instance variable $func, which in turn is changed in the line 19. Through that then the recursive calls return immediately, storing the arguments in the $acc instance variable. The re-implementation in functional-php does not do that, rendering the tail_recursion a noop.
Compare the output of these two scripts:
functional-php code
<?php
function tail_recursion(callable $fn): callable
{
$underCall = false;
$queue = [];
return function (...$args) use (&$fn, &$underCall, &$queue) {
$result = null;
$queue[] = $args;
if (!$underCall) {
$underCall = true;
while ($head = \array_shift($queue)) {
$result = $fn(...$head);
}
$underCall = false;
}
return $result;
};
}
function fac($n, $acc = 1) {
if ($n == 1) {
echo (new Exception())->getTraceAsString()."\n";
return $acc;
}
return fac($n - 1, $acc * $n);
};
$fac_tr = tail_recursion('fac');
echo $fac_tr(10)."\n";The output is:
#0 tailrec_functional.php(27): fac()
#1 tailrec_functional.php(27): fac()
#2 tailrec_functional.php(27): fac()
#3 tailrec_functional.php(27): fac()
#4 tailrec_functional.php(27): fac()
#5 tailrec_functional.php(27): fac()
#6 tailrec_functional.php(27): fac()
#7 tailrec_functional.php(27): fac()
#8 tailrec_functional.php(27): fac()
#9 tailrec_functional.php(13): fac()
#10 tailrec_functional.php(32): {closure}()
#11 {main}
3628800
highlighting 10 stack frames are used.
While the gist linked:
<?php
class TailRecursion
{
public $func;
public $acc;
public $recursing;
public function tail()
{
return call_user_func_array($this->func, func_get_args());
}
public function getClosure($fn)
{
$this->acc = array();
$this->recursing = false;
$fn = $fn->bindTo($this);
return $this->func = function() use ($fn) {
$this->acc[] = func_get_args();
if ( ! $this->recursing) {
$this->recursing = true;
while ($this->acc) {
$ret = call_user_func_array($fn, array_shift($this->acc));
}
$this->recursing = false;
return $ret;
}
};
}
}
function tailrec($func)
{
$tail = new TailRecursion();
return $tail->getClosure($func);
}
$fac = tailrec(function($n, $acc = 1) {
if ($n == 1) {
echo (new Exception())->getTraceAsString()."\n";
return $acc;
}
return $this->tail($n - 1, $acc * $n);
});
echo $fac(10)."\n";produces:
#0 tailrecursion.php(27): Closure->{closure}()
#1 tailrecursion.php(53): TailRecursion->{closure}()
#2 {main}
3628800
Maybe a solution can be implemented using reflection and renaming the function?