这才是面试官想听的：详解「递归」正确的打开方式

最后一层节点的个数：2^n

没看懂？别慌，去 B 站/油管看我的视频讲解哦，搜「田小齐」就好了。

空间复杂度分析

一般书上写的空间复杂度是指：

算法运行期间所需占用的所有内存空间

但是在公司里大家常用的，也是面试时问的指的是
Auxiliary space complexity：

运行算法时所需占用的额外空间。

举例说明区别：比如结果让你输出一个长度为 n 的数组，那么这 O(n) 的空间是不算在算法的空间复杂度里的，因为这个空间是跑不掉的，不是取决于你的算法的。

那空间复杂度怎么分析呢？

我们刚刚说到了冯诺伊曼体系，从图中也很容易看出来，是最左边这条路线占用 stack 的空间最多，一直不断的压栈，也就是从 5 到 4 到 3 到 2 一直压到 1，才到 base case 返回，每个节点占用的空间复杂度是 O(1)，所以加起来总的空间复杂度就是 O(n).

我在上面的视频里也提到了，不懂的同学往上翻看视频哦～

优化算法

那我们就想了，为什么这么一个简简单单的运算竟然要指数级的时间复杂度？到底是为什么让时间如此之大。

那也不难看出来，在这棵 Recursion Tree 里，有太多的重复计算了。

比如一个 F(2) 在这里都被计算了 3 次，F(3) 被计算了 2 次，每次还都要再重新算，这不就是狗熊掰棒子吗，真的是一把辛酸泪。

那找到了原因之后，为了解决这种重复计算，计算机采用的方法其实和我们人类是一样的：记笔记。

对很多职业来说，比如医生、律师、以及我们工程师，为什么越老经验值钱？因为我们见得多积累的多，下次再遇到类似的问题时，能够很快的给出解决方案，哪怕一时解决不了，也避免了一些盲目的试错，我们会站在过去的高度不断进步，而不是每次都从零开始。

回到优化算法上来，那计算机如何记笔记呢？

我们要想求 F(n)，无非也就是要
记录 F(0) ~ F(n-1) 的值，
那选取一个合适的数据结构来存储就好了。

那这里很明显了，可以用之前讲过的 HashMap （没看过的点进去看哦）或者用一个数组来存：

那有了这个 cheat sheet，我们就可以从前到后得到结果了，这样每一个点就只算了一遍，用一个 for loop 就可以写出来，代码也非常简单。

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
        if (N== 1) {
            return 1;
        }
        int[] notes = new int[N+1];
        notes[0] = 0;
        notes[1] = 1;
        for(int i = 2; i <= N; i++) {
            notes[i] = notes[i-1] + notes[i-2];
        }
        return notes[N];
    }
}

这个速度就是 100% 了～

但是我们可以看到，空间应该还有优化的余地。

那仔细想想，其实我们记笔记的时候需要记录这么多吗？需要从幼儿园到小学到初中到高中的笔记都留着吗？

那其实每项的计算只取决于它前面的两项，所以只用保留这两个就好了。

那我们可以用一个长度为 2 的数组来计算，或者就用 2 个变量。

更新代码：

class Solution {
    public int fib(int N) {
        int a = 0;
        int b = 1;
        if(N == 0) {
            return a;
        }
        if(N == 1) {
            return b;
        }
        for(int i = 2; i <= N; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}

这样我们就把空间复杂度优化到了 O(1)，时间复杂度和用数组记录一样都是 O(n).

这种方法其实就是动态规划 Dynamic Programming，写出来的代码非常简单。

那我们比较一下 Recursion 和 DP：

Recursion 是从大到小，层层分解，直到 base case 分解不了了再组合返回上去；
DP 是从小到大，记好笔记，不断进步。

也就是 Recursion + Cache = DP

如何记录这个笔记，如何高效的记笔记，这是 DP 的难点。

有人说 DP 是拿空间换时间，但我不这么认为，这道题就是一个很好的例证。

在用递归解题时，我们可以看到，空间是 O(n) 在栈上的，但是用 DP 我们可以把空间优化到 O(1)，DP 可以做到时间空间的双重优化。

其实呢，斐波那契数列在现实生活中也有很多应用。

比如在我司以及很多大公司里，每个任务要给分值，1分表示大概需要花1天时间完成，然后分值只有1，2，3，5，8这5种，（如果有大于8分的任务，就需要把它 break down 成8分以内的，以便大家在两周内能完成。）
因为任务是永远做不完的而每个人的时间是有限的，所以每次小组会开会，挑出最重要的任务让大家来做，然后每个人根据自己的 available 的天数去 pick up 相应的任务。

披着羊皮的狼

那有同学可能会想，这题这么简单，这都 2020 年了，面试还会考么？

答：真的会。

只是不能以这么直白的方式给你了。

比如很有名的爬楼梯问题：

一个 N 阶的楼梯，每次能走一层或者两层，问一共有多少种走法。

这个题这么想：

站在当前位置，只能是从前一层，或者前两层上来的，所以 f(n) = f(n-1) + f(n-2).

这题是我当年面试时真实被问的，那时我还在写 python，为了炫技，还用了lambda function:

f = lambda n: 1 if n in (1, 2) else f(n-1) + f(n-2)

递归的写法时间复杂度太高，所以又写了一个 for loop 的版本

def fib(n)
  a, b = 1, 1
  for i in range(n-1):
 a, b = b, a+b
  return a 

然后还写了个 caching 的方法:

def cache(f):
 memo = {}
 def helper(x):
  if x not in memo:
   memo[x] = f(x)
  return memo[x]
 return helper
@cache
def fibR(n):
 if n==1 or n==2: return 1
 return fibR(n-1) + fibR(n-2)

还顺便和面试官聊了下 tail recursion:

tail recursion 尾递归：就是递归的这句话是整个方法的最后一句话。

那这个有什么特别之处呢？

尾递归的特点就是我们可以很容易的把它转成 iterative 的写法，当然有些智能的编译器会自动帮我们做了（不是说显性的转化，而是在运行时按照 iterative 的方式去运行，实际消耗的空间是 O(1)）

那为什么呢？

因为回来的时候不需要 backtrack，递归这里就是最后一步了，不需要再往上一层返值。

def fib(n, a=0, b=1):
 if n==0: return a
   if n==1: return b
 return fib(n-1, b, a+b)

最终，拿出了我的杀手锏：lambda and reduce

fibRe = lambda n: reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0, 1])

看到面试官满意的表情后，就开始继续深入的聊了...

所以说，不要以为它简单，同一道题可以用七八种方法来解，分析好每个方法的优缺点，引申到你可以引申的地方，展示自己扎实的基本功，这场面试其实就是你 show off 的机会，这样才能骗过面试官啊～lol