Python 递归：概念、示例与技巧

递归是编程中的基础概念，在 Python 中尤为重要。它指的是函数通过调用自身来解决问题，将问题分解为更小、更易处理的子问题的技术。 

这种方法能带来简洁优雅的解决方案，特别适用于包含重复性任务或层级结构的问题。在 Python 中，递归被广泛用于各种场景，从排序算法到复杂的数据遍历。

递归解法常常与问题的数学定义相呼应，对于熟悉数学推理的人来说更直观。递归的妙处在于，它能用寥寥数行代码表达复杂算法，使解法既优雅又易读。不过，要掌握递归，需要从更常见的迭代思维转换过来。

本文将探讨递归的概念、其在 Python 中的工作方式及其实际应用，并讨论常见问题以及与迭代的对比。如果您是 Python 新手，建议先学习我们的课程，例如Python 入门、编程范式概念或Python 编程基础。

什么是 Python 中的递归？

在 Python 中，递归是指函数通过调用自身来解决问题。它包含两个关键组成部分：

• 基例（Base case）：用于终止递归的条件。没有它，递归调用会无限进行，最终导致函数崩溃或耗尽内存。
• 递归情形（Recursive case）：将问题分解为更小的部分，并用这些更小的部分再次调用函数。

可以这样理解递归：设想一个函数通过解决同一问题的更小版本来解决复杂问题，直到达到一种不再需要进一步递归的情形。

递归方法遵循“分而治之”的策略，将复杂问题逐步拆解为简单版本，直至达到平凡情形。这常常契合我们自然解决问题的方式。比如整理一副纸牌时，我们可能会先整理更小的一组，再将其合并，这本质上就是像归并排序这样的递归排序算法的工作原理。

每个递归函数都必须至少有一个基例和至少一个递归情形。基例通过提供一个不再需要进一步调用的条件来防止无限递归；递归情形则在每次调用时缩小问题规模，确保最终能达到基例。

递归在 Python 中如何工作？

递归通过让函数以修改后的参数再次调用自身来逐步解决问题。为更具体地理解这一点，考虑计算从1到num的累加和这一任务。

下面是一个用于计算和的简单递归方法：

def sum_recursive(num):
    if num == 1:  # Base case
        return num
    return num + sum_recursive(num - 1)  # Recursive case

print(sum_recursive(3)) # 3 + 2 + 1 

6

在这个函数中，基例是当num == 1时停止递归。否则，函数会以num - 1为参数继续调用自身，直到达到基例。

其逐步工作方式如下：

1. sum_recursive(3) 调用 sum_recursive(2)。
2. sum_recursive(2) 调用 sum_recursive(1)。
3. sum_recursive(1) 返回 1（基例）。
4. 此时，sum_recursive(2) 可返回 2 + 1 = 3，而 sum_recursive(3) 可返回 3 + 3 = 6。

另一个例子是用递归函数计算幂：

def power(base, exponent):
    if exponent == 0:  # Base case
        return 1
    else:
        return base * power(base, exponent - 1)  # Recursive case

print(power(2, 3))

8

该幂函数的逐步解释：

• power(2, 3) 调用 power(2, 2)。
• power(2, 2) 调用 power(2, 1)。
• power(2, 1) 调用 power(2, 0)。
• power(2, 0) 返回 1（基例）。
• 然后回溯：power(2, 1) 返回 2 * 1 = 2。
• 接着 power(2, 2) 返回 2 * 2 = 4。
• 最后 power(2, 3) 返回 2 * 4 = 8。

当调用递归函数时，每一次递归调用都会在调用栈上创建一个新条目。这个栈会记录所有函数调用及其变量。当达到基例后，栈会按相反顺序逐一回退，逐步计算出最终结果。

理解这种栈行为至关重要，因为它解释了 Python 中递归的力量与局限：它能优雅地保留上下文，但在深度递归时也可能导致内存问题。

用递归在 Python 中实现阶乘

阶乘函数是演示递归的经典示例。数值 n 的阶乘，记作 n!，是小于或等于 n 的所有正整数之积。数学上：

n! = n × (n − 1) × (n − 2) × … × 1

递归地，阶乘函数可定义为：

n! = n × (n − 1)!

让我们在 Python 中实现它：

def compute_factorial(num):
    if num == 0:  # Base case
        return 1
    return num * compute_factorial(num - 1)  # Recursive case

print(compute_factorial(4)) # 4 * 3 * 2 * 1

24

代码逐步解释：

• 函数 compute_factorial(num) 检查 num == 0 时返回 1。
• 否则返回 num * compute_factorial(num - 1)，即用更小的 num 值调用自身。

阶乘函数很好地体现了递归的优雅。其数学定义本身就是递归的，使代码实现直观且紧贴数学概念。这正是递归的一大优势：它让代码能够直接表达数学定义。

需要注意边界情况。例如，阶乘通常仅对非负整数有定义。健壮的实现应包含对负数输入的错误处理或类型检查。

此外，对于很大的 num 值，递归解法可能导致栈溢出，这一限制将在后文详细讨论。

常见问题：如何修复 Python 中的递归错误

尽管递归功能强大，但也容易出现一些常见问题，例如：

超过最大递归深度

Python 的默认递归深度限制为 1000 次调用。如果递归函数调用自身过多，将引发 RecursionError。

解决方法如下：

您可以使用 sys.setrecursionlimit() 增加递归深度。不过，除非必要，不建议这样做，因为可能导致栈溢出。

import sys  

# Get the current recursion limit
current_limit = sys.getrecursionlimit()
print(f'Current limit: {current_limit}')  

# Set a new recursion limit to 200
new_limit = 200
sys.setrecursionlimit(new_limit)  

# Get the new recursion limit
changed_current_limit = sys.getrecursionlimit()
print(f'Current limit after change: {changed_current_limit}')  

Current limit: 1000
Current limit after change: 200

缺少基例

缺失或错误的基例会导致函数无限递归，最终引发栈溢出。

要修复此问题，请确保基例定义清晰且可达。

如何在 Python 中终止递归

终止递归的关键在于定义恰当的基例。没有基例，递归将永无止境并导致错误。

例如，在前面实现的阶乘函数中，基例是 if num == 0，它会终止递归。总体来说，您需要确保每个递归函数都具备一个使其终止的条件。

要设计有效的基例，需要仔细思考。建议包括：

• 找出可以直接解决的最简单问题形式。
• 确保所有递归路径最终都能到达基例。
• 单独测试边界情况，确认已被正确处理。
• 如有需要，可设置多个基例。

有时，防御式编程技巧也很有帮助，例如增加针对无效输入的保护或运行时检查，以防止过深递归。例如：

def safe_factorial(num, depth=0, max_depth=100):
    # Check if recursion is too deep
    if depth > max_depth:
        raise ValueError("Maximum recursion depth exceeded")
   
    # Base case
    if num <= 0:
        return 1
   
    # Recursive case with depth tracking
    return num * safe_factorial(num - 1, depth + 1, max_depth)

# Calculate factorial of 5 with default depth limits
result = safe_factorial(5)

print(result) 

120

# Calculate factorial of 5 with depth > max_depth
result = safe_factorial(5, depth=20, max_depth=10)

print(result) 

ValueError: Maximum recursion depth exceeded

这种方式允许您设置自定义限制，并提供比默认 RecursionError 更有意义的错误信息。

下面是另一个示例，展示了定义基例的不同方式：使用递归求两个数的最大公约数（GCD）。

两个数 x 和 y 的 GCD 可用欧几里得算法以及取模运算符 % 来计算：

• 基例：若 y == 0，则 GCD 为 x。
• 递归情形：否则，x 与 y 的 GCD 与 y 与 x % y 的 GCD 相同。

def find_gcd(x, y):
    # Base case: if y is 0, the GCD is x
    if y == 0:
        return x
    # Recursive case: GCD of y and x % y
    return find_gcd(y, x % y)

print(find_gcd(48, 18))  

6

Python 中的递归 vs. 迭代

递归与迭代常常都能解决相同的问题，但各有利弊：

• 递归通常更优雅、易懂，尤其对那些天然具有递归结构的问题（如树遍历、阶乘、斐波那契数列）。
• 迭代更高效，因为不涉及多次函数调用的开销，也能避免栈溢出问题。迭代解法通常更省内存。

何时使用递归：

• 当问题可自然分解为更小的子问题时。
• 处理层级数据结构（如树）时。
• 当递归形式更直观且能带来更整洁的代码时。
• 当代码可读性优先于性能优化时。
• 在处理深度未知的数据（如解析嵌套的 JSON 或 XML）时。

何时使用迭代：

• 当问题需要重复性操作而不需要将其拆分为更小子问题时。
• 对性能要求高、深度递归可能导致高内存占用的任务。
• 处理可能超出递归限制的大型数据集时。
• 当内存占用是首要关注点时。
• 针对天然是顺序而非层级的问题。

我们来比较同一问题（计算从 1 到 num 的累加和）的递归与迭代实现：

递归：

def sum_recursive(num):
    if num == 1:
        return 1
    else:
        return num + sum_recursive(num - 1)

迭代：

def iterative_sum(num):
    total = 0
    for i in range(1, num + 1):
        total += i
    return total

迭代版本使用循环累计求和，而递归版本将问题分解为把 n 与从 1 到 num - 1 的和相加。两种方案都可行，但对较大的 num 值，迭代版本更高效，因为它不涉及多次函数调用的开销。

一些天然递归的问题可以通过使用栈或队列来模拟递归调用，从而转换为迭代解法。这在处理树或图的遍历时尤其有用。

Python 中递归的实用示例

递归可用于多种有趣的问题：

1. 计算斐波那契数

斐波那契数列递归定义为：

• F(0) = 0
• F(1) = 1
• F(n) = F(n − 1) + F(n − 2)

由此得到的数列为：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

实现如下：

def compute_fibonacci(num):
    if num <= 0:
        return 0
    elif num == 1:
        return 1
    return compute_fibonacci(num - 1) + compute_fibonacci(num - 2)

print(compute_fibonacci(6))

8

不过，这种朴素实现会多次重复计算。更高效的方法是使用备忘录（memoization），即缓存已计算的结果，避免冗余计算，从而显著降低计算时间：

def optimized_fibonacci(num, cache=None):
    if cache is None:
        cache = {}
    if num in cache:
        return cache[num]
    if num <= 1:
        return num
    cache[num] = optimized_fibonacci(num - 1, cache) + optimized_fibonacci(num - 2, cache)
    return cache[num]

还可以使用 functools 模块中的 lru_cache() 装饰器进一步简化：

from functools import lru_cache

@lru_cache(maxsize=None)  # Cache all computed values
def cached_fibonacci(num):
    if num <= 1:
        return num
    return cached_fibonacci(num - 1) + cached_fibonacci(num - 2)

2. 遍历嵌套数据结构

递归也非常适合处理嵌套数据结构，如列表的列表或 JSON 对象。例如，遍历目录树结构或递归地将嵌套列表拍平。

def flatten(nested):
    result = []
    for element in nested:
        if isinstance(element, list):
            result.extend(flatten(element))
        else:
            result.append(element)
    return result

nested_structure = [1, [2, 3], [4, [5, 6]]]

print(flatten(nested_structure))  

[1, 2, 3, 4, 5, 6]

3. 排序算法（如快速排序或归并排序） 

快速排序与归并排序等排序算法高度依赖递归。它们将问题拆解为更小的子问题，并递归地完成排序。

下面是一个简单的快速排序实现：

def quicksort_algo(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    lower = [item for item in array if item < pivot]
    equal = [item for item in array if item == pivot]
    greater = [item for item in array if item > pivot]
    return quicksort_algo(lower) + equal + quicksort_algo(greater)

array = [220, 33, 400, 150, 16]

print(quicksort_algo(array))

[16, 33, 150, 220, 400]

结语

递归是 Python 中一种强大的思想，通过将复杂问题拆解为更简单的子问题来求解。若运用得当，递归能带来整洁、简练且易于理解的代码。

不过，务必正确定义基例，并留意递归深度，以避免常见错误。

尽管在某些情况下递归不如迭代高效，但对于层级数据或天然适合递归的问题来说，它依然是不可或缺的工具。

通过理解递归并练习诸如阶乘、斐波那契数列及排序算法等示例，您将能够在 Python 项目中熟练运用递归。

如果您对可以运用递归的更高级 Python 主题感兴趣，欢迎查看以下学习路径：Python 编程、Python 数据分析师以及Python 助理数据科学家