尾递归优化 trampoline
09 July 2018

在群里讨论的时候看到下面一道题

计算 x 的 y 次方

解法1

function f($x, $y)
{
    if ($y == 0) {
        return 1;
    }

    if ($y == 1) {
        return $x;
    }

    return $x * f($x, $y-1);
}

解法2:一个优化后的方法

function f($x, $y)
{
    if ($y == 0) {
        return 1;
    }

    if ($y == 1) {
        return $x;
    }

    if ($y % 2 == 0) {
        return f($x * $x, $y/2);
    } else {
        return $x * f($x * $x, $y/2);
    }
}

然后就有大神说,php 没有尾递归优化,过了一下又有大神抛出 PHP 7 magic function call trampoline
“尾递归优化的存在是防止调用栈爆了(个人理解)”,解法2按理来说不会存在调用栈爆了,这是一个 log2(n) 的解法

最后如下(实际上,这个没有尾递归优化,可以通过 ini_set('xdebug.max_nesting_level', VALUE) 来测试)

function f($x, $y)
{
    if ($y == 0) {
        return 1;
    }
    if ($y == 1) {
        return $x;
    }

    if ($y % 2 == 0) {
        return f($x * $x, $y/2);
    } else {
        return $x * f($x * $x, $y/2);
    }
}

function trampoline(callable $c, ...$args)
{
    while (is_callable($c)) {
        $c = $c(...$args);
    }

    return $c;
}

echo trampoline('f', 2, 7) . PHP_EOL; // 128