PHP 与斐波那契数列

三种方式实现斐波那契数列

普通递归实现

function fibonacci_recursive($n) {
    if ($n <= 1) {
        return 1;
    }

    return fibonacci_recursive($n - 1) + fibonacci_recursive($n - 2);
}

for ($i = 1; $i <= 30; $i++) {
   echo fibonacci_recursive($i) . "  ";
}

耗时
3.52s user 0.00s system 99% cpu 3.521 total

递归优化,增加内存缓存

function fibonacci_recursive_optimization($n) {
    static $caches_arr = [];

    if (isset($caches_arr[$n])) {
        return $caches_arr[$n];
    }

    if ($n <= 1) {
        $res = 1;
    } else {
        $res = fibonacci_recursive_optimization($n - 1) + fibonacci_recursive_optimization($n - 2);
    }

    $caches_arr[$n] = $res;

    return $res;
}

for ($i = 1; $i <= 30; $i++) {
    echo fibonacci_recursive_optimization($i) . "  ";
}

耗时
0.01s user 0.01s system 98% cpu 0.022 total

闭包实现

function fibonacci_closure() {
    static $x = 0;
    static $y = 1;
    return function () use (&$x, &$y) {
        [$x, $y] = [$y, $x + $y];
        return $y;
    };
}

$f = fibonacci_closure();
for ($i = 1; $i <= 30; $i++) {
    echo $f() . " ";
}

耗时
0.02s user 0.01s system 99% cpu 0.030 total
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 6

还有更好的方法

7个月前

@rufo 欢迎贴出来实现

7个月前
function getNum($n) {
    $num = 0;
    $pre = 1;
    while ($n--) {
        $num += $pre;
        $pre = $num - $pre;
    }
    return $num;
}
7个月前
Zerin

用循环写,递归太慢了

4个月前

带缓存的这样写我觉得好看一点 。:)

function recursionCache($i)
{
    static $cache = [
        1 => 1,
        2 => 1,
    ];

    if (!isset($cache[$i])) {
        $cache[$i] = recursionCache($i - 2) + recursionCache($i - 1);
    }

    return $cache[$i];
}
3个月前

我也来贴一个

function recursionCache($i)
{
    $f = 0;
    $g = 1;
    // f(n) = f(n+1) - f(n-1)
    while ($i > 0) {
        $g += $f;
        $f = $g - $f;
        $i--;
    }

    return $f;
}
3个月前

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!