《iOS面试题整理》 - 递归

误区

之前在写递归相关的代码时候, 总是试图把调用一层层展开, 层数少的情况还能接受, 多了就烧脑, 不要试图用人脑去分解递归的每一个步骤

正确的思考方式

假设要完成 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)