递归的基本原理——像套娃一样的函数

递归就像套娃——函数自己调用自己

你有没有玩过俄罗斯套娃？一个娃娃里面装着更小的娃娃，打开再打开，直到最小的那个。递归就像这样：一个函数在执行过程中，调用它自己（就像套娃里还有自己），每次解决一个更小的问题，直到遇到最简单的情况（最小的娃娃），然后一层层返回结果。

递归是程序设计中一种强大的方法。它适合解决那些可以分解成相同结构但规模更小的问题。比如计算阶乘、遍历文件夹、画分形图，甚至玩汉诺塔游戏，都能用递归轻松搞定。

递归的两大法宝：终止条件 + 递归步骤

要想递归不出错，必须牢牢把握两点：

终止条件（又叫基线条件）：必须有一个“最小娃娃”的情况——这时递归不再继续，直接返回结果。否则就会无限调用自己，就像永远打不开的套娃，程序最后会崩溃（栈溢出）。
递归步骤：每次调用自己时，问题的规模要变小（比如数字减1、链子变短），一步步靠近终止条件。

小提示：写递归时，先想好终止条件，再写递归步骤。就像先找到最小的套娃，再一层层套回去。

生活中的递归：倒计时、爬楼梯、吃巧克力

?️ 倒计时（从 N 数到 1）

你写一个“倒计时”函数：如果数字是1，就喊“1”然后结束；否则先喊当前数字，再调用自己（数字减1）继续喊。这个过程是不是很像套娃？每一层喊的数字，就是一层娃娃。

def countdown(n):
    # 终止条件：当 n 等于 0 时，什么都不做直接返回
    if n == 0:
        return
    # 先输出当前数字
    print(n)
    # 递归步骤：减少1，继续倒数
    countdown(n - 1)

countdown(5)  # 输出：5 4 3 2 1

?️ 爬楼梯（有多少种走法）

假设你每次可以走1级或2级楼梯，要走到第n级，有多少种不同走法？这个问题可以递归思考：到第n级的方法数 = 到第n-1级的方法数 + 到第n-2级的方法数。终止条件：到第1级有1种（一次跨1步），到第2级有2种（1+1或一次跨2步）。

def climb_stairs(n):
    # 终止条件：第1级和第2级已知
    if n == 1:
        return 1
    if n == 2:
        return 2
    # 递归步骤：两种走法加起来
    return climb_stairs(n - 1) + climb_stairs(n - 2)

print(climb_stairs(5))  # 输出8种

? 吃巧克力棒（分一半）

你有n块巧克力，每天吃一半（如果块数是奇数，先吃掉1块再吃一半），到什么时候吃完？这也是递归：如果n=0，已经吃完了；否则先吃掉n块，再递归处理剩下的（n-1）或者（n//2）。不过这里只是例子，实际应用更常见的是二分查找。

递归是怎样运行的？——借助“调用栈”理解

计算机用“栈”来管理函数调用。每次调用函数，就把当前函数的信息（参数、返回地址）压入栈顶。递归时，一层层调用自己，栈就一层层增高。当到达终止条件后，函数开始返回，栈一层层弹出。

用阶乘 factorial(5) 看一下：

factorial(5) → 5 * factorial(4)
    factorial(4) → 4 * factorial(3)
        factorial(3) → 3 * factorial(2)
            factorial(2) → 2 * factorial(1)
                factorial(1) → 1 * factorial(0)
                    factorial(0) → 1  （终止条件）
                返回 1 * 1 = 1 给上一层
            返回 2 * 1 = 2
        返回 3 * 2 = 6
    返回 4 * 6 = 24
返回 5 * 24 = 120

就像先一层层打开套娃，到最小的一个，再一层层套回来。

新手最容易掉进的三个坑

❌ 坑1：忘记写终止条件

def bad_factorial(n):
    # 没有终止条件！
    return n * bad_factorial(n - 1)

这会导致函数无限调用自己，最终报错 RecursionError: maximum recursion depth exceeded（递归深度超出限制）。一定记得写终止条件。

❌ 坑2：递归步骤没有让问题变小

def infinite(n):
    if n == 0:
        return
    # 参数没变小，还变大了！
    infinite(n + 1)

同样会无限递归。要确保每次调用都向终止条件靠近（比如 n-1 而不是 n+1）。

❌ 坑3：参数类型或边界搞错

比如爬楼梯的例子中，climb_stairs(n) 如果n=0时没有处理，而递归中的 n-2 可能变成负数，导致程序出错。所以终止条件要覆盖所有边界。

完整示例：带过程打印的阶乘计算

下面是一个可以让中小学生看清递归过程的完整程序。它会在每次调用和返回时打印信息，就像看套娃打开和合上的样子。

def factorial(n):
    """
    计算 n 的阶乘，并打印递归过程
    """
    print(f"进入 factorial({n})")
    
    # 终止条件：0! = 1
    if n == 0:
        print(f"到达最小套娃：factorial(0) 返回 1")
        return 1
    
    # 递归步骤：n! = n * (n-1)!
    result = n * factorial(n - 1)
    
    print(f"返回 {n} * factorial({n-1}) = {n} * {result // n} = {result}")
    return result

# 调用并输出最终结果
num = 5
print(f"{num}! = {factorial(num)}")

运行这段代码，你会看到类似下面的输出（缩进可以理解层次）：

进入 factorial(5)
进入 factorial(4)
进入 factorial(3)
进入 factorial(2)
进入 factorial(1)
进入 factorial(0)
到达最小套娃：factorial(0) 返回 1
返回 1 * factorial(0) = 1 * 1 = 1
返回 2 * factorial(1) = 2 * 1 = 2
返回 3 * factorial(2) = 3 * 2 = 6
返回 4 * factorial(3) = 4 * 6 = 24
返回 5 * factorial(4) = 5 * 24 = 120
5! = 120

每一步都清晰展示了“打开套娃”和“合上套娃”的过程。

更多练习：斐波那契数列

斐波那契数列从0和1开始，后面每个数都是前两个数之和：0, 1, 1, 2, 3, 5, 8, 13, ... 求第n项（n从0开始）也可以用递归写：

def fibonacci(n):
    # 终止条件：第0项是0，第1项是1
    if n == 0:
        return 0
    if n == 1:
        return 1
    # 递归步骤：第n项 = 第n-1项 + 第n-2项
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))  # 输出13

注意：这个简单的递归写法效率很低（有很多重复计算）。以后学了“记忆化”或“动态规划”就能优化它。