为什么这段代码的执行时间会超过30S

递归，循环太多，循环套递归，递归套循环。能不慢么。

远大于2的60次方次计算，30S就能出结果？不会吧。
能出结果已经很不错了。

60的fibonnaci sequence 运算30s 在php可以出结果。你的机器已经很牛了

@skyangel3 是飞播纳妾数列咩…

你用的这个算法是算法导论上用来做反面教材的。

这递归到死了吧

@Rojey
@casparchen
@skyangel3

虚拟主机跑到35行，自己的电脑还没试过。我以为是个小运算，很简单的加法。

@wizardoz 正确的是怎样？

建议你用银河或深蓝来跑这个程序

@kennedy32
改用循环写菲波纳锲算法

@luoyou1014 可以把一楼的代码改写一下么??

@kennedy32 这个是一个经典的死递归，从代码层次改变不了多少效率的

@kennedy32 用数组别用递归
*a= 1;
*(a+1) =1;
for(int i =2;i<=n;i++)
*(a+i) = *(a+i-1)+*(a+i-2);

@kennedy32

<?php
function tuzi($x){
$sum = 0;
$first=0;
$secOnd=1;
for($i=0;$i<$x;$i++){
$sum = $first + $second;
$first = $second;
$secOnd= $sum;
}
return $sum;
}

function testtuzi($n){
for ($i=0;$i<=$n;$i++){
echo "兔子在".$i."月的数目是".tuzi($i)."<br/>";
}
}
testtuzi(60);

算法概论第一章吧，就在讲fib的各种算法，更快的算法是用矩阵。最快的是这货：
long int fib(unsigned long int n) {
return lround((pow(0.5 + 0.5 * sqrt(5.0), n) -
pow(0.5 - 0.5 * sqrt(5.0), n)) /
sqrt(5.0));
}
参考：http://www.evanmiller.org/mathematical-hacker.html#HN_Repost

return tuzi($x-1)+tuzi($x-2);
这句话让你的代码变成了一个庞大的2叉树。。。n进去就是2的n-1次方！

因为这种二阶线性递归式直接写出来的话复杂度是exponential time的, 如果一定要递归的话可以用memoization. 所以说那些妄想速成码农就应该尽早砍掉重练, 回去撸一撸SICP和lambda calculus就知道踏实了.

ref: http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html

@TMBest 这货也只是理论上的最快，前提是sqrt与pow函数的运行时间较短

@TMBest 这个是直接套通项公式了吧？

楼主可以看看这个：http://blog.csdn.net/yuanjilai/article/details/8059580

斐波拉契数列，递归的方法存在太多的overlapping，大量重复计算，降低了效率

@TMBest 不是说正确做法是直接用lgamma函数么……

@skydiver 记错了。。那个是算阶乘。。

@Keita1314 额，我只看得懂php

@luoyou1014 谢谢

递归的复杂度不太乐观。

你用一个数组存储计算结果就可以了。算法不用改。

一种很肤浅的作法：
function tuzi($x){
static $result=array();
if(isset($result[$x])){
return $result[$x];
}
if($x == 0 || $x == 1){
$r= 1;
}else{
$r= tuzi($x-1)+tuzi($x-2);
}
$result[$x]=$r;
return $r;
}
functin testtuzi($n){
for ($i=0;$i<=$n;$i++){
echo "兔子在".$i."月的数目是".tuzi($i)."<br/>";
}
}
testtuzi(60);

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
14896 root 25 0 302m 9.9m 6948 R 100.0 0.5 1:07.71 php tuzi.php

php tuzi.php 11870.42s user 4.86s system 99% cpu 3:18:38.25 total
才跑到46

回答楼主的问题：

tuzi($x) 这个函数，里面用到了前两次的计算结果 tuzi($x-1) 和 tuzi($x-2)
但是，每次计算的结果并没有保存在什么地方，每次都是从头开始重新计算的

例如：要计算 tuzi(4)，
>>>> 需要先计算 tuzi(3) 和 tuzi(2)，分解为：
>>>>>>>> 计算 tuzi(3)：需要先计算 tuzi(2) 和 tuzi(1)
>>>>>>>>>> 计算 tuzi(2)：需要先计算 tuzi(1) 和 tuzi(0)
>>>>>>>>>>>> 计算 tuzi(1) 得 1
>>>>>>>>>>>> 计算 tuzi(0) 得 1
>>>>>>>>>> 计算 tuzi(1) 得 1
>>>>>>>> 计算 tuzi(2)：需要先计算 tuzi(1) 和 tuzi(0)
>>>>>>>>>> 计算 tuzi(1) 得 1
>>>>>>>>>> 计算 tuzi(0) 得 1

注意上面每一步计算都是独立的（因为之前的结果并没有保存起来供以后使用），比如 tuzi(2) 就分别计算了两次。

然后，比如 testtuzi 的循环里面，下一步假如开始要计算 tuzi(5)，需要计算 tuzi(4) 和 tuzi(3)，然后虽然上次循环里面 tuzi(4) 和 tuzi(3) 其实已经都算过了，但是不行，这一次里面还是得重新从头开始算。

@kuye 的方法是拿空间换时间的方法（如果我对 PHP 的 static 没理解错的话），拿很少的空间（那个 static array）保存了每次 tuzi($x) 计算的结果，大大提高了后面计算的速度。

@dorentus 非常感谢，最详细的解答

@kuye 改动最小的方案，谢谢。其实这是MIT600SC第六课递归的例子，能用递归当然最好了

能30s跑完这个代码的电脑都是神级的电脑了...
我的电脑还在慢慢跑，我看多久能跑完...

其实 LZ 是来秀电脑配置的。。。

楼上正解...

@levn 怎么插入github的这种格式化了的代码的？

@kofj 贴到gist.github.com

@dorentus
看到现在，只有你got point

这个问题，本质就是应该拿空间换时间。
有张表记录下每次计算的结果作为缓存，以后不用每次计算就可以了。

这个是大学作业吗？好像很久很久以前有人讨论过这个问题了，

用超算平台跑一遍试试

可以改成尾递归的... 或者直接改迭代

@vibbow
@pljhonglu
@hourui

E3 1230 v2 30s跑到36行

@kennedy32 你怎么做到那么快的？
我 i7-4930mx 跑到 testtuzi(36); 花了332秒...

@kennedy32 正确的应该是从底向上，从n = 1 累加到n = x。所以问题不在于用了递归调用，而是在于选了一种有很多冗余计算的算法。

@vibbow 我还觉得慢呢，虚拟主机都能跑35

你函数还没定义好，就内部调用。。。