使用递归实现 fibonacci 函数。所谓 fibonacci 函数，就是输入 n，输出 fibonacci 队列的第 n 项。

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 2622 天前的主题，其中的信息可能已经有所发展或是发生改变。

<?php

$time1= microtime();
//普通递归
function fib($n)
{
    if ($n < 2) {
        return 1;
    }
    return fib($n - 1) + fib($n - 2);
}

echo fib(30);
echo PHP_EOL;
echo microtime()-$time1;
echo PHP_EOL;
$time2 = microtime();
//缓存  空间换时间
function fib2($n)
{
    $tmp = [];
    if (isset($tmp[$n]) && $tmp[$n] != 0)
        return $tmp[$n];

    if ($n < 2) {
        $tmp[$n] = 1;
        return 1;
    } else {
        $tmp[$n] = fib2($n - 1) + fib2($n - 2);
        return $tmp[$n];
    }
}

echo fib2(30);
echo PHP_EOL;
echo microtime()-$time2;
echo PHP_EOL;
$time3 = microtime();

//尾递归
function fib3($a, $b ,$n)
{
    if ($n == 0) {
        return $a;
    } else {
        return fib3($a+$b, $a, $n-1);
    }
}
echo fib3(1, 0 , 30);
echo PHP_EOL;
echo microtime()-$time3;

在数据量比较大的情况下尾递归的效率就超级高啦

5 条回复 • 2017-02-28 11:54:38 +08:00

geeti

2017-02-28 04:27:02 +08:00

what's the point?

rannnn

2017-02-28 05:34:19 +08:00

用矩阵快速幂可以 O(logN)

justudy

2017-02-28 09:13:27 +08:00

@rannnn #2 嗯这个应该是最优的，敢请大神展示代码

LukeXuan

2017-02-28 11:47:50 +08:00

If you insist.

function matrix_mult_2_2($a, $b) {
$c = [
[$a[0][0] * $b[0][0] + $a[0][1] * $b[1][0], $a[0][0] * $b[0][1] + $a[0][1] * $b[1][1]],
[$a[1][0] * $b[0][0] + $a[1][1] * $b[1][0], $a[1][0] * $b[0][1] + $a[1][1] * $b[1][1]],
];
return $c;
}

function optimized_fib($n) {
$vector = [1, 1];

$result = [
[1, 0],
[0, 1]
];

$base = [
[1, 1],
[1, 0]
];

while ($n > 0) {
if ($n % 2) {
$result = matrix_mult_2_2($result, $base);
}
$base = matrix_mult_2_2($base, $base);
$n = $n / 2;
}
return $result[1][0];
}

在 n >= 10000 的时候会体现出优势。

justudy

2017-02-28 11:54:38 +08:00

@LukeXuan #4 看来要把数学书翻出来看看了