【算法】递归的艺术：从本质思想到递归树，深入剖析算法的性能权衡

(递归)

导读

大家好，很高兴又和大家见面啦！！！ 在上一篇内容中，我们揭开了递归的"神秘面纱"：递归就是函数自己调用自己，并且掌握了它的两个必要条件：

• 必须有一个明确的结束条件
• 每次递归调用都要向结束条件靠近

理解了这些基础知识后，不知道你是否也曾思考过这样的问题：

• 为什么我们需要递归？​ 如果所有问题都能用循环解决，递归存在的意义是什么？
• 递归到底有什么魔力，让程序员们对它又爱又恨？为什么有人说"递归让代码更优雅"，却又警告"小心栈溢出"？
• 当你面对一个复杂问题时，如何判断它是否适合用递归解决？递归是如何将复杂问题"化繁为简"的？
• 更重要的是，递归的执行过程到底是怎样的？函数一次次调用自己时，计算机内部发生了什么？

如果你对这些问题感到好奇，那么今天的探讨将为你一一揭晓答案。让我们继续深入递归的世界，探索其背后的精妙之处！

一、核心思想

递归的核心思想：分而治之 递归的本质是将一个大规模问题分解成一个或几个规模较小、但与原问题本质相同的小问题。这些小问题再用同样的方法继续分解，直到分解到足够小、可以直接解决（这个“足够小”的点就是递归基）。

二、适用场景

递归这种分解思想非常适用于以下场景：

• 问题的定义本身就是递归的场景： 斐波那契数列：F(n) = F(n - 1) + F(n - 2) 阶乘：n! = n * (n - 1)!
• 操作的数据结构是递归的场景： 树的相关操作：遍历、搜索、计算深度、计算结点数量…… 链表：将长度为 n 的链表 = 1 个结点 + 长度为 (n - 1) 的链表 图的深度优先遍历
• 需要 回溯 算法的问题：
  • 迷宫问题：走到一个岔路口，先尝试一条路走到底（递归），如果走不通，就返回到上一个岔路口（回溯），再尝试另一条路
  • 八皇后问题：尝试在棋盘上放置一个皇后，然后递归地在下一行放置，如果导致冲突，就撤销当前选择（回溯），尝试下一个位置

三、递归与迭代

之前我们有介绍过递归与迭代的区别：

• 因为计算机内存的限制，递归会随着层次的深入，耗尽内存空间，进而出现 栈溢出 的情况导致递归的结束；
• 但是迭代是直接在内存空间中申请一块空间，并在这个空间中进行一系列的操作，如果不加以限制，则会出现死循环；

这是二者在限制条件下的区别，简单的说：

• 递归无限制条件（即递归结束条件）时，会出现栈溢出而导致递归的终止；
• 迭代无限制条件（即循环结束条件）时，会出现死循环

但是二者的区别不限于此，二者在实现的细节上也存在很大的区别：

• 递归只需要关注 递归基 的具体实现，而其它的步骤则会简化为函数的调用；
• 迭代则会明确整个过程的每一个细节

四、优势与缺点

4.1 优势

递归的优势可以总结为两点：

• 代码简洁、清晰：对于适用的问题，递归代码通常比等价的循环代码要简短的多，可读性更强，它更加接近我们对问题的数学或逻辑定义；
• 简化复杂问题：它将包含多重循环、状态维护的复杂逻辑，简化成几个简单的递归调用；

这里我们以斐波那契数列的实现来具体说明其优势：

//斐波那契数列——递归实现
int Fbn(int n) {
	if (n == 0) {
		return 0;
	}
	if (n == 1) {
		return 1;
	}
	return Fbn(n - 1) + Fbn(n - 2);
}

//斐波那契数列——迭代实现
int Fbn_(int n) {
	if (n == 0) {
		return 0;
	}
	if (n == 1) {
		return 1;
	}
	int a = 0, b = 1, c = 0;
	for (int i = 2; i <= n; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}

上述的代码片段分别展示了斐波那契数列的递归实现与迭代实现这两种实现方式，下面我们先来看一下两个函数的测试结果：

可以看到，在计算斐波那契数列时，递归在整个过程中只用关心某一项是如何计算，如我们要计算 F(5) 我们只需要知道它的值可以通过 F(4) + F(3) 获取，但是具体如何获取的我们不需要过多关注； 而迭代的实现中，我们则需要计算从 F(2) 到 F(5) 的每一项的值，进而得到 F(5) 的值； 相比于迭代，递归在代码的编写上会更加的简洁，并且递归将迭代中的具体实现逻辑简化为了斐波那契数列的递推公式；

4.2 缺点

但是递归同样也会有一些不可忽视的缺点：

• 性能开销大

因为递归是直接在内存空间中申请新的函数栈帧来实现每一次递归基，所以当递归的深度增加，对函数栈帧的需求也会增加，当申请的函数栈帧到达内存极限时，继续申请函数栈帧，就会导致 栈溢出。

• 可能产生重复计算

递归的实现是关注于 递归基 的实现细节，就比如计算斐波那契数列时，我们只需要关注其递归基 F(0) 与 F(1)，而其它的数值对应的斐波那契数我们则可以通过递推公式进行推导，如：

• F(5) = F(4) + F(3)
• F(4) = F(3) + F(2)
• F(3) = F(2) + F(1)
• F(2) = F(1) + F(0)

可以看到，在整个的推导过程中，当我们要计算 F(5) 的斐波那契数时，我们需要在 F(5) 的递推式中计算一次 F(3) ，在 F(4) 的递推式中计算一次 F(3) ； 也就是说在计算 F(5) 的过程中，对于 F(3) 这个数的值，我们就重复计算了两次；

• 难以调试

由于递归的代码过于简洁，将复杂的实现逻辑简化为了相应的函数调用，因此在具体的调试过程中会增加整体的调试难度；

4.3 小结

综上所述，递归作为一种强大的编程工具，它可以用于解决特定类型问题，而不能作为盲目替代迭代的通用工具； 当一个复杂的问题可以通过分而治之的思想将其分解为相同类型的子问题时，我们可以优先考虑使用递归实现； 而当我们需要关注算法的性能，或者使用递归时其递归深度可能会导致栈溢出的问题时，使用迭代通常是更安全、更高效的选择。 现在我们已经解决了第一个问题——为什么要使用递归？ 那我们又应该如何使用递归呢？下面我们就来了解以下实现递归的具体步骤；

五、实现步骤

当我们要通过递归解决一个复杂的问题时，我们可以将其划分为 4 个具体步骤：

• 定义递归函数
• 寻找递归基
• 寻找递进关系
• 组合与优化

接下来我们就通过阶乘的计算来具体了解一下这 4 个步骤；

5.1 定义递归函数

当我们要通过递归解决 阶乘问题 时，我们需要明确函数的三要素——函数名、函数参数以及函数的返回类型；

• 函数名：我们可以直接通过 阶乘 的英文翻译：Factorial 来进行命名；
• 函数参数：因为阶乘计算的是整型值，因此我们可以根据任务的规模大小来定义函数的参数：
  • 数值的大小不超过 int 的最大值 INT_MAX ，我们可以定义其参数类型为 int；
  • 数值的大小超过 int 的最大值 INT_MAX ，则我们需要使用 long long 来作为参数类型；
• 函数返回类型：函数的返回类型需要根据其值的大小来进行确定：
  • 当值的大小不超过 INT_MAX 时，函数的返回类型可以定义为 int
  • 当值的大小超过 INT_MAX 时，函数的返回类型可以定义为 long long

这里我们就以 int 型为例，来定义递归函数：

int Factorial(int n) {

}

5.2 寻找递归基

递归基 指的就是 递归出口 ，也就是在整个递归的过程中 最简单、不需要通过递归就能得到答案的情况。 而在 阶乘问题 中，其递归基为 0! = 1 与 1! = 1 ，因此该问题的递归实现中，其函数出口我们可以定义为：

if (n == 0 || n == 1) {
	return 1;
}

5.3 寻找递进关系

递进关系 我们可以理解为 递推公式 ，这是实现递归的 引擎 。 我们要寻找一个问题的 递进关系 ，我们就需要通过 分而治之 的思想，将该问题分解为规模更小、但结构相同的子问题：

• 斐波那契数列 的递推公式为：F(n) = F(n - 1) + F(n - 2)
• 阶乘问题的递推公式为：n! = n * (n - 1)!

因此根据该 递推公式 我们可以得到函数的 递进关系：

return n * Factorial(n - 1);

5.4 组合与优化

在确保了递归调用始终是靠近 递归基 后，我们就可以将所有内容加以整合并对其进行优化，得到最终的 阶乘问题 的 递归实现 代码：

//阶乘问题
int Factorial(int n) {
	if (n == 0 || n == 1) {
		return 1;
	}
	return n * Factorial(n - 1);
}

说明这么多，那么递归算法具体是如何实现的呢？它的算法执行过程是怎么样的？ 要了解递归算法的具体实现过程，我们就需要借助一个工具——递归树；

六、递归树

递归树：一种用于分析和可视化递归算法执行过程的树形结构。它是理解递归工作原理、分析递归算法时间复杂度的强大工具。 这里我们以 阶乘问题 的递归算法为例：

flowchart TB
a[5!]--->b[5]
a--->c[4!]
c--->d[4]
c--->e[3!]
e--->f[3]
e--->g[2!]
g--->h[2]
g--->i[1!]
i--->j[1! == 1]

在上面这棵二叉树中，其左子树为所求值 n ，其右子树则为该算法的递归函数 f(n - 1)。 也就是说，当我们要计算 5! ，其递归算法的执行过程会根据右子树不断的进行深入，直到递归函数到达 递归基 ，函数才会开始回归：

flowchart BT
a[120]
b[5]
c[24]
d[4]
e[6]
f[3]
g[2]
h[2]
i[1]
j[1! == 1]
j--->i
h--->g
i--->g
f--->e
g--->e
d--->c
e--->c
b--->a
c--->a

最终递归函数会将该 递归树 的根节点中存储的值进行返回。 当我们要对该算法进行分析时，我们实际分析的是该棵递归树的 高度 与 结点数量：

• 第一层：C(1) = 1
• 第二层：C(2) = 2
• 第三层：C(3) = 2
• \cdots
• 第n层：C(n) = 1

在这些结点中，我们需要关注每个结点的具体 工作量 ：

• 第一层：根结点的工作量为 O(1) ，即该结点执行了一次 函数调用
• 第二层： 左子树的工作量为 O(1) ，即该结点执行了一次 数乘 右子树的工作量为 O(1) ，即该结点执行了一次 函数调用
• \cdots
• 第 n 层：该结点的工作量为 O(1) ，即该结点执行了一次 赋值返回

在计算 n! 的函数递归中，其对应的递归树中除了第一层与第 n 层只有 1 个结点外，其它层均有 2 个结点，即整棵树的结点总数为：

• C(n) = 1 + \underbrace{2 + 2 + \cdots + 2}_{n - 2\text{个}2} + 1 = 2 + 2 * (n - 2) = 2 * (n - 1)

该算法的时间复杂度我们可以通过下面的公式计算得出：

即：

$$ \begin{align*} O(N) &= C(N) * O(N) \ &= 2 * (n - 1) * O(1) \ &= O(2n) - O(2) \ &= O(n) \rightarrow O(N) \end{align*} $$

也就是说，通过递归算法计算 阶乘问题 ，其算法的时间复杂度为：O(N) 。 该算法的空间复杂度分析则由递归的深度决定，即通过树的深度决定：

• 阶乘问题 中，其对应的递归树的深度为 n
• 每一层递归我们都需要在内存中开辟大小为 O(1) 的函数栈帧空间
• 算法的空间复杂度为 O(N) = n * O(1) = O(N)

也就是说通过递归算法解决 阶乘问题，不管是其时间复杂度还是空间复杂度均为：O(N)，即该算法与数据规模均为 线性关系。 由于系统的内存大小是固定的，因此当我们计算的数值所需的函数栈帧空间大于系统的内存大小时，递归算法就会出现 栈溢出 的问题；这时我们通过迭代实现，往往是更佳的选择。

结语

通过今天的学习，我们深入探索了递归这一重要的编程思想。让我们回顾一下本文的核心要点：

• 递归的核心思想是"分而治之"——将复杂的大问题分解为结构相同的子问题，直到问题足够简单可以直接解决。
  • 这种思想在数学定义递归的问题（如阶乘、斐波那契数列）、递归数据结构（树、链表）以及需要回溯算法的问题中表现出色。
• 递归与迭代各有优劣：
  • 递归让代码更加简洁清晰，更贴近问题的数学定义，但需要付出性能开销和栈溢出的风险；
  • 迭代虽然代码相对复杂，但在性能和内存使用上更加安全可控。
• 实现递归的四步法为我们提供了清晰的实践指南：

• 递归树这一工具帮助我们直观理解递归的执行过程，并能够系统分析算法的时间复杂度和空间复杂度，让我们对递归的性能特征有了量化认识。

递归就像一把双刃剑——用对了能让复杂问题迎刃而解，用错了则可能导致性能灾难。关键在于根据具体问题特点做出明智选择：

• 当问题天然具有递归结构时，递归往往是最优雅的解决方案；
• 当性能至关重要或递归深度可能很大时，迭代可能是更稳妥的选择。

希望本文能帮助你不仅理解递归的"形"，更能掌握其"神"，在未来的编程实践中游刃有余地运用这一强大工具。 互动与分享

• 点赞👍 - 您的认可是我持续创作的最大动力
• 收藏⭐ - 方便随时回顾这些重要的基础概念
• 转发↗️ - 分享给更多可能需要的朋友
• 评论💬 - 欢迎留下您的宝贵意见或想讨论的话题

感谢您的耐心阅读！ 关注博主，不错过更多技术干货。我们下一篇再见！