关于java:一文学懂递归和动态规划

前言

大家好，这里是《齐姐聊算法》系列之递归和 DP 问题。

递归，是一个十分重要的概念，也是面试中十分喜爱考的。因为它岂但能考查一个程序员的算法功底，还能很好的考查对 工夫空间复杂度 的了解和剖析。

本文只讲一题，也是简直所有算法书讲递归的第一题，但力争讲出花来，在这里分享四点不一样的角度，让你有不同的播种。

• 时空复杂度 的详细分析
• 辨认并 简化 递归过程中的 反复 运算
• 披上羊皮的狼
• 适当炫技助我拿到第一份工作

算法思路

大家都晓得，一个办法本人调用本人就是递归，没错，但这只是了解递归的最表层的了解。

那么递归的 本质 是什么？

答：<span style=”color:blue”> 递归的本质是可能把一个大问题分解成比它小点的问题，而后咱们拿到了小问题的解，就能够用小问题的解去结构大问题的解。</span>

那小问题的解是如何失去的？

答：用再小一号的问题的解结构进去的，小到不能再小的时候就是到了零号问题的时候，也就是 base case 了。

那么总结一下递归的三个步骤：

Base case：就是递归的零号问题，也是递归的起点，走到最小的那个问题，可能间接给出后果，不用再往下走了，否则，就会成死循环；

拆解：每一层的问题都要比上一层的小，一直放大问题的 size，能力从大到小到 base case；

组合：失去了小问题的解，还要晓得如何能力结构出大问题的解。

所以每道递归题，咱们依照这三个步骤来剖析，把这三个问题搞清楚，代码就很容易写了。

斐波那契数列

这题虽是陈词滥调了，但置信我这里分享的肯定会让你有其余播种。

题目形容

斐波那契数列是一位意大利的数学家，他闲着没事去钻研兔子滋生的过程，钻研着就发现，能够写成这么一个序列：1，1，2，3，5，8，13，21… 也就是每个数等于它前两个数之和。那么给你第 n 个数，问 F(n) 是多少。

解析

用数学公式示意很简略：

$$f(n) = f(n-1) + f(n-2)$$

代码也很简略，用咱们刚总结的三步：

• base case: f(0) = 0, f(1) = 1.
• 合成：f(n-1), f(n-2)
• 组合：f(n) = f(n-1) + f(n-2)

那么写进去就是：

class Solution {public int fib(int N) {if (N == 0) {return 0;} else if (N == 1) {return 1;}
        return fib(N-1) + fib(N-2);
    }
}

然而这种解法 Leetcode 给出的速度教训只比 15% 的答案快，因为，它的工夫复杂度切实是太高了！

过程剖析

这就是我想分享的第一点，如何去剖析递归的过程。

首先咱们把这颗 Recursion Tree 画进去，比方咱们把 F(5) 的递归树画进去：

那理论的执行路线是怎么的？

首先是沿着最右边这条线一路到底：F(5) → F(4) → F(3) → F(2) → F(1)，好了终于有个 base case 能够返回 F(1) = 1 了，而后返回到 F(2) 这一层，再往下走，就是 F(0)，又触底反弹，回到 F(2)，失去 F(2) = 1+0 =1 的后果，把这个后果返回给 F(3)，而后再到 F(1)，拿到后果后再返回 F(3) 失去 F(3) = 左 + 右 = 2，再把这个后果返下来 …

这种形式实质上是由咱们计算机的 冯诺伊曼体系 造就的，目前 一个 CPU 一个核在某一时间只能执行一条指令，所以不能 F(3) 和 F(4) 一起进行了，肯定是先执行了 F(4)（本代码把 fib(N-1) 放在后面），再去执行 F(3).

咱们在 IDE 里 debug 就能够看到栈外面的状况：这里的确是先走的最右边这条线路，一共有 5 层，而后再一层层往上返回。

没看懂的小伙伴能够看视频解说哦～

完整版视频还请大家移步 B 站，搜寻「田小齐」「递归」，即可看到我的视频解说。

<video src=”../../2.%20%E5%85%AC%E4%BC%97%E5%8F%B7/5%20Recursion%20-%20Fib/%E5%8E%8B%E6%A0%88%E8%BF%87%E7%A8%8B%E8%AF%A6%E8%A7%A3.MP4″></video>

工夫复杂度剖析

如何评估一个算法的好坏？

很多问题都有多种解法，毕竟条条大路通罗马。但如何评估每种办法的优劣，咱们个别是用 大 O 表达式 来掂量 工夫和空间 复杂度。

工夫复杂度：随着自变量的增长，所需工夫的增长状况。

这里大 O 示意的是一个算法在 worst case 的体现状况，这就是咱们最关怀的，不然春运抢车票的时候零碎 hold 不住了，你跟我说这个算法很优良？

当然还有其余掂量工夫和空间的形式，比方

Theta: 形容的是 tight bound
Omega(n): 这个形容的是 best case，最好的状况，没啥意义

<span style=”color:blue”> 这也给咱们了些许启发，不要说你平时体现有多好，没有意义；面试掂量的是你在 worst case 的程度；不要说面试没有施展出你的实在程度，扎心的是那就是咱们的实在程度。

那对于这个题来说，工夫复杂度是多少呢？

答：因为咱们每个节点都走了一遍，所以是把 所有节点的工夫加起来 就是总的工夫。

在这里，咱们在每个节点上做的事件就是相加求和，是 O(1) 的操作，且每个节点的工夫都是一样的，所以：

总工夫 = 节点个数 * 每个节点的工夫

那就变成了求 节点个数 的数学题：

在 N = 5 时，

最下面一层有 1 个节点，
第二层 2 个，
第三层 4 个，
第四层 8 个，
第五层 16 个，如果填满的话，设想成一颗很大的树:)

这里就不要在意这个没填满的中央了，必定是会有差这么几个 node，然而大 O 表白的工夫复杂度咱们刚说过了，求的是 worst case.

那么总的节点数就是：
1 + 2 + 4 + 8 + 16

这就是一个等比数列求和了，当然你能够用数学公式来算，但还有个 小技巧 能够帮忙你疾速计算：

<span style=”color:blue”> 其实后面每一层的节点相加起来的个数都不会超过最初一层的节点的个数，总的节点数最多也就是最初一层节点数 * 2，而后在大 O 的工夫复杂度外面常数项也是无所谓的，所以这个总的工夫复杂度就是：

<span style=”color:blue”>

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

空间复杂度剖析

个别书上写的空间复杂度是指：

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

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

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

<span style=”color:blue”> 举例说明区别：比方后果让你输入一个长度为 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) 的值，
那选取一个适合的数据结构来存储就好了。

那这里很显著了，用一个数组来存：

那有了这个 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，写进去的代码非常简单。

<span style=”color:blue”> 那咱们比拟一下 Recursion 和 DP：

Recursion 是从大到小，层层合成，直到 base case 合成不了了再组合返回下来；
DP 是从小到大，记好笔记，不断进步。

也就是 Recursion + Cache = DP

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

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

在用递归解题时，咱们能够看到，空间是 O(n) 在栈上的，然而 <span style=”display:block;color:blue”> 用 DP 咱们能够把空间优化到 O(1)，DP 能够做到工夫空间的双重优化。</span>

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

比方在我司以及很多大公司里，每个工作要给分值，1 分示意大略须要花 1 天工夫实现，而后分值只有 1，2，3，5，8 这 5 种，（如果有大于 8 分的工作，就须要把它 break down 成 8 分以内的，以便大家在两周内能实现。）
因为工作是永远做不完的而每个人的工夫是无限的，所以每次小组会散会，挑出最重要的工作让大家来做，而后每个人依据本人的 available 的天数去 pick up 相应的工作。

披着羊皮的狼

<span style=”color:blue”> 那有同学可能会想，这题这么简略，这都 2020 年了，面试还会考么？

答：真的会。

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

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

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

这个题这么想：

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

这题是我当年面试时实在被问的，那时我还在写 python，为了炫技，<span style=”color:blue”> 还用了 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 

<span style=”color:blue”> 而后还写了个 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)

<span style=”color:blue”> 还顺便和面试官聊了下 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)

<span style=”color:blue”> 最终，拿出了我的杀手锏：lambda and reduce

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

看到面试官称心的表情后，就开始持续深刻的聊了 …

所以说，不要认为它简略，同一道题能够用七八种办法来解，剖析好每个办法的优缺点，引申到你能够引申的中央，展现本人扎实的基本功，这场面试其实就是你 show off 的机会，这样能力骗过面试官啊～lol

如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！

我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！

更多干货文章见我的 Github: https://github.com/xiaoqi6666…

前言

大家好，这里是《齐姐聊算法》系列之递归和 DP 问题。

递归，是一个十分重要的概念，也是面试中十分喜爱考的。因为它岂但能考查一个程序员的算法功底，还能很好的考查对 工夫空间复杂度 的了解和剖析。

本文只讲一题，也是简直所有算法书讲递归的第一题，但力争讲出花来，在这里分享四点不一样的角度，让你有不同的播种。

• 时空复杂度 的详细分析
• 辨认并 简化 递归过程中的 反复 运算
• 披上羊皮的狼
• 适当炫技助我拿到第一份工作

算法思路

大家都晓得，一个办法本人调用本人就是递归，没错，但这只是了解递归的最表层的了解。

那么递归的 本质 是什么？

答：<span style=”color:blue”> 递归的本质是可能把一个大问题分解成比它小点的问题，而后咱们拿到了小问题的解，就能够用小问题的解去结构大问题的解。</span>

那小问题的解是如何失去的？

答：用再小一号的问题的解结构进去的，小到不能再小的时候就是到了零号问题的时候，也就是 base case 了。

那么总结一下递归的三个步骤：

Base case：就是递归的零号问题，也是递归的起点，走到最小的那个问题，可能间接给出后果，不用再往下走了，否则，就会成死循环；

拆解：每一层的问题都要比上一层的小，一直放大问题的 size，能力从大到小到 base case；

组合：失去了小问题的解，还要晓得如何能力结构出大问题的解。

所以每道递归题，咱们依照这三个步骤来剖析，把这三个问题搞清楚，代码就很容易写了。

斐波那契数列

这题虽是陈词滥调了，但置信我这里分享的肯定会让你有其余播种。

题目形容

斐波那契数列是一位意大利的数学家，他闲着没事去钻研兔子滋生的过程，钻研着就发现，能够写成这么一个序列：1，1，2，3，5，8，13，21… 也就是每个数等于它前两个数之和。那么给你第 n 个数，问 F(n) 是多少。

解析

用数学公式示意很简略：

$$f(n) = f(n-1) + f(n-2)$$

代码也很简略，用咱们刚总结的三步：

• base case: f(0) = 0, f(1) = 1.
• 合成：f(n-1), f(n-2)
• 组合：f(n) = f(n-1) + f(n-2)

那么写进去就是：

class Solution {public int fib(int N) {if (N == 0) {return 0;} else if (N == 1) {return 1;}
        return fib(N-1) + fib(N-2);
    }
}

然而这种解法 Leetcode 给出的速度教训只比 15% 的答案快，因为，它的工夫复杂度切实是太高了！

过程剖析

这就是我想分享的第一点，如何去剖析递归的过程。

首先咱们把这颗 Recursion Tree 画进去，比方咱们把 F(5) 的递归树画进去：

那理论的执行路线是怎么的？

首先是沿着最右边这条线一路到底：F(5) → F(4) → F(3) → F(2) → F(1)，好了终于有个 base case 能够返回 F(1) = 1 了，而后返回到 F(2) 这一层，再往下走，就是 F(0)，又触底反弹，回到 F(2)，失去 F(2) = 1+0 =1 的后果，把这个后果返回给 F(3)，而后再到 F(1)，拿到后果后再返回 F(3) 失去 F(3) = 左 + 右 = 2，再把这个后果返下来 …

这种形式实质上是由咱们计算机的 冯诺伊曼体系 造就的，目前 一个 CPU 一个核在某一时间只能执行一条指令，所以不能 F(3) 和 F(4) 一起进行了，肯定是先执行了 F(4)（本代码把 fib(N-1) 放在后面），再去执行 F(3).

咱们在 IDE 里 debug 就能够看到栈外面的状况：这里的确是先走的最右边这条线路，一共有 5 层，而后再一层层往上返回。

没看懂的小伙伴能够看视频解说哦～

完整版视频还请大家移步 B 站，搜寻「田小齐」「递归」，即可看到我的视频解说。

<video src=”../../2.%20%E5%85%AC%E4%BC%97%E5%8F%B7/5%20Recursion%20-%20Fib/%E5%8E%8B%E6%A0%88%E8%BF%87%E7%A8%8B%E8%AF%A6%E8%A7%A3.MP4″></video>

工夫复杂度剖析

如何评估一个算法的好坏？

很多问题都有多种解法，毕竟条条大路通罗马。但如何评估每种办法的优劣，咱们个别是用 大 O 表达式 来掂量 工夫和空间 复杂度。

工夫复杂度：随着自变量的增长，所需工夫的增长状况。

这里大 O 示意的是一个算法在 worst case 的体现状况，这就是咱们最关怀的，不然春运抢车票的时候零碎 hold 不住了，你跟我说这个算法很优良？

当然还有其余掂量工夫和空间的形式，比方

Theta: 形容的是 tight bound
Omega(n): 这个形容的是 best case，最好的状况，没啥意义

<span style=”color:blue”> 这也给咱们了些许启发，不要说你平时体现有多好，没有意义；面试掂量的是你在 worst case 的程度；不要说面试没有施展出你的实在程度，扎心的是那就是咱们的实在程度。

那对于这个题来说，工夫复杂度是多少呢？

答：因为咱们每个节点都走了一遍，所以是把 所有节点的工夫加起来 就是总的工夫。

在这里，咱们在每个节点上做的事件就是相加求和，是 O(1) 的操作，且每个节点的工夫都是一样的，所以：

总工夫 = 节点个数 * 每个节点的工夫

那就变成了求 节点个数 的数学题：

在 N = 5 时，

最下面一层有 1 个节点，
第二层 2 个，
第三层 4 个，
第四层 8 个，
第五层 16 个，如果填满的话，设想成一颗很大的树:)

这里就不要在意这个没填满的中央了，必定是会有差这么几个 node，然而大 O 表白的工夫复杂度咱们刚说过了，求的是 worst case.

那么总的节点数就是：
1 + 2 + 4 + 8 + 16

这就是一个等比数列求和了，当然你能够用数学公式来算，但还有个 小技巧 能够帮忙你疾速计算：

<span style=”color:blue”> 其实后面每一层的节点相加起来的个数都不会超过最初一层的节点的个数，总的节点数最多也就是最初一层节点数 * 2，而后在大 O 的工夫复杂度外面常数项也是无所谓的，所以这个总的工夫复杂度就是：

<span style=”color:blue”>

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

空间复杂度剖析

个别书上写的空间复杂度是指：

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

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

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

<span style=”color:blue”> 举例说明区别：比方后果让你输入一个长度为 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) 的值，
那选取一个适合的数据结构来存储就好了。

那这里很显著了，用一个数组来存：

那有了这个 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，写进去的代码非常简单。

<span style=”color:blue”> 那咱们比拟一下 Recursion 和 DP：

Recursion 是从大到小，层层合成，直到 base case 合成不了了再组合返回下来；
DP 是从小到大，记好笔记，不断进步。

也就是 Recursion + Cache = DP

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

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

在用递归解题时，咱们能够看到，空间是 O(n) 在栈上的，然而 <span style=”display:block;color:blue”> 用 DP 咱们能够把空间优化到 O(1)，DP 能够做到工夫空间的双重优化。</span>

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

比方在我司以及很多大公司里，每个工作要给分值，1 分示意大略须要花 1 天工夫实现，而后分值只有 1，2，3，5，8 这 5 种，（如果有大于 8 分的工作，就须要把它 break down 成 8 分以内的，以便大家在两周内能实现。）
因为工作是永远做不完的而每个人的工夫是无限的，所以每次小组会散会，挑出最重要的工作让大家来做，而后每个人依据本人的 available 的天数去 pick up 相应的工作。

披着羊皮的狼

<span style=”color:blue”> 那有同学可能会想，这题这么简略，这都 2020 年了，面试还会考么？

答：真的会。

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

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

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

这个题这么想：

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

这题是我当年面试时实在被问的，那时我还在写 python，为了炫技，<span style=”color:blue”> 还用了 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 

<span style=”color:blue”> 而后还写了个 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)

<span style=”color:blue”> 还顺便和面试官聊了下 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)

<span style=”color:blue”> 最终，拿出了我的杀手锏：lambda and reduce

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

看到面试官称心的表情后，就开始持续深刻的聊了 …

所以说，不要认为它简略，同一道题能够用七八种办法来解，剖析好每个办法的优缺点，引申到你能够引申的中央，展现本人扎实的基本功，这场面试其实就是你 show off 的机会，这样能力骗过面试官啊～lol

如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！

我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！

更多干货文章见我的 Github: https://github.com/xiaoqi6666…