理解递归函数，从简单例子到复杂应用

科普 2025年03月13日 11:17 88 高柯

从简单例子到复杂应用

递归函数是编程中一个强大而优雅的概念，它允许我们用简洁的方式解决复杂的问题，尽管递归函数在初学者眼中可能显得有些抽象和难以理解，但通过一些生动的实例和深入的解析,我们可以逐步揭开它的神秘面纱。

什么是递归函数？

递归函数是一种在其定义或实现中调用自身的函数，换句话说，递归函数会在满足一定条件时，反复调用自身来解决问题，递归的核心思想是将一个大问题分解成若干个较小的、相似的子问题,直到这些子问题变得足够简单可以直接求解为止。

为了防止无限递归,递归函数必须包含两个基本要素：

基准条件（Base Case）：这是递归终止的条件，当满足该条件时，函数不再调用自身,而是直接返回结果。
递归步骤（Recursive Step）：这是函数调用自身的部分，通常会传递一个更小规模的参数给下一次调用,逐渐逼近基准条件。

简单的递归函数示例

让我们从一个最经典的递归函数例子开始——计算阶乘（Factorial），阶乘是一个非常直观的例子,可以帮助我们理解递归的基本原理。

计算阶乘

阶乘的定义如下： [ n! = n \times (n-1) \times (n-2) \times \ldots \times 1 ]

5 的阶乘（5!）等于 ( 5 \times 4 \times 3 \times 2 \times 1 = 120 )。

我们可以用递归函数来实现阶乘的计算：

理解递归函数，从简单例子到复杂应用

def factorial(n):
    # 基准条件：当 n 为 0 或 1 时，返回 1
    if n == 0 or n == 1:
        return 1
    # 递归步骤：n * factorial(n-1)
    else:
        return n * factorial(n - 1)
print(factorial(5))  # 输出 120

在这个例子中，factorial 函数首先检查 n 是否为 0 或 1，如果是，则直接返回 1（这就是基准条件），否则，它会调用自己并传入 n-1 作为参数，最终返回 n * factorial(n-1)，这个过程会一直持续到 n 变为 0 或 1 为止。

更复杂的递归函数示例

除了简单的阶乘计算，递归函数还可以用于解决更复杂的问题，我们将探讨几个更具挑战性的例子,以展示递归的强大功能。

斐波那契数列

斐波那契数列是一个著名的数学序列，每一项都是前两项之和，形式如下： [ F(n) = F(n-1) + F(n-2) ] ( F(0) = 0 )，( F(1) = 1 )。

我们可以使用递归来实现斐波那契数列的计算：

def fibonacci(n):
    # 基准条件：当 n 为 0 或 1 时，直接返回 n
    if n <= 1:
        return n
    # 递归步骤：fibonacci(n-1) + fibonacci(n-2)
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(10))  # 输出 55

这个递归实现虽然直观，但在计算较大的 n 时效率较低，因为它会导致大量的重复计算，为了提高效率，我们可以使用记忆化技术（Memoization），将已经计算过的结果存储起来,避免重复计算。

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]
print(fibonacci_memo(10))  # 输出 55

汉诺塔问题

汉诺塔问题是另一个经典的递归问题，问题描述如下：有三根柱子 A、B 和 C，A 上有 n 个大小不同的圆盘，按照从小到大的顺序排列，要求将所有圆盘从 A 移动到 C，每次只能移动一个圆盘,并且任何时候都不能将较大的圆盘放在较小的圆盘上。

我们可以用递归来解决这个问题：

def hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, target, auxiliary)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, source, target)
hanoi(3, 'A', 'B', 'C')

这段代码展示了如何通过递归将问题分解成更小的子问题,最终完成整个任务。