递归（Recursion）的两种优化方法
跳台阶问题
注意
递归在汇编层面来看，是一种特殊的循环。
平时解释递归，会说调用函数自己。其实实际执行时，当“调用自己”，就又重新分配了一块内存来保存相应数据，进行运算。
1.普通写法
1
2
3
4
5
6
7
8
9
| int Fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
}
else
{
return Fibonacci(n - 2) + Fibonacci(n - 1);
}
}
|
递归的缺点在于可能存在很多重复的操作，原因就不赘述了。一种优化方式就是避免这些重复的操作，用空间保存已计算的值，不再做重复的计算。
比较起递归的从后往前计算（要算 fn(n)，先算 fn(n-1)，fn(n-2)），这种方式是从前往后计算。
2.迭代法
1
2
3
4
5
6
7
8
9
10
11
12
| int Fibonacci(int n){
int sta[3] = {1,1,0};
if(n < 2){
return 1;
}
for(int i = 2; i <= n; i++){
dp[2] = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = dp[2];
}
return dp[2];
}
|
3.尾递归
用函数式编程能简单实现.(用 kawa 时写过.)
ps:尾递归就相当于迭代法吧……
1
2
3
| (let sum ((i 100))
(if (= i 0) 0
(+ (sum (- i 1)) i)))
|
1
2
3
4
5
6
| function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5, 1)
|