5.4 递归

递归（recursion）是函数调用自己的过程。递归可以把复杂问题拆成更小的同类问题，但它也更容易造成重复计算和调用栈增长。

递归的两个条件

一个递归函数（recursive function）通常需要两部分：

• 基本情况（base case）：不再继续递归，直接返回结果。
• 递归情况（recursive case）：把问题缩小，然后调用自己。

如果没有基本情况，函数会一直调用自己，最终导致栈溢出（stack overflow）。

def tell_story():
    print("从前有座山，山里有座庙")
    print("庙里有个老和尚")
    print("老和尚在对小和尚讲故事：")
    tell_story()

这个函数没有停止条件，因此不能正常结束。

阶乘

阶乘（factorial）是递归入门的经典例子。

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

print("5! = %d" % factorial(5))

运行结果：

5! = 120

factorial(5) 不会马上得到结果。它会先调用 factorial(4)，再调用 factorial(3)，直到遇到 factorial(1)。然后结果才会一层层返回。

Ackermann 函数

Ackermann 函数是一个经典递归例子。它不像阶乘那样只把 n 减 1，而是根据 m 和 n 的组合进入不同递归分支。

def ackermann(m, n):
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))

print(ackermann(2, 2))

运行结果：

7

这个函数非常适合观察“递归里面再嵌套递归”的结构，但它增长极快。初学时只用很小的输入，例如 ackermann(2, 2) 或 ackermann(3, 1)。

递归的代价

递归代码常常很简洁，但每一次递归都会产生一次函数调用。如果问题规模很大，递归可能会非常慢，甚至导致栈溢出。

以斐波那契数列（Fibonacci sequence）为例：

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

print(fibonacci(7))

运行结果：

13

这个递归版本会重复计算很多次。例如 fibonacci(5) 和 fibonacci(4) 内部都会继续计算 fibonacci(3)。对于较大的 n，这种重复会变得非常明显。

汉诺塔

有些问题天生适合递归。汉诺塔（Tower of Hanoi）的思路是：

1. 把上面的 n - 1 个盘子从源柱移动到辅助柱。 2. 把最大盘从源柱移动到目标柱。 3. 把 n - 1 个盘子从辅助柱移动到目标柱。

move = 0

def hanoi(n, src, mid, dst):
    global move

    if n == 1:
        print(src, "->", dst)
        move += 1
    else:
        hanoi(n - 1, src, dst, mid)
        print(src, "->", dst)
        move += 1
        hanoi(n - 1, mid, src, dst)

hanoi(3, "A", "B", "C")
print("移动次数：%d" % move)

运行结果：

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
移动次数：7

每一步看起来只是移动一个盘子，但背后的递归任务是“先移动上面的 n - 1 个盘子，再移动最大的盘子”。下面的组件可以逐步观察盘子如何在三根柱子之间移动。

递归不是为了“看起来高级”，而是为了让某些本来就具有自相似结构的问题更容易表达。