@chyoo1991
2015-09-07T01:17:30.000000Z
字数 544
阅读 1360
coding
斐波那契数列
见书73页。
此处重新复习了下递归和迭代的不同。
递归写起来比较简洁。但是,因为递归是不断调用函数,调用函数要入栈出栈一些局部变量、函数返回地址等。这样上下文的切换,会带来过多的时间开销。而且会带来另一个问题:栈溢出。因此相同条件下会比循环的效率低很多。
public class Fib {
public static int fb(int n){
if(n <= 0) //注意小于0的情况
return 0;
if(n == 1) //递归出口
return 1;
return fb(n - 1) + fb(n - 2);
}
}
这种写法会造成很多函数的重复调用,性能很低。实际上可以把中间结果保存起来,通过查取而不是继续调用函数迭代的方式解决。
public class Fib {
public static long fb(int n){
if(n <= 0)
return 0;
if(n == 1)
return 1;
long pre = 0;
long cur = 1;
for(int i = 2; i <= n; i++) {
long tmp = pre + cur;
pre = cur;
cur = tmp;
}
return cur;
}
}
注意青蛙跳台阶的问题,就是用斐波那契数列来解决的。另有方块覆盖的问题,也是斐波那契数列来解决。