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
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 8
function getNum($n) {
    $num = 0;
    $pre = 1;
    while ($n--) {
        $num += $pre;
        $pre = $num - $pre;
    }
    return $num;
}
5年前 评论

用循环写,递归太慢了

5年前 评论

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

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

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

    return $cache[$i];
}
5年前 评论

我也来贴一个

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;
}
5年前 评论

代码最下面的的耗时怎么得到的?

3年前 评论

@Sunnicholas 有个命令后工具叫做time

time php -a index.php
3年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!