递归 (Recursion)

递归是指函数自己调用自己。它是很多高级算法（如分治、搜索、树与图的遍历）的基础。

递归的三要素

编写递归函数时，必须明确以下三点：

1. 基本情况 (Base Case): 递归终止的条件。如果没有这个，程序会无限循环导致栈溢出。
2. 递归关系 (Recurrence Relation): 将大问题分解为小问题的公式。
3. 函数定义: 明确这个函数输入什么，返回什么。

示例 1：计算阶乘 (Factorial)

\(n! = n \times (n-1) \times \dots \times 1\)

• Base Case: 当 \(n=1\) 时，返回 1。
• 递归关系: \(n! = n \times (n-1)!\)

def factorial(n):
    # 1. Base Case
    if n == 1:
        return 1

    # 2. 递归调用
    return n * factorial(n - 1)

print(factorial(5)) # 120

示例 2：斐波那契数列 (Fibonacci)

数列：1, 1, 2, 3, 5, 8, 13...
公式：\(F(n) = F(n-1) + F(n-2)\)

def fib(n):
    # 1. Base Case
    if n == 1 or n == 2:
        return 1

    # 2. 递归关系
    return fib(n - 1) + fib(n - 2)

print(fib(6)) # 8

递归的陷阱

上面的斐波那契写法效率极低 (\(O(2^n)\))，因为它进行了大量的重复计算。例如计算 fib(5) 时，fib(3) 会被计算两次。后续章节的动态规划将解决这个问题。

示例 3：汉诺塔问题 (Hanoi Tower)

将 \(n\) 个盘子从 A 移动到 C，中间借用 B。

思路：

1. 先把 \(n-1\) 个盘子从 A 移到 B。
2. 把最大的盘子 (\(n\)) 从 A 移到 C。
3. 最后把 \(n-1\) 个盘子从 B 移到 C。

def hanoi(n, source, target, auxiliary):
    """
    n: 盘子数量
    source: 源柱子
    target: 目标柱子
    auxiliary: 辅助柱子
    """
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return

    # 1. 移走上面的 n-1 个
    hanoi(n - 1, source, auxiliary, target)

    # 2. 移动最底下的 1 个
    print(f"Move disk {n} from {source} to {target}")

    # 3. 把 n-1 个移回来
    hanoi(n - 1, auxiliary, target, source)

hanoi(3, 'A', 'C', 'B')

递归 vs 迭代

特性	递归	迭代 (循环)
代码结构	简洁、符合思维逻辑	可能较繁琐
空间消耗	较大 (调用栈)	小 (\(O(1)\))
适用场景	树/图遍历、分治、回溯	简单的线性遍历

本章小结

递归的核心是相信你的函数：在实现 factorial(n) 时，假设 factorial(n-1) 已经能算出正确结果，你只需要做 \(n \times \text{result}\) 即可。

---

下一章：分治