误区
之前在写递归相关的代码时候, 总是试图把调用一层层展开, 层数少的情况还能接受, 多了就烧脑, 不要试图用人脑去分解递归的每一个步骤
正确的思考方式
假设要完成 A , 可以分解为B、C、D 三个子问题, 可以假设B、C、D 已经解决, 在这基础上思考如何解决A
递归满足的条件
- 一个问题可以分解为几个子问题
- 分解后的子问题, 除了数据规模不同, 求解思路完全一样
- 存在递归终止条件
防止堆栈溢出
- 限制递归调用的最大深度 （最大深度比较小的情况下可以使用）
警惕重复计算
- 用hash表存储已经计算过的值
斐波那契数列
// 最简单的递归实现, 效率非常低, 存在大量重复计算
func fibonaci(num: Int) -> Int {
if num <= 0 { return 0 }
if num == 1 { return 1}
return fibonaci(num: num-1) + fibonaci(num: num-2)
}
// 使用 Dictionary 存储中间计算值
var cache : Dictionary<Int,Int> = [:]
func fibonaci(num: Int) -> Int {
if num <= 0 { return 0 }
if num == 1 { return 1}
if let value = cache[num] { return value }
let value = fibonaci(num: num-1) + fibonaci(num: num-2)
cache[num] = value
return value;
}
// 更简单的是从下往上计算, 时间复杂度是 O(n)
func fibonaci(num : Int) -> Int {
if num <= 0 { return 0 }
if num == 1 { return 1 }
var a = 1;
var b = 0;
var result = 0;
for _ in 2...num {
result = a + b; // result 存放计算过的值
b = a;
a = result;
}
return result;
}
青蛙跳台阶问题
一只青蛙可以跳上 1 级, 也可以跳 2级台阶, 如果青蛙跳上 n 级台阶有多少种跳法
分析得知: n = 1 有 1 种, n = 2 有2种, n > 2时, 可以看成第一次跳1级, 此时等于剩下 n - 1 台阶的跳法数目, 或者第一次跳 2 级, 此时等于剩下 n - 2 台阶数, 其实就是斐波那契数列, F(n) = F(n - 1) + F(n - 2)
