结合代码示例解析递归的工作原理
结合代码示例解析递归的工作原理
原文：How Does Recursion Work? Explained with Code Examples
在本文中，你将学习递归的工作原理。
在学习递归之前，你需要很好地理解函数的工作原理。我在本文中使用了 Python 代码作为示例，因为它的语法简单，但递归的概念对于每种编程语言都是一样的。
什么是递归？
在大多数编程语言中，一个函数可以调用另一个函数。但一个函数也可以调用自身。递归是一种函数调用自身的技术。
这是一个例子：
def call_me():
call_me()
在这里，函数调用自身，这就是所谓的递归。
但是“调用自身”只是递归的程序定义。递归涉及将一个问题分解为更小的部分，直到无法进一步分解为止。你解决小问题并将它们组合起来以解决整个问题。
用真实生活中的例子类比递归
让我们通过一个例子来理解递归如何真正工作。
想象一下，你在迪士尼乐园排队等候，你不知道前面有多少人。
为了找出答案，你问你前面的人。
试图找出排在你前面的人数
那个人也不知道，所以她们询问她们前面的那个人。
这个过程继续进行，直到问题到达队伍最前面的人，他们看到前面没有人，回答说前面有零人。
然后队伍开始将回复传递回去。每个人在将信息传递回去之前，都会在他们被告知的数字上加 1。
当排在最前面的人回答，“前面有 0 人”时，下一个人加 1 然后回答，“前面有 1 人”，依此类推。
每个人都知道他们前面有多少人
当回复到达直接在你前面的人时，他们再加上 1 并告诉你。通过这种方式，你可以通过将前面的人给的数字添加1，来确定你在队伍中的位置。
这个例子说明了递归如何将问题分解为更小的子问题，然后结合它们的解决方案以解决原始问题。
队伍中的每个人代表同一问题的一个较小实例：确定前面的人数。通过解决这些较小的实例并结合它们的结果，整个问题得到了解决。这正是递归的工作原理。
递归的技术细节
在编码递归时最重要的是要找出：
递归情况：我们可以做的最小工作。在上面的例子中，询问你前面的人他们前面有多少人是我们可以做的最小工作。
基本情况：无需工作的条件。在上面的例子中，队伍最前面的人没有必要问任何问题，因此这是无需工作的条件。
递归的简单例子
计算阶乘是递归的最简单例子，它将真正帮助你理解其工作原理。
有很多方法可以计算一个数的阶乘。但在这里，我们将看到递归的方式来找到它。
在思考我们如何做到这一点之前，我们需要知道一个数的阶乘是什么。
一个数的阶乘是从1到该数的所有数字的乘积。
例如，5的阶乘是120—— 即5×4×3×2×1。
我们还可以用数学方式表示如下：
5×(5−1)!
这意味着如果我们知道
(5−1)!
的值，我们就可以通过简单地将5乘以它来轻松得到阶乘。
这就是我们如何找到4、3、2、1和0的阶乘：
Factorial of 4 = 4×(4−1)!
Factorial of 3 = 3×(3−1)!
Factorial of 2 = 2×(2−1)!
Factorial of 1 = 1
Factorial of 0 = 1
通过观察这些，很明显要找到5的阶乘，我们必须将5乘以
4!
。
更普遍的例子
要找到
n
的阶乘，我们需要将
n
乘以
(n−1)!
。这就是你需要递归执行的过程。
现在，必须为递归设置一个停止条件。停止条件是我们不再执行其他操作的地方。当
n
是1或0时，我们可以简单地停止递归，因为这些值的阶乘是已知的。我们可以简单地说1的阶乘是1，对于0也是如此。
因此，分解下来，要找到 n 的阶乘，所需做的最小工作量是
n×(n−1)!
。当我们找到1或0的阶乘时，我们可以停止对它进行操作。
让我们看看代码是怎样的：
# 计算 n 的阶乘
def fact(n):
# 基本情况
if n == 0 or n == 1:
return 1
# 递归情况
else:
return n * fact(n - 1)
n = 5
# 计算阶乘
factorial = fact(n)
print(factorial)
输出:
120
让我们看看它是如何工作的：
在第一次函数调用中，计算了5的阶乘。接着在第二次调用中，计算了4的阶乘，以此类推，直到计算2的阶乘。
递归计算 5 的阶乘
在调用2的阶乘时，我们有
2×fact(2−1)
，即
2×fact(1)
。
这达到了我们的基本条件。因此，递归停止，
2×fact(1)
返回
2×1
给前一个函数调用，并且结果从堆栈中弹出。
第四次函数调用返回 2 给前一个函数调用并从堆栈中弹出
类似地，这里是其他内容的计算方式：
第三次函数调用返回 6 给前一个函数调用并从堆栈中弹出
第二次函数调用返回 24 给前一个函数调用并从堆栈中弹出
第一次函数调用返回 120 给初始函数调用并从堆栈中弹出
所以函数最终将值120返回给初始函数调用。
为什么我们需要一个基本条件？
在上面的例子中，我们为代码使用了停止条件。但是如果我们不添加停止条件，或者我们编写的函数永远不满足停止条件呢？
代码会永远运行吗？
不会 – 即使你不终止，代码也不会永远运行。让我们通过一个例子来理解为什么会这样。
def print_five():
print(5)
# 调用自身
print_five()
# 函数调用
print_five()
输出:
5
5
5
...
RecursionError: maximum recursion depth exceeded
如果运行上面的代码，你会看到函数不会永远运行，并以消息
RecursionError: maximum recursion depth exceeded
结束。
当一个函数被调用时，它会被存储在一个调用堆栈中。下面是函数
print_five()
第一次被调用时在调用堆栈中的存储方式。
第一次函数调用时的调用堆栈
函数一次又一次地调用自身，并且每次调用时，函数被存储在调用堆栈中。
n 次函数调用后的调用堆栈
但是调用堆栈的大小是有限的，不能存储无限数量的函数。
调用堆栈空间不足导致栈溢出
当堆栈已满时，它无法再容纳更多调用，导致栈溢出错误。
因此，基本条件对于防止此类错误并确保递归正确终止是必不可少的。
现在让我们看看另一个例子，以便更深入地理解递归。
如何检查一个单词是否是回文
在深入代码之前，你应当知道什么是回文。回文是指正向和反向读取都相同的单词。
例如，
racecar
正向和反向读取都是相同的。
要检查一个单词是否是回文，我们需要检查第一个和最后一个字母是否相同。如果相同，我们接着检查第二个和倒数第二个字母是否相同。
检查 racecar 的第一个和最后一个字符是否相同
在
racecar
这一例子中，第一个和最后一个字母是相同的，所以我们检查第二个和倒数第二个字母是否相同。它们相同，所以现在我们检查第三个和倒数第三个字母是否相同。现在只剩下一个字母需要检查。一个单一字母始终是回文，因为它正反读都是相同的。
如何检查 racecar 是否是回文
所以，现在让我们尝试以递归的方式思考，包括最少的工作量以及确定何时不需要工作。
最少工作量
检查第一个和最后一个字母是否相同，如果相同，则移除单词中的第一个和最后一个字母。
不需要工作
当只剩下一个或没有字母时，我们可以简单地说它是一个回文。
现在，让我们看看代码是什么样子的：
# 检查回文
def check_palindrome(text):
# 停止条件
# 如果文本长度是 1 或 0，返回真
if len(text) == 0 or len(text) == 1:
return True
# 最少工作量
# 检查第一个和最后一个字符是否相同
# 如果相同，移除字符串中的第一个和最后一个字符
if(text[0]==text[-1]):
return(check_palindrome(text[1:-1]))
else:
return False
# 检查字符串是否为回文
text = "racecar"
is_palindrome = check_palindrome(text)
print(is_palindrome)
以下是上述代码的工作原理：
检查 racecar 是否为回文
检查 racecar 是否为回文
何时使用递归
递归看似优雅且简单，但由于反复向堆栈添加方法带来的 CPU 开销，即便是简单问题常也需经过多个步骤方能解决。因此，在使用之前，请确保仔细考虑它是否为解决问题的正确方案。
当代码需要多个循环且显得混乱时，递归可以提供更清晰的解决方案。然而，是否使用递归取决于具体的代码以及所涉及的数据类型或数据结构。对于树和图这类数据结构，递归尤其有用。
尽管递归表面简单，但可能难以理解，即使处理简单问题也可能需要多个步骤。因此，再次提醒，一定要根据具体情况考虑使用。
总结
这只是递归的入门介绍。递归的应用场景很多，你可能对其工作原理感到困惑。我将在下一篇文章中讨论更多递归的高级示例。
顺便说一下，以下是我在学习递归过程中找到的简单且有用的资源：
freeCodeCamp 的递归视频：我必须感谢 freeCodeCamp，他们优秀的递归视频课程在我写这篇文章时给我了极大的启发。
Programiz Pro 的递归课程：另一个好资源是 Programiz 的递归课程。这是一个高级课程，需付费，但它经过精心设计。而且，你可以直接在他们的平台上进行练习，真的是很值得。
无论你从哪里学习，都不要花太多时间寻找完美的资源。掌握概念并开始练习——这是你唯一能真正学会的方法。