最近看到好几篇博客，由fibnazzi数列引申出来的一些思考。
直接递归
public int headRecursiveFib(int n){
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
return headRecursiveFib(n - 1) + headRecursiveFib(n - 2);
}
上面的代码有几个弊端：
- 首先递归是一个栈式调用，如果n足够大，那么会导致stackoverflow异常。
- 递归调用会导致f(n)调用多次的问题，n越小调用次数越多，调用次数跟n的大小呈指数相关。
递归的优化版本
对于多次调用的问题，我们可以采取备忘录的形式，把每次计算出来的结果存起来，然后从备忘录中查询。过程----如果已经存在结果，则直接返回，否则才进行计算并把结果存进备忘录。
public int memFib(int n, int mem[]){
if (n == 0) {
mem[0] = 0;
return mem[0];
} else if (n == 1) {
mem[1] = mem[1];
return mem[1];
} else {
if (mem[n] > 0) {
return mem[n];
} else {
mem[n] = memFib(n-1, mem) + memFib(n - 2, mem);
return mem[n];
}
}
}
这是典型的以空间换时间的方式。
迭代版本
迭代解决方式比上面的备忘录版本更优，主要是提现在空间效率上，也不会有栈溢出的问题。
public int lineFib(int n){
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
int sumPre = 0;
int sum = 1;
for (int i = 2; i <= n; i++) {
int tmp = sum;
sum = sumPre + sum;
sumPre = tmp;
}
return sum;
}
头递归和尾递归
- 头递归表示在递归过程中，在执行其它代码之前就调用递归函数自身
- 尾递归表示在递归过程中，在执行其它代码后再调用函数自身。
下面是尾递归版本
public int tailRecursiveFib(int sum, int sumPre, int n) {
if (n == 1) {
return sum;
} else {
return tailRecursiveFib(sum + sumPre, sum, n - 1);
}
}
对比本文开头的函数，首先进行了计算 sum+sumPre,然后才调用函数自身。这种方式就是尾递归。
