Skip to content

Instantly share code, notes, and snippets.

@beberlei
Forked from pkriete/gist:2425817
Created November 25, 2012 21:25
Show Gist options
  • Star 8 You must be signed in to star a gist
  • Fork 6 You must be signed in to fork a gist
  • Save beberlei/4145442 to your computer and use it in GitHub Desktop.
Save beberlei/4145442 to your computer and use it in GitHub Desktop.
PHP Tail Recursion
<?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) {
return $acc;
}
return $this->tail($n - 1, $acc * $n);
});
echo $fac(4); // 1 * 2 * 3 * 4 = 24
@pyldin601
Copy link

pyldin601 commented Oct 22, 2016

I optimized your version and done it without classes:
https://gist.github.com/pldin601/8de8e0c7f1288676ea0e451886799833

Just function that decorates other function. Works awasome.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment