递归的方式和时间
当函数调用导致在原始函数调用终止之前再次调用相同的函数时，会发生递归。例如，考虑众所周知的数学表达式 x!（即因子运算）。为所有非负整数定义了阶乘操作，如下所示：
- 如果数字为 0，则答案为 1。
- 否则，答案是该数字乘以比该数字小 1 的阶乘。
在 Python 中，可以将因子操作的简单实现定义为如下函数：
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
递归函数有时很难掌握，所以让我们一步一步地逐步完成。考虑表达 factorial(3)。此和所有函数调用都会创建一个新环境。环境基本上只是将标识符（例如 n，factorial，print 等）映射到其对应值的表。在任何时间点，你都可以使用 locals() 访问当前环境。在第一个函数调用中，唯一定义的局部变量是 n = 3。因此，打印 locals() 会显示 {'n': 3}。从 n == 3 开始，返回值变为 n * factorial(n - 1)。
在接下来的步骤中，事情可能会变得有些混乱。看看我们的新表达，我们已经知道什么是 n。但是，我们还不知道 factorial(n - 1) 是什么。首先，n - 1 评估为 2。然后，2 作为 n 的值传递给 factorial。由于这是一个新的函数调用，因此创建了第二个环境来存储这个新的 n。设 A 为第一环境， B 为第二环境。 A 仍然存在且等于 {'n': 3}，然而， B （等于 {'n': 2}）是当前环境。查看函数体，返回值又是 n * factorial(n - 1)。在不评估此表达式的情况下，让我们将其替换为原始的返回表达式。通过这样做，我们在精神上丢弃B，所以记得要相应地替代 n（即引用B的 n 与 n - 1 其使用取代A小号 n’）。现在，原始的返回表达式变为 n * ((n - 1) * factorial((n - 1) - 1))。花一点时间确保你明白为什么会这样。
现在，让我们评估一下这个部分。从 A ’s n == 3 开始，我们将 1 传递给 factorial。因此，我们正在创造一个新的环境 C ，它等于 {'n': 1}。同样，返回值是 n * factorial(n - 1)。因此，让我们替换原始返回表达式的 factorial((n - 1) - 1))，类似于我们之前调整原始返回表达式的方式。 原始表达现在是 n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1)))。
几乎完成了。现在，我们需要评估 factorial((n - 2) - 1)。这一次，我们正在传递 0。因此，这评估为 1。现在，让我们进行最后一次替换。 原始的回归表达现在是 n * ((n - 1) * ((n - 2) * 1))。回想一下原始返回表达式在 A 下计算，表达式变为 3 * ((3 - 1) * ((3 - 2) * 1))。当然，这评估为 6.要确认这是正确答案，请回忆一下 3! == 3 * 2 * 1 == 6。在进一步阅读之前，请确保你完全理解环境的概念以及它们如何应用于递归。
声明 if n == 0: return 1 被称为基本案例。这是因为它没有递归。绝对需要一个基本案例。没有一个，你将遇到无限递归。话虽如此，只要你至少有一个基本案例，你就可以拥有任意数量的案例。例如，我们可以按如下方式编写 factorial：
def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return n * factorial(n - 1)
你可能还有多个递归案例，但我们不会涉及到这种情况，因为它相对不常见并且通常很难进行精神处理。
你还可以进行并行递归函数调用。例如，考虑 Fibonacci 序列 ，其定义如下：
- 如果数字为 0，则答案为 0。
- 如果数字是 1，那么答案是 1。
- 否则，答案是前两个斐波纳契数的总和。
我们可以定义如下：
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)
我不会像使用 factorial(3) 那样彻底地完成这个功能，但是 fib(5) 的最终返回值等同于以下（ 语法无效）表达式：
(
fib((n - 2) - 2)
+
(
fib(((n - 2) - 1) - 2)
+
fib(((n - 2) - 1) - 1)
)
)
+
(
(
fib(((n - 1) - 2) - 2)
+
fib(((n - 1) - 2) - 1)
)
+
(
fib(((n - 1) - 1) - 2)
+
(
fib((((n - 1) - 1) - 1) - 2)
+
fib((((n - 1) - 1) - 1) - 1)
)
)
)
这变成了 (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1)))，当然评估为 5。
现在，我们将介绍一些词汇术语：
- 一个尾呼叫是一个简单的递归函数调用，它是返回值之前要执行的最后一个操作。要清楚，
return foo(n - 1)是一个尾调用，但return foo(n - 1) + 1不是（因为添加是最后一个操作）。 - 尾调用优化 （TCO）是一种自动减少递归函数递归的方法。
- 尾调用消除 （TCE）是对一个表达式的尾调用的减少，该表达式可以在没有递归的情况下进行求值。TCE 是一种 TCO。
尾调用优化有很多原因：
由于多种原因， Python 没有实现任何形式的 TCO。因此，需要其他技术来限制这种限制。选择方法取决于用例。通过一些直觉，factorial 和 fib 的定义可以相对容易地转换为迭代代码，如下所示：
def factorial(n):
product = 1
while n > 1:
product *= n
n -= 1
return product
def fib(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a
这通常是手动消除递归的最有效方法，但对于更复杂的函数来说，它可能变得相当困难。
另一个有用的工具是 Python 的 lru_cache 装饰器，它可用于减少冗余计算的次数。
你现在已经知道如何避免 Python 中的递归，但何时应该使用递归？答案是不经常。所有递归函数都可以迭代实现。这只是一个弄清楚如何做到这一点的问题。但是，极少数情况下递归是可以的。当预期的输入不会导致大量的递归函数调用时，递归在 Python 中很常见。
如果递归是你感兴趣的主题，我恳请你学习函数语言，如 Scheme 或 Haskell。在这种语言中，递归更有用。
请注意，Fibonacci 序列的上述示例虽然很好地展示了如何在 python 中应用定义以及稍后使用 lru 缓存，但由于它为每个非基本情况进行 2 次递归调用，因此运行时间效率低。对函数的调用次数呈指数增长至 n。
相反，非直观地，更有效的实现将使用线性递归：
def fib(n):
if n <= 1:
return (n,0)
else:
(a, b) = fib(n - 1)
return (a + b, a)
但那个问题就是返回一对数字。这强调了一些函数实际上并没有从递归中获得太多收益。