很多时候，大家都在思考递归在数学上面应该如何表示了，毕竟对于数学的简单理解比起我们直接写代码起来还是要简单很多的。观察递归，我们会很容易发现递归的数学模型类似于数学归纳法，这个在高中的数列里面就已经开始应用了。数学归纳法常见的描述如下最简单和常见的数学归纳法是证明当 n 等于任意一个自然数时某命题成立。证明分下面两步：证明当 n= 1 时命题成立。假设 n=m 时命题成立，那么可以 推导出在 n=m+1 时命题也成立。（m 代表任意自然数）数学归纳法适用于将需要解决的原问题转换为解决他的子问题，而其中的子问题又可以变成子问题的子问题，而且这些问题都是同一个模型，可以用相同的处理逻辑归纳处理。当然有一个是例外的，就是归纳结束的那一个处理方法不能适用于其他的归纳处理项。递归同样的是将大的问题分解成小问题处理，然后会有一个递归的终止条件，满足终止条件之后开始回归。数学里面有一个很有名的斐波那契数列，我们在编程求解斐波那契数列的时候就会用到递归的思想，在后续的内部中会具体讲到。

递归（Recursion），是计算机科学与技术领域中一种常见的算法思想。在数学和计算机领域中，递归主要是指在函数的定义中使用函数自身的方法。顾名思义，递归主要包含两个意思，递和归，这个是递归思想的精华所在。递归就是有去（递去）有回（归来）。“有去” 是指递归问题可以分解成若干个规模较小、与原问题形式相同的子问题，这些子问题可以和原问题用相同的方法来求解。“有回” 是指这些问题的演化过程是一个从大到小，并且最终会有一个明确的终点，一旦达到终点，就可以从终点原路返回，解决原问题。更为直接的说法就是：递归的基本思想就是把大问题转化为相似的小问题解决。特别是在程序中的函数实现时，大问题的解决方案和小问题是一模一样的，所以就产生解决一个问题会调用函数本身的情况，这个也是递归的定义。

本节将会以 3 个有意思的 leetcode 编程题来实践递归算法，帮助大家更加深刻理解和掌握递归算法。

递归算法，通常是把一个大型复杂的问题，一次次通过递归调用而层层转化为一个与原问题相似的规模较小的问题来求解，基本思想是将大问题一步步化为小问题，递归算法只需少量的程序就可表达对大问题的计算过程所需要的多次重复计算，大大地减少了程序代码。从代码的角度上来看就是函数调用自身，我们称之为递归。

在日常的生活学习中，递归算法一般可以用来解决很多实际问题。回顾一下我们之前学习的排序算法，其中快速排序利用了递归的思想进行解决。总而言之，递归在很多场景中都有应用。比如说一个常见的对于操作系统里面删除指定路径下的文件夹里内容以及子文件夹里面内容的操作，就可以利用递归思想完成。这个时候递归的终止条件就是判断当前路径是文件，就可以直接删除；发现当前路径是文件夹，则递归调用方法，进入文件夹内部删除里面的文件内容。总而言之，递归问题在现实学习科研中经常会遇到，这是一种解决问题的思路与方法，将大问题拆分成小问题，然后求解小问题之后回归归纳，得出整个问题的求解结果。

我们来看 leetcode 的第 15 题：三数之和。该题的难度为中等，题目内容如下：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。**注意：**答案中不可以包含重复的三元组。示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[ [-1, 0, 1], [-1, -1, 2]]我们今天并不打算通过这道题的题解，因为这道题用递归算法是无法通过题解的，原因和之前一样，算法的时间复杂度高，最后会超出时间限制。另外我们去掉后面的注意部分事项，允许答案包含重复的三元组，我们使用递归算法相当于穷举出所有可能的情况，判断三元组的值是否能为 0。首先继续我们的解题三部曲：函数定义，输入和输出：def three_sum(nums, target, count): """ 输入: num: 输入的数组 target: 目标值 count: 在数组中找到几个数之和满足target 输出： []或者[[1,2,3], [-1,4,3]] 这样的满足条件的全部结果 """ res = [] # ... return res注意： 定义这样的递归函数是经过思考的，因为后续递归调用时需要依赖目标值 (target) 或元素个数 (count) 这样两个参数。返回的参数要么为空，要么是所有找到的满足条件的三元组的集合。接下来是递归方法的终止条件，首先考虑以下几个终止条件：如果输入的 nums 列表为空，那么直接返回 []；如果输入的 count 等于1，就要开始判断了，因为这个时候只需要判断 target 是否在列表中存在即可；综上，我们写出终止条件的代码：def three_sum(nums, target, count): """ 输入: num: 输入的数组 target: 目标值 count: 在数组中找到几个数之和满足target 输出： []或者[[1,2,3], [-1,4,3]] 这样的满足条件的全部结果 """ res = [] ###################### 终止条件 ###################################### if not nums: return res if count == 1 and target in nums: return [[ target ]] elif count == 1 and target not in nums: # count等于1时，如果target没有出现在剩余的nums中，说明不存在满足条件的数组元素 return res ####################################################################### # 返回值 return res接下来最重要的，就是递归的公式了，递归的方向一定要朝着减小目标函数规模进行。很明显，我们的递归应该是这样子：以 nums 的第一个元素为递归点，整个 nums 列表中和为 target 的 count 个元素的结果可以分为包含 nums[0] 和不包含 nums[0] 的结果组成，简单点说就是：如果包含 nums[0]，那么接下来的 nums[1:] 列表中我们就要找值为 target - nums[0] 的 count - 1 个元素，也即 three_sum(nums[1:], target - nums[0], count -1)，然后我们还需要在得到的元组集中的最前面位置加上 nums[0]；如果不包含 nums[0]，那么就是在 nums[1:] 列表中找值为 target 的 count 个元素，用递归函数表示就是 three_sum(nums[1:], target, count)；这样找到的结果正是 count 个元素。组合上述两个递归得到的结果，就得到了函数 three_sum(nums, target, count) 的结果，代码如下：res = []# 包含nums[0]t1 = three_sum(nums[1:], target - nums[0], count - 1)# 不包含nums[0]t2 = three_sum(nums[1:], target, count)if t1: for i in range(len(t1)): t = [nums[0]] t.extend(t1[i]) # 每个得到的结果前面加上 nums[0] res.append(t)if t2: for j in range(len(t2)): res.append(t2[j]) # 此时得到的res就是递归的最后结果综合就可以得到递归遍历所有三个元素和的情况并最终找出所有满足条件结果的三元集：def three_sum(nums, target, count): res = [] # 终止条件 if not nums: return res if count == 1 and target in nums: # 一定要这样写 return [[ target ]] elif count == 1 and target not in nums: return res # 包含nums[0] t1 = three_sum(nums[1:], target - nums[0], count - 1) # 不包含nums[0] t2 = three_sum(nums[1:], target, count) if t1: for i in range(len(t1)): # 犯了一个巨大的错误，extend() 方法的使用，它无返回，只会扩充原数组 # res.append([nums[0]].extend(t1[i])) t = [nums[0]] t.extend(t1[i]) res.append(t) if t2: for j in range(len(t2)): res.append(t2[j]) return res调用该函数的方式如下：nums = [-1, 0, 1, 2, -1, -4]# 0 为目标值，3为多少个元素和为targetres = three_sum(nums, 0, 3)这样的递归遍历思想在穷举中用的比较多，因为它以非常优雅的方式简化了穷举代码。不过这道题使用递归算法等价于穷举法，时间复杂度为 O(n3)O(n^3)O(n3)，因此显得并不高效。对于最优的解法读者可以自行思考下然后解决它。

对于一个递归问题，我们会有一套模板去实现这样一个递归算法：递归终止条件：一定和必须要有；递归公式：递归的核心，找不出递归公式的，也就无法使用递归算法来解决。这里实现递归算法的递部分；返回预定结果：返回我们预先定好的结果参与递归算法的归部分；基本上完成这样三个步骤，一个简易的递归算法也就算完成了，剩下的就是按照这三部实现代码了。我们不妨用前面的递归函数来看看这三步的具体位置：递归三部曲在下一节中，我们会在 LeetCode 上完成 3 道和递归相关的算法题，并使用这三个步骤去完成相关题解，也会让大家加深对这三步的理解。

这道题是 leetcode 的第 70 题，题目名称为爬楼梯。题目内容如下：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶示例 2：输入： 3输出： 3解释： 有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶使用前面的递归三套件来解答这个基础的递归问题，即函数 f(n) 为 n 阶楼梯的爬楼总方法数，则有：终止条件：很明显，当楼梯阶数为 1 时，我们知道答案肯定为 1，即 f(1) = 1；此外 n = 2时，也知 f(2) = 2；递归公式：递归指的是用前面计算出来的 f(n-1), f(n-2)，~，f(1) 等等的值递推得到 f(n)。这里思考下，首先我们的台阶往上减一级，即到达 n-1 级台阶的方法一共有 f(n-1) 种，然后只能跨 1 级到达第 n 级台阶，这是一种爬到楼顶的方法；由于我每次可以爬 1 个或者 2 个台阶，那么另一种爬到楼顶的方法是在 n-2 级台阶，然后爬 2 级就到了楼顶，而到达 n-2 级台阶的方法正好有 f(n-2) 种。综合得到递推公式为：f(n) = f(n-1) + f(n-2)返回预定结果：每个函数返回的结果是爬到 n 级台阶楼顶的总方法。综合这三步，我们就可以得到如下的函数：def climb_stairs(n): # 终止条件 if n <= 2: return n # 递推公式和返回预定结果 return climb_stairs(n - 1) + climb_stairs(n - 2) 但是这样的递归算法在 leetcode 上时无法通过的，原因就是我们前面提到的递归算法的可能会导致的一个问题：冗余计算，这样会使得递归算法的时间复杂度随着问题规模呈指数级上升，非常低效。递归超时我们来分析下这个递归算法造成冗余计算的原因，参考下图：计算f(5)时的冗余计算可以看到，在上面的递归分解计算图中可以看到，计算 f(5) 时，f(3) 会被重复递归计算。如果是计算 f(6) 时，f(5)、f(4) 以及 f(3) 都会被重复计算，具体的图就不画了。而且随着输入的值越大，冗余的数越多，会导致一个 f(k) 可能被重复计算好多次。这也就造成了该算法无法通过题解的原因。改进方法当然比较简单，我们有了递推式，不用递归即可：def climbStairs(self, n: int) -> int: if n <= 2: return n s = [1, 2] for _ in range(3, n + 1): s[0], s[1] = s[1], s[0] + s[1] return s[1]因此，有时候递归算法看起来美好但需要慎用，特别对于递推关系式中用到前面多个值时，要小心分析，避免出现冗余计算情况。

def F(n): if n == 1: return 1 return n * F(n - 1)前两行的语句是递归终止条件，这个是必须要有的，而且必须是递归要能到达的。最后一个 n * F(n - 1) 正是递归调用自身，且每次递归的参数都会减少直到最后的终止条件结束。我们用示例图来演示下 F(5) 执行的递归过程，这样方便我们理解递归调用。计算F(5)的递归调用递归算法动态示意图：从上面的示意图可以看到，递归的思想就是在不停调用本身往下执行，直到终止条件达到然后再回推结果。递归带来的好处非常明显，就是减少代码，让代码看起来简洁明了。假如我们要使用非递归算法来求解 n 的阶乘，代码如下：def F_no_recursive(n): s = 1 for i in range(1, n + 1): s = s * i return s可以看到，递归代码相比不使用递归的代码少了 for 循环，并且递归的代码看起来会比较简洁和清楚，这在二叉树的问题中会体现的非常明显。

按照之前的说明，递归应该是有去有回的，这样递归就必须有一个明确的分界点，递归可以在什么时候结束。程序一旦达到这个临界点，就不用继续递归重复下去了。简单来说，递归的终止条件就是为了防止出现无限递归的情况。

前面说到了递归问题的优点，就是使用递归后整体代码简洁明了，阅读起来让人如沐春风。但是递归方法也会才能在较大问题：递归太深，容易导致栈溢出异常。前面介绍过，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出；可能存在大量的冗余计算，算法的时间复杂度呈指数级增长，这个会在后面的递归实例中展示。

Shell 支持递归函数，递归函数也就是自己调用自己，即在函数体内部又一次调用函数自己，例如：[root@master func]# cat recursion.sh #!/bin/bashfunction myecho() { echo "$(date)" sleep 1 myecho inner}myecho[root@master func]# bash recursion.sh Sat Mar 28 13:14:38 CST 2020Sat Mar 28 13:14:39 CST 2020Sat Mar 28 13:14:40 CST 2020Sat Mar 28 13:14:41 CST 2020Sat Mar 28 13:14:42 CST 2020...如上就是一个递归函数，在函数体内部又调用了函数 myecho，在执行的时候就会陷入无限循环。

在明确递归的定义及数学模型之后，我们需要掌握递归的三要素：递归终止条件；递归终止时候的处理方法；递归中重复的逻辑提取，缩小问题规模。

如前面说到递归需要一个终止条件一样，在达到递归的终止条件时，需要有一个对应终止条件的程序处理方法。一般而言，在达到递归的终止条件时，对应的问题都是很容易解决的，可以快速的给出问题的解决方案。

递归的本质上还是要将一个大的问题分解成各个逻辑相同的小问题，所以递归过程中一个重要的步骤就是提取递归中重复的逻辑规则，以便利用相同的处理方式进行处理。按照以上递归的三要素，递归程序的一般处理可以总结成下面的伪代码：recursion(big_problem){ if (end_condition){ //满足递归的终止条件 solve_end_condition; //处理终止条件下的逻辑 end; //递归结束 }else { recursion(small_problem); //递归中重复的逻辑提取，缩小问题规模 }}

在这一节中，我们就需要利用递归的思想去求解斐波那契数列，当给出一个斐波那契中第几项的数字，然后求解出对应的斐波那契数值。在之前，我们已经定义了递归算法的相关概念，并且明确了需要应用递归时候的三要素：递归终止条件；递归终止时候的处理方法；递归中重复的逻辑提取，缩小问题规模。接下来，我们将利用递归的知识来解决斐波那契数列问题，明确在斐波那契数列求解问题中的递归三要素分别是什么。斐波那契数列的递归终止条件显然易见，通过观察斐波那契数列的定义，我们很容易发现当 n=1 或者 n=2 时，是斐波那契数列的递归终止条件，这个时候可以给出斐波那契数列的具体值。斐波那契数列递归终止时候的处理方法同样的，基于斐波那契数列的递推定义，当斐波那契数列达到终止条件 n=1 或者 n=2 时，我们也很容易发现对应 F(1)=1，F(2)=1，这就是斐波那契数列在递归终止时对应的取值。斐波那契数列的递归重复逻辑提取按照斐波那契数列的数学定义，F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*），即当 n ≥ 3 时，斐波那契数列中这一项的值等于前面两项的值之和，这样便可以将求解一个比较大的斐波那契数列转化为求解较小数值的斐波那契数列值，这里面有重复逻辑可以递归复用。例如，当我们求解斐波那契数列中的 F(5) 时，按照定义，我们有：F(5) = F(4) + F(3) // 递归分解​ = ( F(3) + F(2) ) + ( F(2）+F(1) ) // 递归求解​ = [ ( F(2)+F(1) ) + 1 ] + ( 1+1 ) // 递归求解，遇到终止条件就求解​ = [(1+1) +1 ]+(1+1) // 归并​ = 3 + 2 // 归并​ = 5 // 归并

本节将主要介绍基础算法中最为常见和最为简单的算法：递归算法。

本教程只需要简单的 Python 基础即可，没有其他的任何要求。主要是能理解一些解决问题的方法，比如递归、动态规划，需要一些抽象的思考能力。

在所有的编程语言中，函数的调用都是这样的过程：将当前调用函数的下一个指令地址压入堆栈，并保存现场环境；调到调用函数地址去执行；调用函数执行完成后，调用 ret 指令弹出下一步执行的地址，返回到原来的函数中接着执行下一条语句。示意图如下： 函数调用过程自己调用也是一样的过程，并不会说自己调用自己递归就会在函数内部执行，同样是在另一个地址有一份相同的函数代码拷贝，也就是将上图中的函数 B() 换成函数 A()，这幅图同样正确。递归调用的示意图如下：递归调用示意图

关于快排，候选人需要注意几个关键的考察点：（1）快排的平均时间复杂度为O（N*logN），最坏状态下时间复杂度为O（N^2），一般不会涉及具体的数学证明；（2）快排不是稳定排序算法，例如原始数组存在两个相同的数值，排序可能会交换两个值的顺序；（3）快速排序的核心思路是分治算法，实现方式是递归。

在二叉树的问题中，几乎处处用着递归。最经典的例子就是二叉树的前中后序的遍历，使用递归算法较为简单和明了，而使用非递归算法实现时会显得十分复杂，尤其是后序遍历，非常难写。今天我们来看二叉树中的几个非常简单的问题，全部使用递归方法解决这些问题。给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。示例 1：输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3]输出: true示例 2：输入: 1 1 / \ 2 2 [1,2], [1,null,2]输出: false示例 3：输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2]输出: false问题也比较简单，leetcode 官方给我们定义了二叉树类：# Definition for a binary tree node.class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None继续我们的递归三要素：终止条件，递推公式，预定输出。首先看看递归函数的输出：相同的树(True) 和不同的树(False)，输入是两个待比较二叉树的根节点，那么递归函数这样写：def is_same_tree(p, q): # ... reture False然后来看看终止条件，对于二叉树的终止条件就是到输入的两个根节点只要有一个为空即可。当两个根节点都为空是，返回 True；当只有其中一个根节点为空而另一个根节点不为空时，明显两个树不是相同的树，故返回 False：def is_same_tree(p, q): ################### 终止条件 ######################## if not p and not q: return True if not p or not q: return False ##################################################### # 递归比较 # ... reture False来看递归公式，判断一棵二叉树是否相同，我们首先是比较根节点的值，如果根节点的值不相同，那就直接返回 False；如果根节点相同，我们递归比较左子树和右子树，左子树或者右子树都相同时，那么这棵二叉树才是相同的：def is_same_tree(p, q): # 终止条件 # ... # 递归比较，返回True/False return p.val == q.val and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)看看这个递归的方法是不是非常简洁？那么这种写法会不会存在冗余的计算呢？答案时不会的，因为我们可以看到这里递归计算的左子树和右子树时完全没有重叠的部分，所以不存在冗余计算。因此，对于该问题而言，递归是一种非常优美的写法。完整的递归代码如下：class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef isSameTree(p, q): if not p and not q: return True if not p or not q: return False return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

假设存在 test 目录，test 目录下的子文件和子目录如下图所示：用于测试的目录树 现在要求编写程序 listDir.py，列出 test 目录下所有的文件，listDir.py 的内容如下：import osdef listDir(dir): entries = os.listdir(dir) for entry in entries: path = os.path.join(dir, entry) print(path) if os.path.isdir(path): listDir(path)listDir('test')在第 4 行，使用 os.listdir(dir) 获取目录 dir 下的文件名列表在第 5 行，遍历该列表，entry 为子文件的文件名在第 6 行，使用 os.path.join 生成子文件的完整路径在第 7 行，打印子文件的完整路径 path在第 8 行，如果子文件是目录，递归调用 listDir 列出它的所有文件运行程序，输出结果如下：test\atest\btest\b\x.txttest\b\y.txttest\ctest\readme.txt

本节主要介绍了递归的定义及基本概念，在学完本节课程之后，需要明白递归的基础逻辑是什么样的，如何自己去设计一个递归算法，在设计一个递归算法时需要考虑到哪些问题，以及我们日常中常见的递归问题。

有时候需要删除多层目录以及目录下的文件，可以使用 rm -r 递归删除，以删除 /home/data 目录为例：ls -l # 列出当前目录下的所有文件cd /home/data # 进入 /home/data 目录ls -l # 列出当前目录下的所有文件cd .. # 返回上一级目录rm -rf data/ # 递归删除 data/ 目录下所有文件ls执行结果如下：

本节主要介绍了用递归思想求解斐波那契数列，在学完本节课程之后，我们了解到了什么是斐波那契数列，并且将递归算法在斐波那契数列中进行了实际应用，需要掌握斐波那契数列的递归求解方法，并自己可以实现相关的代码实现，并清楚里面的每一步逻辑。

本节在介绍了递归算法概念并对递归算法的优缺点进行了相关分析，紧接着用 leetcode 上的两道基础递归题目进行了练习和说明，帮助理解递归算法。Tips：文中动图制作参考：https://visualgo.net/zh/sorting。

我们现在用一个简单的例子进行说明：假设我们需要写一个函数去求数字n的阶乘。当输入5时，输出5!=120，当输入6时，输出6!=720。如果我们编写了一个函数 F(n) 用来求解输入参数 n 的阶乘值，很明显我们可以发现这样一个递归关系：F(n) = n * F(n - 1)，那么我们求解 F(n) 的代码可以这样写：

思考：sync () 和 await () 方法如何同步等待执行完成并获取执行结果的呢？源码分析如下所示：private short waiters;//计数器@Overridepublic Promise<V> await() throws InterruptedException { //1.判断是否执行完成，如果执行完成则返回 if (isDone()) { return this; } //2.线程是否已经中断，如果中断则抛异常 if (Thread.interrupted()) { throw new InterruptedException(toString()); } //3.检查死锁 checkDeadLock(); //4.同步代码块->while循环不断的监听执行结果 synchronized (this) { while (!isDone()) { incWaiters();//waiters递增 try { wait();//JDK 的 Object 方法，线程等待【核心】 } finally { decWaiters();//waiters 递减 } } } return this;}//递增函数private void incWaiters() { if (waiters == Short.MAX_VALUE) { throw new IllegalStateException("too many waiters: " + this); } ++waiters;}//递减函数private void decWaiters() { --waiters;}通过以上代码，我们发现 await () 的核心其实就是调用 Object 的 wait () 方法进行线程休眠，普通的 Java 多线程知识点。

本节内容是递归算法系列之一：斐波那契数列递归求解，主要介绍了斐波那契数列的定义，然后用递归的实现思想分析了一下斐波那契数列，最后给出了基于 Java 代码应用递归思想实现斐波那契数列的代码实现及简单讲解。

今天我们用 3 道编程题来体验了一把递归算法，可以看到递归算法在编写时会使得代码整体看起来简洁优雅，但是有时候也会存在美丽的陷阱。例如第一个算法题中，使用递归算法会导致大量的冗余计算，使得算法的复杂度呈指数级增长。对于是否会存在冗余计算是在使用递归算法时一定要慎重考虑的，它会极大地影响算法的复杂度，如果存在的话，尽量不要使用递归算法或者想办法避免它。