关于“斐波那契数列”的编程

今天上网看到一个有关“斐波那契数列”的数学概念。自己学习编程时间也不短了，就借这个东东练习一下。

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）（来自百度）

一开始，我编程的代码如下：

function fbnq($num) {

if ($num == 0) {

return 0;

}elseif ($num== 1) {

return 1;

}else {

return fbnq($num-2) + fbnq($num-1);

}

}

$total = 10;

$arr = array();

for ($i=0;$i <$total ;$i++) {

$arr[$i] = fbnq($i);

echo $i. '--->' . $arr[$i] . '<br>';

}

编好以后，我想OK了，结果把$tatal改到25以后就发现运行越来越慢了。运行到30秒程序就提示运行时间太长了。可能是函数设计的效率问题。因为一开始我考虑用递归，n大于3以后，每个数都要通过递归来获得。越往后，递归次数越多。实际上，根本不需要用到递归。只需要取前面已经做好的运算结果相加就好了。于是，改为以下代码，$tata改为100也没问题了：

function fbnq($num) {

global $arr;

if ($num == 0) {

return 0;

}elseif ($num== 1) {

return 1;

}else {

return $arr[$num-2] + $arr[$num-1];

}

}

$total = 100;

$arr = array();

for ($i=0;$i <$total ;$i++) {

$arr[$i] = fbnq($i);

echo $i. '--->' . $arr[$i] . '<br>';

}