盒子
盒子
文章目录
  1. 注意
  2. 1.普通写法
  3. 2.迭代法
  4. 3.尾递归

关于递归

递归(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) // 120