John Sturtz
如果你熟悉 Python 中的函数，那么你一定知道一个函数调用另一个函数是很常见的。在 Python 中，函数甚至还可以调用自身！这种调用自己的函数被称为递归函数，而使用递归函数的技术就叫做递归（recursion）。
虽然函数调用自身听起来有些奇怪，但许多类型的编程问题用递归方式表达最为自然。当你遇到这类问题时，递归将成为你工具箱中不可或缺的利器。
学完本教程后，你将理解：
- 什么是函数的递归调用
- Python 函数的设计如何支持递归
- 在决定是否使用递归来解决问题时应考虑哪些因素
- 如何在 Python 中实现递归函数
接下来，你将学习几个使用递归解决的 Python 编程问题，并将递归解法与对应的非递归解法进行对比。
什么是递归？
“Recursion”（递归）一词源自拉丁语 recurrere，意为“跑回去、返回、重现”。以下是网上对“递归”的一些定义：
- Dictionary.com：返回或折返的行为或过程
- Wiktionary：用对象自身来定义该对象（通常是函数）的行为
- The Free Dictionary：一种定义对象序列（如表达式、函数或集合）的方法，其中给出若干初始对象，后续每个对象都由前面的对象定义
递归定义是指被定义项出现在其自身的定义中。现实生活中经常出现这种自指（self-referential）的情形，尽管我们未必立刻意识到。例如，假设你想描述构成你祖先的那群人，你可以这样定义：
祖先的递归定义：你的父母是你的祖先；你祖先的父母也是你的祖先。
注意，被定义的概念“祖先”出现在了它自己的定义中——这就是一个递归定义。
在编程中，递归有非常明确的含义：它指的是一种函数调用自身的编码技术。
为什么使用递归？
严格来说，大多数编程问题都可以不用递归来解决，因此递归通常并非必需。
然而，某些情形特别适合用自指的方式来定义——比如上面提到的“祖先”定义。如果你要为此类问题设计算法，递归解法通常会更简洁、清晰。
另一个典型例子是遍历树状数据结构。由于这些结构是嵌套的，它们天然契合递归定义。用非递归算法遍历嵌套结构往往会显得笨拙，而递归解法则相对优雅。本教程稍后会展示一个这样的例子。
不过，递归并不适用于所有场景。你还需考虑以下因素：
- 对某些问题，递归解法虽然可行，但可能显得笨拙而非优雅。
- 递归实现通常比非递归消耗更多内存。
- 在某些情况下，使用递归可能导致执行速度变慢。
通常，代码的可读性是最重要的考量因素，但具体情况具体分析。下面的示例将帮助你判断何时应选择递归。
Python 中的递归
在 Python 中调用函数时，解释器会创建一个新的局部命名空间，以避免函数内部定义的名称与其他地方的同名变量冲突。一个函数可以调用另一个函数，即使两者都定义了同名变量，也不会出错，因为它们存在于不同的命名空间中。
同样的规则也适用于同一函数的多个并发实例。例如，考虑以下定义：
def function():
x = 10
function()
当 function() 第一次执行时，Python 创建一个命名空间，并在其中将 x 赋值为 10。然后 function() 递归调用自身。第二次运行时，解释器又创建了一个新的命名空间，并再次将 x 设为 10。这两个 x 是彼此独立的，因为它们位于不同的命名空间中。
不幸的是，按当前写法运行 function() 的结果并不理想，如下所示：
>>> function()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 3, in function
File "<stdin>", line 3, in function
File "<stdin>", line 3, in function
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
理论上，这个 function() 会无限递归下去，永不停止。但实际上，计算机内存有限，最终会耗尽。
Python 不允许这种情况发生。解释器限制了函数递归调用的最大次数，一旦达到该限制，就会抛出 RecursionError 异常，如上所示。
技术提示：你可以使用
sys模块中的getrecursionlimit()查看 Python 的递归限制：>>> from sys import getrecursionlimit >>> getrecursionlimit() 1000也可以用
setrecursionlimit()修改它：>>> from sys import setrecursionlimit >>> setrecursionlimit(2000) >>> getrecursionlimit() 2000你可以设得很大，但不能设为无限。
一个毫无节制地无限递归的函数没什么实际用途。这就像洗发水瓶上的说明：“起泡、冲洗、重复”。如果你字面理解，就会永远洗下去！
显然，一些厂商也意识到了这个逻辑漏洞，因此有些瓶子上写着：“起泡、冲洗，必要时重复”。这就提供了一个终止条件——当你觉得头发足够干净时，就可以停止了。
同样，递归函数也必须有停止计划。典型的递归函数遵循以下模式：
- 存在一个或多个基础情况（base cases），可以直接求解，无需进一步递归。
- 每次递归调用都使问题逐步靠近基础情况。
现在，让我们通过几个例子看看它是如何工作的。
入门示例：倒计时到零
第一个例子是一个名为 countdown() 的函数，它接收一个正整数作为参数，并从该数字打印到 0：
>>> def countdown(n):
... print(n)
... if n == 0:
... return # 终止递归
... else:
... countdown(n - 1) # 递归调用
...
>>> countdown(5)
5
4
3
2
1
0
注意 countdown() 完全符合上述递归算法的范式：
- 基础情况是
n == 0，此时递归停止。 - 递归调用中，参数比当前
n小 1，因此每次递归都更接近基础情况。
注意：为简化起见，
countdown()没有检查参数的有效性。如果n不是整数或为负数，由于永远达不到基础情况，将引发RecursionError。
上面的 countdown() 清晰地展示了基础情况和递归调用，但也可以写得更简洁：
def countdown(n):
print(n)
if n > 0:
countdown(n - 1)
以下是对应的非递归实现供对比：
>>> def countdown(n):
... while n >= 0:
... print(n)
... n -= 1
...
>>> countdown(5)
5
4
3
2
1
0
在这个例子中，非递归解法至少和递归一样清晰直观，甚至更胜一筹。
定义 Python 阶乘函数
下面是一个计算阶乘的递归函数。注意它多么简洁，并且完美对应数学定义：
>>> def factorial(n):
... return 1 if n <= 1 else n * factorial(n - 1)
...
>>> factorial(4)
24
稍作修饰，加入 print() 语句，可以更清楚地看到调用和返回的顺序：
>>> def factorial(n):
... print(f"factorial() called with n = {n}")
... return_value = 1 if n <= 1 else n * factorial(n -1)
... print(f"-> factorial({n}) returns {return_value}")
... return return_value
...
>>> factorial(4)
factorial() called with n = 4
factorial() called with n = 3
factorial() called with n = 2
factorial() called with n = 1
-> factorial(1) returns 1
-> factorial(2) returns 2
-> factorial(3) returns 6
-> factorial(4) returns 24
24
注意所有递归调用是如何“堆叠”起来的：函数依次以 n = 4, 3, 2, 1 被调用，直到 n = 1 时无需再递归，问题得以解决。然后，各层递归依次“展开”，从最内层返回 1、2、6，最终外层返回 24。
当然，这里并不必须使用递归。你可以用 for 循环迭代实现阶乘：
>>> def factorial(n):
... return_value = 1
... for i in range(2, n + 1):
... return_value *= i
... return return_value
...
>>> factorial(4)
24
你也可以使用 functools 模块中的 reduce() 实现：
>>> from functools import reduce
>>> def factorial(n):
... return reduce(lambda x, y: x * y, range(1, n + 1) or [1])
...
>>> factorial(4)
24
这再次说明：如果一个问题可以用递归解决，通常也有多种非递归方案。你应根据哪种写法更清晰、直观来选择。
另一个要考虑的因素是执行速度。递归与非递归解法之间可能存在显著性能差异。下一节将进一步探讨这一点。
阶乘实现的速度比较
要评估执行时间，可以使用 timeit 模块中的 timeit() 函数。本教程使用以下格式：
timeit(<command>, setup=<setup_string>, number=<iterations>)
timeit() 首先执行 <setup_string> 中的命令，然后重复执行 <command> 指定次数，并报告总耗时（秒）：
>>> from timeit import timeit
>>> timeit("print(string)", setup="string='foobar'", number=100)
foobar
foobar
...
foobar
0.03347089999988384
下面使用 timeit() 比较三种阶乘实现（递归、迭代、reduce）的性能。每种情况下，setup_string 定义相应的 factorial() 函数，然后 timeit() 执行 factorial(4) 一千万次并报告总时间。
首先是递归版本：
>>> setup_string = """
... print("Recursive:")
... def factorial(n):
... return 1 if n <= 1 else n * factorial(n - 1)
... """
>>> from timeit import timeit
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
Recursive:
4.957105500000125
接着是迭代版本：
>>> setup_string = """
... print("Iterative:")
... def factorial(n):
... return_value = 1
... for i in range(2, n + 1):
... return_value *= i
... return return_value
... """
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
Iterative:
3.733752099999947
最后是 reduce() 版本：
>>> setup_string = """
... from functools import reduce
... print("reduce():")
... def factorial(n):
... return reduce(lambda x, y: x * y, range(1, n + 1) or [1])
... """
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
reduce():
8.101526299999932
在这个测试中，迭代最快，递归稍慢但差距不大，reduce() 最慢。你在自己机器上运行结果可能不同——时间肯定不一样，甚至排名也可能不同。
这重要吗？ 迭代与 reduce() 之间近 4 秒的差距是在一千万次调用下才显现的。
- 如果函数会被频繁调用，可能需要考虑执行速度。
- 如果函数很少运行，执行时间差异可忽略不计，此时应优先选择最清晰表达问题解法的实现。
对阶乘而言，上述测试表明递归实现是一个合理的选择。
不过坦白说，在 Python 中你根本不需要自己实现阶乘函数——它已在标准库 math 模块中提供：
>>> from math import factorial
>>> factorial(4)
24
它在计时测试中的表现如何？
>>> setup_string = "from math import factorial"
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
0.3724050999999946
哇！math.factorial() 比上述三种实现中最快的还要快约 10 倍！
遍历嵌套列表
下一个例子涉及遍历嵌套列表结构。考虑以下 Python 列表：
names = [
"Adam",
[
"Bob",
[
"Chet",
"Cat",
],
"Barb",
"Bert"
],
"Alex",
[
"Bea",
"Bill"
],
"Ann"
]
如下图所示，names 包含两个子列表。
假设你想统计这个列表中的**叶元素（leaf elements）**数量——即最底层的字符串对象，就好像把列表“展平”了一样。叶元素包括 "Adam"、"Bob"、"Chet"、"Cat"、"Barb"、"Bert"、"Alex"、"Bea"、"Bill" 和 "Ann"，共 10 个。
直接对列表调用 len() 并不能得到正确答案：
>>> len(names)
5
len() 只统计 names 顶层的对象，即三个叶元素 "Adam"、"Alex"、"Ann" 和两个子列表：
>>> for index, item in enumerate(names):
... print(index, item)
...
0 Adam
1 ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
2 Alex
3 ['Bea', 'Bill']
4 Ann
你需要一个能**递归遍历整个列表结构（包括子列表）**的函数。算法大致如下：
- 逐个检查列表中的每个元素。
- 如果是叶元素，累加计数。
- 如果遇到子列表，则：
- 进入该子列表，同样遍历它；
- 遍历完子列表后，将其元素数量加到总计数中；
- 继续从父列表中断处继续遍历。
注意这里的自指性：遍历列表 → 遇到子列表 → 同样遍历该列表。这种情况非常适合递归！
递归遍历嵌套列表
递归非常适合这个问题。你需要判断列表中的某个元素是叶节点还是子列表。为此，可使用 Python 内置函数 isinstance()。
在 names 列表中，若某元素是 list 类型，则为子列表；否则为叶元素：
>>> isinstance(names[0], list) # 'Adam'
False
>>> isinstance(names[1], list) # ['Bob', ...]
True
>>> isinstance(names[1][1], list) # ['Chet', 'Cat']
True
>>> isinstance(names[1][1][0], list) # 'Chet'
False
现在可以实现一个递归函数来统计叶元素数量：
def count_leaf_items(item_list):
"""递归统计（可能嵌套的）列表中的叶元素数量"""
count = 0
for item in item_list:
if isinstance(item, list):
count += count_leaf_items(item)
else:
count += 1
return count
在多个列表（包括 names）上测试：
>>> count_leaf_items([1, 2, 3, 4])
4
>>> count_leaf_items([1, [2.1, 2.2], 3])
4
>>> count_leaf_items([])
0
>>> count_leaf_items(names)
10 # 成功！
像阶乘例子一样，加入 print() 可展示递归调用过程：
def count_leaf_items(item_list):
print(f"List: {item_list}")
count = 0
for item in item_list:
if isinstance(item, list):
print("Encountered sublist")
count += count_leaf_items(item)
else:
print(f'Counted leaf item "{item}"')
count += 1
print(f"-> Returning count {count}")
return count
在 names 上运行输出如下：
List: ['Adam', ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert'], 'Alex', ['Bea', 'Bill'], 'Ann']
Counted leaf item "Adam"
Encountered sublist
List: ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
Counted leaf item "Bob"
Encountered sublist
List: ['Chet', 'Cat']
Counted leaf item "Chet"
Counted leaf item "Cat"
-> Returning count 2
Counted leaf item "Barb"
Counted leaf item "Bert"
-> Returning count 5
Counted leaf item "Alex"
Encountered sublist
List: ['Bea', 'Bill']
Counted leaf item "Bea"
Counted leaf item "Bill"
-> Returning count 2
Counted leaf item "Ann"
-> Returning count 10
10
每次 count_leaf_items() 调用结束时，都会返回它所统计的叶元素数量。顶层调用返回 10，正确无误。
注意：为简化，此实现假设列表只包含叶元素或子列表，不含字典、元组等其他复合对象。
非递归遍历嵌套列表
和前面的例子一样，列表遍历也不必须用递归。以下是迭代实现：
def count_leaf_items(item_list):
"""非递归统计（可能嵌套的）列表中的叶元素数量"""
count = 0
stack = []
current_list = item_list
i = 0
while True:
if i == len(current_list):
if current_list == item_list:
return count
else:
current_list, i = stack.pop()
i += 1
continue
if isinstance(current_list[i], list):
stack.append([current_list, i])
current_list = current_list[i]
i = 0
else:
count += 1
i += 1
测试结果与递归版本一致：
>>> count_leaf_items(names)
10
该策略使用栈处理嵌套子列表。遇到子列表时，将当前列表和索引压入栈；统计完子列表后，从栈中弹出父列表和索引，继续遍历。
实际上，递归实现内部也做了类似的事：每次递归调用时，Python 会将当前执行状态保存在调用栈中；递归返回时，再从栈中恢复状态。区别在于，递归版本中 Python 自动帮你管理了栈。
检测回文
是否使用递归，很大程度上取决于问题本身的性质。
- 阶乘：天然适合递归，但迭代解法也很直接——两者难分高下。
- 列表遍历：递归解法优雅，非递归则笨拙。
- 下一个问题：用递归反而显得多余。
回文（palindrome） 是指正读反读都一样的单词，例如：
- Racecar
- Level
- Kayak
- Reviver
- Civic
要判断一个字符串是否为回文，你可能会想到：“反转字符串，看是否与原字符串相同”。这已经足够简单明了。
更妙的是，Python 的切片语法 [::-1] 提供了便捷的反转方式：
>>> def is_palindrome(word):
... """如果 word 是回文返回 True，否则返回 False"""
... return word == word[::-1]
...
>>> is_palindrome("foo")
False
>>> is_palindrome("racecar")
True
>>> is_palindrome("civic")
True
这段代码清晰简洁，几乎无需替代方案。但为了趣味，考虑以下递归定义：
- 基础情况：空字符串和单字符字符串天然是回文。
- 递归情况：长度 ≥2 的字符串是回文，当且仅当：
- 首尾字符相同；
- 去掉首尾后的子串也是回文。
利用切片：
- 首字符：
word[0] - 尾字符：
word[-1] - 中间子串：
word[1:-1]
递归实现如下：
>>> def is_palindrome(word):
... if len(word) <= 1:
... return True
... else:
... return word[0] == word[-1] and is_palindrome(word[1:-1])
...
>>> is_palindrome("") # True
>>> is_palindrome("a") # True
>>> is_palindrome("foo") # False
>>> is_palindrome("racecar") # True
>>> is_palindrome("civic") # True
即使在不必要的情况下，思考递归也是一种有趣的练习！
结论
至此，你已完成对递归——这一“函数调用自身”的编程技术——的探索之旅。
递归绝非万能，但某些问题天生呼唤递归。在这些场景中，它是你不可或缺的利器。
在本教程中，你学到了：
- 什么是函数的递归调用
- Python 函数设计如何支持递归
- 选择递归与否的考量因素
- 如何在 Python 中实现递归函数
你还通过多个示例对比了递归与非递归解法。
现在，你应该能够识别何时需要递归，并在必要时自信地使用它！