PHP实现斐波那契数列，php斐波那契数列

PHP实现斐波那契数列，php斐波那契数列

在数学上，斐波纳契数列以如下被以递归的方法定义：
F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）

使用递归实现

很直观表示方式，用递归很容易实现：

function f($a)
{
    if ($a == 0 || $a == 1) {
        return 1;
    }
    return f($a-1) + f($a-2);
}

for($i = 0; $i < 70; ++$i)
{
    echo f($i).' ';
}

但是运行的时候，发现上面代码运行会超时：

递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解，容易编程。但递归是用栈机制实现的，每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上会以内存崩溃或超时而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。

那么如果非要用递归，有什么办法可以改进呢？

可以看到，在打印的过程中，比如求 f(6) 调用 f(5) 和 f(4)时，之前的某次循环其实已经算出来了 f(5) 和 f(4) ，不需要再算了。

可以使用一个数组，来保存之前的结果

function f($n, $arr)
{
    global $arr;
    if( isset($arr[$n]) ) {  //比 array_key_exits()效率高
        return $arr[$n];
    }
    return f($n-1, $arr) + f($n-2, $arr);
}
$arr = [
    0 => 1,
    1 => 1,
];
for($i = 0; $i < 1000000; ++$i)
{
    $arr[$i] = f($i, $arr);
    echo f($i, $arr).' ';
}

使用PHP7，打印1000000个也没有问题。

使用循环实现

<?php 
$arr[1] = 1;
for($i = 2;$i < 100;$i++)
{
    $arr[$i] = $arr[$i-1] + $arr[$i-2];
}
echo join(",",$arr);  //将数组合并为一个字符串输出
?>

非递归实现比递归效率高很多。

递归和循环的简单比较：

1、从程序上看，递归表现为自己调用自己，循环则没有这样的形式。
2、递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，并且简单的问题的解决思路和复杂问题一样，同时存在基准情况，就能最终求得问题，是逆向的。而循环是从简单问题出发，一步步的向前发展，最终求得问题，是正向的。
3、任意循环都是可以用递归来表示的，但是想用循环来实现递归（除了单向递归和尾递归），都必须引入栈结构进行压栈出栈。
4、一般来说，非递归的效率高于递归。而且递归函数调用是有开销的，递归的次数受堆栈大小的限制。