递归与迭代

递归与迭代是编程中两种基本的控制结构，用于解决需要重复执行任务的问题。它们在算法设计中扮演着重要角色，理解它们的区别和应用场景是掌握算法基础的关键。

概念介绍

递归（Recursion）

递归是一种通过函数调用自身来解决问题的方法。一个递归函数通常包含两个部分：

• 基线条件（Base Case）：定义递归何时终止，防止无限递归。
• 递归条件（Recursive Case）：将问题分解为更小的子问题，并调用自身解决。

递归的优点是代码简洁，适合解决分治问题（如树遍历、排序算法等）。缺点是可能因调用栈过深导致栈溢出，且效率可能低于迭代。

迭代（Iteration）

迭代是通过循环结构（如 `for`、`while`）重复执行一段代码直到满足条件。迭代通常使用计数器或状态变量控制循环次数。

迭代的优点是性能较高（无函数调用开销），内存占用更少。缺点是某些问题（如分治、回溯）的代码实现可能较复杂。

代码示例

递归示例：计算阶乘

以下是递归计算阶乘的示例：

def factorial(n):
    # 基线条件
    if n == 0 or n == 1:
        return 1
    # 递归条件
    else:
        return n * factorial(n - 1)

# 输入与输出
print(factorial(5))  # 输出: 120

解释： 1. 基线条件：当 `n` 为 0 或 1 时，直接返回 1。 2. 递归条件：将问题分解为 `n * factorial(n - 1)`，逐步缩小问题规模。

迭代示例：计算阶乘

以下是迭代实现阶乘的示例：

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# 输入与输出
print(factorial_iterative(5))  # 输出: 120

解释： 1. 初始化 `result` 为 1。 2. 通过循环从 1 累乘到 `n`，得到阶乘结果。

递归与迭代的对比

特性	递归	迭代
代码简洁性	高（适合分治问题）	低（需手动管理状态）
内存占用	高（调用栈开销）	低（无额外调用）
适用场景	树遍历、回溯、分治	简单循环、线性问题

实际应用案例

案例1：斐波那契数列

斐波那契数列是递归的经典案例，但递归效率较低（指数时间复杂度）。迭代或记忆化递归更高效。

递归实现：

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

迭代实现：

def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

案例2：文件系统遍历

递归适合处理嵌套结构（如目录树）：

import os

def list_files(path):
    for entry in os.listdir(path):
        full_path = os.path.join(path, entry)
        if os.path.isdir(full_path):
            list_files(full_path)  # 递归调用
        else:
            print(full_path)

递归与迭代的转换

任何递归问题均可通过显式栈转换为迭代，反之亦然。例如，以下是使用栈模拟递归的阶乘实现：

def factorial_stack(n):
    stack = []
    result = 1
    stack.append(n)
    while stack:
        current = stack.pop()
        if current == 1:
            break
        result *= current
        stack.append(current - 1)
    return result

性能优化

递归可能因重复计算导致性能问题（如斐波那契数列）。可通过以下方法优化：

• 记忆化（Memoization）：缓存已计算结果。
• 尾递归优化：某些语言（如Scheme）支持，但Python默认不支持）。

记忆化斐波那契示例：

from functools import lru_cache

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

总结

• 选择递归还是迭代取决于问题特性和语言支持。
• 递归适合分治问题，但需注意栈溢出和性能。
• 迭代适合线性问题，效率更高但代码可能冗长。
• 实际开发中可结合两者优势（如递归思路 + 迭代实现）。