Posted by on | Featured

递归是指一种函数通过调用自身来解决问题的方法。

一开始这听起来可能有些奇怪——为什么一个函数会调用自己呢？但一旦你理解了其中的原理，就会发现这种做法往往是最自然的方式来用代码表达某些类型的问题。

在本文中，你将了解什么是递归、它在内部是如何工作的，以及如何在Python中使用递归。我们会通过从基础内容到实际应用案例的例子来讲解这些内容。

你可以从GitHub上获取相关代码。

先决条件

在开始学习之前，请确保你满足以下要求：

  • 已安装Python 3.10或更高版本

  • 对Python函数及其工作原理有基本了解

  • 熟悉循环和条件语句

目录

什么是递归？

递归是一种技术，其中函数通过将问题分解为更小的相同问题版本，然后对这些较小的版本再次调用自身来解决问题。

想象一下俄罗斯套娃。要找到最小的那个娃娃，你需要先打开最外层的套娃，然后再打开里面的套娃，依此类推，直到没有更多的套娃可以打开为止。每一步所做的都是同样的动作——打开一个套娃——只不过每次处理的都是规模更小的套娃而已。

这就是递归的本质：相同的操作不断应用于规模逐渐缩小的问题，直到最终达到无需再继续操作的阶段。

每个递归函数都遵循的两条规则

每一个正确的递归函数都必须同时满足以下两点：

1. 基本情况——即函数停止自我调用并直接返回结果的条件。

2>递归情况——即函数使用规模更小或结构更简单的输入版本来再次调用自身的部分。

如果你忘记了基本情况，函数就会无限循环地调用自身，直到Python抛出RecursionError错误。我们稍后会详细讨论这个问题。

你的第一个递归函数

让我们从经典的例子开始：计算阶乘。

n的阶乘（记作n!）是从1到n的所有整数的乘积。因此，5! = 5 × 4 × 3 × 2 × 1 = 120。

注意这个规律：5! = 5 × 4!，而4! = 4 × 3!。每一个阶乘都可以表示为n乘以它下面那个数的阶乘。这种规律非常适合使用递归来求解。

def factorial(n):
    # 基本情况：0或1的阶乘是1
    if n <= 1:
        return 1
    # 递归情况：n! = n * (n-1)!
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(10))

运行这段代码会得到以下结果：

120
3628800

基本情况是n <= 1。当n等于0或1时，函数会停止执行并返回1。递归情况是n * factorial(n - 1)，我们只需要将n乘以它下面那个数的阶乘，剩下的部分就交给递归函数来处理。

Python是如何处理递归调用的

当一个函数调用自身时，Python并不会简单地替换当前的调用——而是将这些调用堆叠起来。每个调用都会等待下面的调用返回结果之后才会结束执行。

让我们一步步追踪factorial(4)的执行过程：

factorial(4)
  └── 4 * factorial(3)
            └── 3 * factorial(2)
                      └── 2 * factorial(1)
                                └── 返回1   ← 基本情况
                      └── 2 * 1 = 2
            └── 3 * 2 = 6
  └── 4 * 6 = 24

每次调用都会被添加到Python的调用栈中。一旦遇到基本情况，调用栈就会开始逐层释放——每个等待中的调用都会得到结果并结束执行。这就是为什么深度递归可能会引发问题：过多的调用会耗尽Python的栈空间。

递归与迭代

对于大多数可以通过递归解决的问题，使用循环也同样可以解决。让我们来比较一下这两种方法在求和运算中的表现。

迭代方法：

def sum_iterative(numbers):
    total = 0
    for n in numbers:
        total += n
    return total

递归方法：

def sum_recursive(numbers):
    if not numbers:       # 基本情况：空列表
        return 0
    return numbers[0] + sum_recursive(numbers[1:])

print(sum_recursive([10, 20, 30, 40]))

递归版本的代码执行结果如下：

100

递归方法的思路是：一个列表的和等于它的第一个元素加上其余所有元素的和。基本情况是空列表，其和为0。

迭代方法和递归方法都可以解决问题，但递归在表达问题时往往更为直观，更符合人们用自然语言描述问题的方式；而在Python中，迭代方法通常效率更高。知道何时使用哪种方法是需要通过实践来积累的经验。

处理嵌套数据

在这里，递归的作用就真正体现出来了。循环非常适合处理扁平结构的数据，但对于嵌套结构——比如文件夹树或深度嵌套的字典——仅使用循环来处理往往会显得很不方便。

假设你有一个表示产品目录的嵌套字典，而你想找出其中所有的价格信息：

catalog = {
    "electronics": {
        "laptops": {
            "ThinkPad X1": 1299.99,
            "MacBook Air": 1099.99
        },
        "accessories": {
            "USB-C Hub": 49.99,
            "Laptop Stand": 34.99
        }
    },
    "stationery": {
        "Notebook A5": 8.99,
        "Gel Pen Set": 12.49
    }
}

def find_all_prices(data):
    prices = []
    for value in data.values():
        if isinstance(value, dict):
            # 如果是一个嵌套字典，就递归地处理它
            prices.extend(find_all_prices(value))
        else:
            # 如果是一个数字，就把它添加到价格列表中
            prices.append(value)
    return prices

all_prices = find_all_prices(catalog)
print(f"所有价格信息：{all_prices}")
print(f"总库存价值：${sum(all_prices):.2f}")

这个函数会检查每个值。如果是一个字典，就会递归地处理它；如果是一个数字，就会被添加到价格列表中。

如果使用嵌套循环来实现这个功能，你就需要事先知道结构的深度。而递归则不需要关心结构的深度。

输出结果：

所有价格信息：[1299.99, 1099.99, 49.99, 34.99, 8.99, 12.49]
总库存价值：$2506.44

递归遍历树结构

一棵树是一种这样的数据结构：每个节点都可以有子节点，而每个子节点本身也是一棵树。这种自相似的结构非常适合用递归函数来处理。

让我们构建一个简单的文件系统树结构，并计算所有文件的总大小：

class FileNode:
    def __init__(self, name, size=0, children=None):
        self.name = name
        self.size = size  # 文件夹的大小为0
        self.children = children or []

def total_size(node):
    # 基本情况：如果这个节点没有子节点，那么它的大小就是它本身的值
    if not node.children:
        return node.size
    # 递归情况：将这个节点的大小加上所有子节点的大小之和
    return node.size + sum(total_size(child) for child in node.children)

# 构建一个简单的文件系统树结构
project = FileNode("project", children=[
    FileNode("src", children=[
        FileNode("main.py", size=12400),
        FileNode("utils.py", size=5800),
    ],
    FileNode("data", children=[
        FileNode("sales_jan.parquet", size=302914),
        FileNode("sales_feb.parquet", size=289000),
    ],
    FileNode("README.md", size=3200)
])

print(f"整个项目文件的总大小为：{total_size(project):,}字节")
print(f"仅源代码文件的大小为：{total_size(project.children[0]):,}字节")

对于每一个节点，我们要么直接返回它的大小（基本情况：当该节点是一个文件时），要么将其大小加到其所有子节点的大小之和上（递归情况：当该节点是一个文件夹时）。代码的结构与树的结构是一致的。

运行上述代码后，将会得到如下输出：

项目总大小：613,314字节
仅源文件的大小：18,200字节

记忆化技术：解决递归调用速度慢的问题

递归算法有时会进行大量的重复计算。一个典型的例子就是斐波那契数列，其中每个数字都是前两个数字之和。

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

这种实现方式虽然可行，但fib(35)的运算过程会花费相当长的时间。问题在于fib(30)这个值会在不同的计算路径中被反复计算数十次。

解决这个问题的方法是使用记忆化技术，也就是将已经计算过的结果保存起来，避免重复计算。在Python中，可以使用functools.lru_cache来实现这一功能，使用方法如下：

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(10))
print(fib_fast(50))
print(fib_fast(100))

输出结果：

55
12586269025
354224848179261915075

添加@lru_cache后，每次调用fib_fast(n)时，都会直接返回之前计算过的结果，而不会重新进行计算。

注意：只要你的递归函数可能会多次遇到相同的子问题，使用记忆化技术都是非常有意义的。

Python的递归限制

Python默认设置的递归限制为1000次调用。如果你的函数递归次数超过了这个限制，就会引发RecursionError：

def countdown(n):
    if n == 0:
        return "完成"
    return countdown(n - 1)

print(countdown(5))     # 可以正常运行
print(countdown(2000))  # 会引发RecursionError

在这里，countdown(5)可以正常运行并输出“完成”，而countdown(2000)则会因为超过了1000次的递归限制而出现错误。

完成
RecursionError: 最大递归深度已超出

你可以通过sys.setrecursionlimit()来调整这个限制值，但通常情况下，如果使用迭代或记忆化技术能够更有效地解决某个问题，那么就没有必要提高递归限制。

import sys
sys.setrecursionlimit(5000)  # 使用时需谨慎

对于大多数树形数据结构的遍历操作以及分治算法来说，默认的递归限制已经足够使用了。只有在对非常复杂的输入结构进行处理时，才会遇到这个限制。

何时应该使用递归

在以下情况下，递归是一种非常合适的选择：

  • 问题的结构本身就具有自相似性——例如树结构、图结构、嵌套数据或文件系统。

  • 当你需要使用分治算法来实现功能时，比如归并排序、二分搜索或快速排序。

  • 递归解决方案比迭代方案更易于理解。

  • 在编译时无法确定该结构的深度。

然而，在以下情况下，应优先选择迭代方法：

  • 当你处理的是扁平数据结构时，比如对列表求和或在数组中搜索元素。

  • 当性能要求极高时——Python并不会对尾递归进行优化，因此深度递归会带来额外的开销。

  • 当输入数据量非常大或者结构层次非常深时，使用递归可能会导致“RecursionError”错误。

总结

虽然刚开始使用递归时会感到有些困难，但其基本原理其实很简单：先解决问题的简化版本，让函数去处理剩余的部分，并且一定要定义一个终止条件来防止无限递归。

你已经掌握了递归的一些基础知识，包括调用栈的工作原理、如何处理嵌套数据、如何遍历树结构，以及如何通过记忆化技术提高程序的执行效率。这些技巧在实际开发中非常常用，尤其是在处理文件系统、解析器或层次化数据时。

要想真正掌握递归，最好的方法就是先选择一个适合的问题，尝试用递归的方式来解决它，而不是直接使用循环结构。每次这样练习之后，你对递归的理解都会加深一些。你也可以在HackerRank或LeetCode上做一些相关的编程练习题来巩固所学。

祝编码愉快！

Tags:
Comments are closed.