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