5000字彻底搞明白 递归

下载第1-第4周 周报pdf版 请移步星球

本周算法刷题集中递归专题，下面是从我的知识星球里选取的星友们的精华回答，推送在公众号里，希望能真正帮助到更多朋友。如果你对算法感兴趣，欢迎加入我的星球（扫描文末二维码），只有几十块钱，收益却是无价的，每天成长都是可见的。

Day 25：递归求斐波那契数列前 N 项

先总结 Day 24 作业题，再布置 Day 25 作业题。

Day 24 作业总结

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

已知杨辉三角第 i-1行，生成第 i 行为：

[1] + 
[yanghui[-1][i-1] + yanghui[-1][i] for i in range(1, numRows-1)] + 
[1]

完整代码：

class Solution():
 def generate(self, numRows):
  if numRows == 0:
   return []
  elif numRows == 1:
   return [[1]]
  else: # 调用自身生成前 numRows - 1 行的杨辉三角
   yanghui = self.generate(numRows - 1) 
      # 根据倒数第二行再生成最后一行：
      last_row = [1] + [yanghui[-1][i-1] + yanghui[-1][i] for i in range(1, numRows-1)] + [1]
   yanghui.append(last_row)
  return yanghui

递归总结

在实现递归函数之前，有件重要的事情需要解决：找出递推关系。

Day25 作业

下面再进一步，学习递归的其他知识。

通常情况下，递归是一种直观而有效的实现算法的方法。但是，如果使用不合理，会造成大量的重复计算。那么，你有什么办法能消除某些重复计算呢？通过求斐波那契数问题，体会如何消除递归计算中的重复计算问题。

def fib(self, N):
    pass

补全以上代码，返回斐波那契数列前 N 项。

Day 26：现实中，一名算法工程师的日常是什么？

总结 Day 25 作业题

通常情况下，递归是一种直观而有效的实现算法的方法。但是，如果使用不合理，会造成大量的重复计算。

例如求斐波那契数问题时，参考星友 infrared62 的解释：Fibonacci Number，使用递归来解，首先如果直接递归会用很多重复子问题计算，画完二叉树会发现是指数级的时间复杂度，每一层的计算比上一层多2倍。

下面的树显示了在计算 时发生的所有重复计算（按颜色分组）。

那么，你有什么办法能消除某些重复计算呢？很自然的一个想法，将中间结果存储在缓存中，以便以后可以重用它们，而不需要重新计算。

这是一种经常与递归一起使用的技术。

通过求斐波那契数问题，体会如何消除递归计算中的重复计算问题。

具体代码实现：

def fib(self, N):
    history = {}
    def recur(N):
        if N in history:
            return history[N]
        if N < 2:
            result = N
        else:
            result = recur(N-1) + recur(N-2)
        history[N] = result
        return result

    return recur_fib(N)

补全以上代码，返回斐波那契数列前 N 项。

星友 infrared62 还提出一个缓存的方法：在Python中也可以用语言特性 @lru_cache 来自动缓存。

代码参考下面：

Day 26 ：现实中，一名算法工程师的日常是什么？

如果你是学生，还未毕业工作，你可能会畅想着将来成为一名算法工程师，看起来高大上，待遇各方面都不错。那么现实中，一名算法工程师的日常又是什么呢？你可以想象一下然后打卡。如果你是算法工程师，那么平时大部分时间在做什么，也欢迎打卡留言。

Day 27：如何分析递归的时间复杂度？

总结 Day 26 作业

作业题：现实中，一名算法工程师的日常是什么？

首先，大概看下算法工程师日常做什么：

算法工程师的日常 星友 LFeng 回答

业务场景分析 需求分析 数据处理 建模 调试 应用 反馈调整 总结报告等 ”

这个总结很精炼。

参考星友 箱子 回答

我感觉算法工程师有相当一部分时间是在处理数据。算法工程师也是为项目服务，项目也是为最后的解决方案服务，解决方案也是为了解决现实生活中的实际问题。为了让现实生活中数据呈现出背后隐藏的信息或者趋势，才需要一个算法来支撑，但是我们能得到的却是杂乱无章的东西。整理数据，优化数据结构，我感觉也需要很多的工作量。 ”

具体来说，参考星友 北方 回答

借鉴于知乎 1.对接业务方，第一个步骤是去和业务方进行对接，对接的过程中要去了解业务方的需求，业务的真实痛点，很多时候对接的业务方并不了解算法能做哪些事情，因此，在对接的过程中业务方会提自己想要的目标是什么，而此时算法工程师需要凭借经验去评估这个方向的业务价值，评估这个方向是否适合算法来做，现在是否是切入的好时机。 ”

2.数据的盘点，对于算法来说，数据的重要性不言而喻，很多时候调半个月的参数，模型的效果都不如引入一份高质量数据来得效果好。阿里算是数据的基础设施做的很好的一家公司，数据在不同平台的流转工作相对方便，另外阿里也有很多基础数据，然而，实际在工作的过程中还是时常会碰到没有数据，或者数据质量不佳的情况，在这种情况下一方面需要对数据做出大量预处理的工作，另一方面，需要去思考如何依赖现有数据对模型进行评估，进而去评估业务效果。 ”

3.建模，包括以什么样的思路去解决这个问题，预测模型效果增益，特征抽取，特征处理，选用何种模型，效果评估，模型迭代，这部分可能是在我的人之中算法工程师的工作，而在实际工作中，这部分工作如果能占用30%的精力，已经是很高的比例了。 ”

4.模型上线，取决于依赖何种上线方式，有的时候很简单，可能产出的结果只是一张结果表，业务方下游直接引用即可，有的时候涉及到大量的工程工作，需要考虑模型的性能，复杂度。延时，可解释性什么的也会需要去进行考虑。 ”

这四个过程中就是算法的日常工作，精力分配大概是30%，10%，30%，30%，这只是一个毛估估的精力分配比例，有可能一两周都是处于和业务方开会过程中，也有可能某一个小项目从头到尾都比较确认，直接当天就能从第一步走到第四步。 ”

这个回答，确实很中肯。

算法工程师需要具备的能力，可以大概参考星友：孙颖颍穎颕頴 的回答：

举我的例子 一名合格的图像处理算法工程师 不但要有扎实的计算机基础 什么c++和python是必须要熟练使用的 还有一些深度学习的框架如tf torch 还有一些图像处理的算法 opencv等等 然后就是细分方向了 人脸识别 目标检测等等 在学校还是以学术复现顶会论文为主 出学校就是根据自己的方向从事相关的工作吧 解决问题 根据项目要求设计模型 优化模型 在项目上有想法就发发专利和论文 感觉算法工程师重在idea吧 挺难的。 ”

大家一步一步来，慢慢掌握

Day 27 作业题 ：递归的时间复杂度分析

大家参考下面网址：

https://leetcode-cn.com/explore/orignial/card/recursion-i/259/complexity-analysis/1222/

回答一个问题：如何分析递归的时间复杂度？

Day 28 ：0-1背包问题

先总结 Day 27 作业题

递归确实能让代码变得更加简洁，让代码看起来更加优美，但是稍不留神，就会写出时间复杂度为指数级的代码。所以使用递归，必须要留意时间复杂度分析。

昨天推荐的参考网址：

https://leetcode-cn.com/explore/orignial/card/recursion-i/259/complexity-analysis/1222/

里面主要讲到两类时间复杂度分析，一种以相反顺序打印字符串的递归，这种时间复杂度的求解较为直观，因为每次问题规模 都会缩减 ，并且每次只打印 个字符，故时间复杂度为：

但是，以求解裴波那契数列为代表的递归，时间复杂度的求解就不那么直观了，文中给出一个很好的求解示意图：

因为递归的方程：

以求解数列前 4 项为例，在求解 f(4) 是需要求解出 f(3) 和 f(2)，求解 f(3) 时又需要求解 f(2) 和 f(1)，以此类推。

整个过程可以绘制为下图的二叉树：

我们知道二叉树模型的节点个数与层数的关系为指数次幂，所以递归的时间复杂度为：

如果不做优化，时间复杂度为指数级的算法基本是难解，或者不是一个真正意义上的可行解， 就已经是一个很恐怖的数字：

所以使用递归再次告诉我们：记忆化技术或称为缓存技术的重要性。

以上就是两类典型的递归时间复杂度。

Day 28：0-1背包

0-1 背包是一个经典的组合优化问题，其中的思想非常重要。今天我们以一个简单的例子，先来体会 0-1 背包问题。

有一个最大承重量为w的背包，第i件物品的价值为a1[i]，第i件物品的重量为a2[i]，将物品装入背包，求解背包内最大的价值总和可以为多少？

例子：

a1 = [100, 70, 50, 10], a2 = [10, 4, 6, 12], w = 12, 背包内的最大价值总和为 120，分别装入重量为4和6的物品，能获得最大价值为 120

补全下面代码，返回求解的最大价值：

def f(a1,a2,w):
    pass

Day 29 ：递归求解 0-1 背包问题

本周专题：学习递归，所以昨天作业题0-1背包也是基于递归的一类问题，只不过带有动态规划，动态转移方程，这些我们后面会重点讲解。

再理解下0-1背包问题：

有一个最大承重量为w的背包，第i件物品的价值为a1[i]，第i件物品的重量为a2[i]，将物品装入背包，求解背包内最大的价值总和为多少？

例子：

价值数组：a1 = [100, 70, 50, 10],

重量数组：a2 = [10, 4, 6, 12],

背包最大可载重量：W = 12

结果：背包内的最大价值总和为 120，分别装入重量为 4 和 6 的物品，能获得最大价值为 120

如何计算机编写代码求出这类问题，返回求解的最大价值。

分析过程：

如下图所示：

第一行物品价值

第二行物品重量

我们从最右侧开始决策是否装入重量为12的物品：

背包可装最大重量恰好为 12

• 1. 如果选择装入此物品，背包内物品价值为 10，并且已经不能再装入，因此得到一种可行解：价值为 10
• 1. 如果选择不装入，我们的视线移动到下一个物品决策上，同样地我们会面临装入还是不装入的两个可选择项：

如果选择装入，创造 50 价值，并且还能最多装入重量为6的物品：

以此类推。

你看，无论何时，当视线移动到下一个物品时，我们都会面临装还是不装的问题，称此类问题为：

0-1 背包问题

以上过程转化为如下求解代码：

a1 = [100, 70, 50, 10]
a2 = [10, 4, 6, 12]
W = 12


def f(i, w):
    # 基本情况：
    if w == 0 or i < 0:
        return 0
    elif a2[i] > w:
        return f(i-1, w)
    # 递归：
    return max(a1[i] + f(i-1, w-a2[i]),
               f(i-1, w))


r = f(3, W)
print(r) # 120

基本情况包括：

1. 背包可装载重为 0 时，表明它不能再装物品了，自然价值为 0
2. i < 0 表明没有物品可装入了，自然价值也为 0
3. 当 a2[i] > w 时，表明此物品太重，背包剩余空间装载不下，表明此物品不能装入背包，我们的视线自动移动到下一个物品，即返回：f(i-1,w)

递归情况：到这里表明，a2[i] 能装入背包，就看我们是否选择它：0-1 选择问题：

装：a1[i] + f(i-1, w-a2[i])，产生 a1[i] 大小的价值，代价背包剩余空间变小，还能装载 w-a2[i]

不装：f(i-1, w)

决策：选择较大的

以上问题递归树的完整示意图如下：

Day 29 :复习 0-1 背包问题

如果觉得昨天作业不好理解，或者之前拉下作业的星友，借助Day29的机会弥补一下。已经全都搞定的星友，Day29放松一下吧。

Day 30 ：理解递归的特例：尾递归

0-1 背包问题的递归解法有些星友理解起来有些困难，所以Day29我们放慢脚步，单独留出这一天好好理解背包问题。

算法的魅力：它会让你念念不忘，几天后必有回响，然后编程水平就会提升一个小小的 level

今天我去油管上翻阅一下0-1背包讲解视频，觉得下面这个讲解较为形象，特意再在这里帖一下：

图1(左上角)：背包问题示意图

图2：待求解问题，例子

图3：求解表格，这是动态规划的求解，不是我们这周训练的递归的求解方法。现在这里提一下动态规划，后面会重点讲到。

图4：全部求解完成

图5：检验价值7如何得来的

图6：最后选择放置到背包里的三个物品，绿颜色表示：

Day 30 尾递归

使用递归会使代码变得非常简洁，但是递归利用不慎，很容易就会出现：stack overflow 栈溢出的问题，这是因为通常的递归也需要消耗在系统调用栈上产生的隐式额外空间，这算是我们使用递归所付出的代价。

但是有一类递归非常特殊，它不受此空间开销的影响。它就是一种特殊的递归情况：尾递归。

那么，满足哪些条件才算是尾递归呢？下面的两种代码示例，哪个是尾递归，哪个是一般的递归情况呢？

写法1：

def sum:1(ls):
    if len(ls) == 0:
        return 0
    return ls[0] + sum1(ls[1:])

写法2：

def sum2(ls):
    def helper(ls, acc):
        if len(ls) == 0:
            return acc
        return helper(ls[1:], ls[0] + acc) 
    return helper(ls, 0)

Day 31：使用递归快速幂算法：Pow(x,n)

总结 Day30 尾递归作业

递归调用是递归函数中的最后一条指令。并且在函数中应该只有一次递归调用。

大家注意：最后一行语句和最后一条指令的区别:

下面代码中sum1函数最后一条语句也是sum1函数，但是最后一条指令显然是加法操作。所以它不是尾递归！

def sum1(ls):
    if len(ls) == 0:
        return 0
    return ls[0] + sum1(ls[1:])

下面函数sum2中的子函数helper的最后一条指令也是helper，所以它是尾递归：

def sum2(ls):
    def helper(ls, acc):
        if len(ls) == 0:
            return acc
        return helper(ls[1:], ls[0] + acc) 
    return helper(ls, 0)

总结：非尾递归中，在最后一次递归调用之后有一个额外的计算。

Day 31 作业题

求 x 的 n 次幂，一般解法时间复杂度为：O(n)，你能使用递归写出 O(logn) 的解法吗？

补全如下代码，返回 x 的 n 次幂：

def pow(x,n):
    pass