递归 != 递龟

不要被我们的标题误导了，递归不等于递只乌龟。

今天终于来到了，闫哥认为的第一个“玄学”算法了。

递归这玩意，对于初学者而言，在基础的数据结构和算法中，我认为可以归纳到到“玄学”这一类了。

那么，大家就会问了“既然递归跟玄学一样，那为什么还要学它呢？”。那我可以先给你说一句“不学也是可以滴，咱们直接转行，不学编程了”。其实到后面。比如，深度优先搜索，八皇后，回溯等算法的学习都会涉及到递归算法。

所以，咱们今天就放句狠话，必须搞定递归，搞的明明白白的。

对于“玄学”算法，我们就不能用正常的思维去学习它。既然是玄学，那么我们就先采用玄学的思维去理解和分析一下递归。

为什么称它为玄学呢？不是有多难，而是有些人，一看就明白，一用就精髓。而有些人呢，比如我，一看就会，一学就废，一开始就感觉递归是黑洞，我可以递进去，但就是归不出来。

这里呢。我们先敲一下重点。

递归：必须有递有归那才叫递归。

那么，接下来。我们先从一个故事去理解什么是递归吧。

在一个繁忙的大学食堂里，有一个长长的队伍，学生们都在耐心地等待着打饭。这个故事的主角是一个名叫小闫的学生，他刚刚加入队伍，但他有一个问题：他想知道自己在队伍中的确切位置。

小闫看着前面的人群，感到有些困惑。他想知道自己还要等多久才能打到饭，但他又不好意思直接问前面的人。突然，他灵机一动，决定用一种聪明的方法来解决这个问题。

小闫决定从队伍的最后一个人开始，也就是他前面的那个人，他称之为“前面的同学”。他问前面的同学：“你知道你在队伍中的位置吗？”前面的同学摇了摇头，但他说：“我可以问问我前面的同学。”

就这样，小闫的问题在队伍中传递开来。每个被问到的人都会问他们前面的同学，直到这个问题传到了队伍的最前面。

以下是就是一个简单的递归过程：

• 第 19 个人问第 18 个人：“你知道你在队伍中的位置吗？”
• 第 18 个人问第 17 个人：“你知道你在队伍中的位置吗？”
• 这样一直问到第 2 个人，他问第 1 个人：“你知道你在队伍中的位置吗？”

队伍的第一个人，也就是即将打饭的人，他笑着回答：“我是第一个，所以我确定我在队伍中的位置是 1。”(这里的第一个人就是我们的递归结束条件)

现在，这个信息开始返回给小闫：

• 第 2 个人告诉第 3 个人：“我是第二个，所以你是第三个。”
• 第 3 个人告诉第 4 个人：“我是第三个，所以你是第四个。”
• 这样一直传递，直到第 18 个人告诉第 19 个人：“我是第 18 个，所以你是第 19 个。”

最后，小闫前面的同学转过头告诉他：“我是第 18 个，所以你是第 19 个。” 小闫终于知道了他在队伍中的位置，他感到非常高兴。

小闫安心地等待着，最终轮到他打到饭。他一边吃着美味的饭菜，一边想着：“递归真是个神奇的东西，它帮助我解决了问题，而且还让队伍中的每个人都参与进来。”

（由此看来，小闫的道德素质真的没话说，从来不插队，而且还能让你学会递归。）

这个故事展示了递归的概念，其实就像一个链式反应，每个人都在解决问题的一部分，直到最终得到完整的答案。

上面的🌰，在生活中比较常见，接下来，正戏开始。

递归算法

递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归算法应用的场景是要解决的问题和其子问题具有相似性的时候，通过直接或间接的调用自己求出问题解的方法。它是通过解决一个问题的更小实例来解决一个大的问题的解的算法。递归算法有两个过程，一是调用过程，二是向上传递结果的过程。
—摘自《百度词条》

以下是我自己的对递归算法的理解：

递归算法是一种自我调用的算法，它解决问题的方法是通过将问题分解为更小的、与原问题有着相同形式的子问题，然后递归地解决这些子问题。

递归算法通常用于那些具有天然递归结构的问题，比如树和图的遍历、排序算法中的快速排序和归并排序、动态规划问题等。

以下是递归算法的一些关键概念：

递归的定义

递归算法通常由两部分组成：

1. 基例（Base Case）： 这是最简单的情况，可以直接得到答案，不需要进一步的递归调用。
2. 递归步骤（Recursive Step）： 对于更复杂的情况，算法将问题分解为更小的子问题，并递归地调用自身来解决这些子问题。

递归的要素

1. 递归调用： 算法在执行过程中调用自身。
2. 终止条件： 必须有一个或多个基例来终止递归调用，否则会导致无限递归，最终导致栈溢出错误。
3. 状态收敛： 递归调用应该逐步接近基例，确保递归最终能够终止。

递归算法的优缺点

优点：

• 递归代码通常更简洁、易于理解和维护。
• 递归可以自然地表达那些具有递归结构的问题。

缺点：

• 递归可能导致较高的内存消耗，因为每次递归调用都需要在调用栈上保存信息。
• 如果递归深度太大，可能会导致栈溢出。
• 递归算法的性能可能不如迭代算法，特别是在大量递归调用的情况下。

总结：
递归算法的设计通常更为简洁，但它们可能需要更多的内存空间，因为每次函数调用都会在调用栈上添加一个新的层级。此外，递归算法有时可能需要优化以避免重复计算，例如通过记忆化（缓存已计算的结果）。

递归算法的设计

设计递归算法时，通常遵循以下步骤：

1. 确定基例： 找到最简单的情况，可以直接给出答案。
2. 定义递归关系： 确定如何将问题分解为更小的子问题，并定义递归调用的方式。
3. 递归地解决子问题： 通过递归调用解决子问题。
4. 合并结果： 如果需要，合并子问题的解以得到原问题的解。

应用：

1. 数学计算：

   • 阶乘计算：计算一个数的阶乘 n! = n * (n-1) * (n-2) * ... * 1。
   • 斐波那契数列：计算斐波那契数列中的第 n 个数，F(n) = F(n-1) + F(n-2)，其中 F(0) = 0, F(1) = 1。

2. 排序算法：

   • 归并排序：将数组分成两半，对每一半进行排序，然后合并起来。
   • 快速排序：选择一个基准元素，将数组分成两部分，然后递归地对这两部分进行排序。

3. 搜索算法：

   • 二分搜索：在有序数组中使用递归进行二分搜索，以找到目标值。

4. 树的遍历：

   • 深度优先搜索（DFS）：在图或树中，从一个节点开始，探索尽可能深的分支，直到达到叶子节点，然后回溯。
   • 先序遍历、中序遍历、后序遍历：这些是树的三种基本遍历方式，通常使用递归实现。

5. 动态规划：

   • 背包问题：使用递归解决背包问题，确定哪些物品应该放入背包以最大化价值。
   • 最长公共子序列：寻找两个序列中最长的公共子序列。

6. 图形算法：

   • 图的连通性：使用递归检查图中的节点是否连通。
   • 图的拓扑排序：使用递归进行拓扑排序，以确定图中节点的线性顺序。

7. 组合与排列：

   • 组合：生成所有可能的组合，例如从 n 个物品中选择 k 个物品的所有可能方式。
   • 排列：生成所有可能的排列，例如对 n 个物品进行排序的所有可能方式。

8. 算法竞赛与游戏：

   • 八皇后问题：在棋盘上放置八个皇后，使得它们互不攻击。
   • 数独求解器：使用递归算法解决数独谜题。

9. 字符串处理：

   • 字符串匹配：使用递归算法（如 KMP 算法）在文本中搜索模式字符串。

例题

首先说一点，以下两个问题既能使用递归解决，也能使用递推解决，既让讲题，那么我们就一次性把它讲完全。

斐波那契数列

斐波那契数列是一个非常著名的数列，它以递归的方式定义，其特点是从第三项开始，每一项都等于前两项之和。数列的前两项分别是 0 和 1。数学上，斐波那契数列 $F($