递归：自己调用自己

这是什么：递归（Recursion） = 函数在内部调用自己，像套娃，但往往是很多难题的最短解法。

为什么用：排序会了，来学一个"烧脑但优雅"的武器。有些问题拆成"大问题 + 小一号的大问题"特别顺，用循环写反而绕，递归几句话就够。

如何用：本章先讲递归的两条铁律——基准情形和递归步骤，再用阶乘做第一道题。

递归两要素

自己调用自己，怎么不变成无限套娃？靠两条铁律：

1. 基准情形：一个"不用再递归"的出口，直接给出答案
2. 递归步骤：把大问题缩小一圈，交给"下一个自己"

记住这句：每次调用都要离出口更近一步。缺任何一条，程序就撞车（Python 会报 RecursionError：递归太深）。

经典第一题：阶乘

5 的阶乘 = 5 × 4 × 3 × 2 × 1。用数学话讲：n! = n × (n-1)!，而 1! = 1——看，定义本身就是递归的！

def factorial(n):
    if n <= 1:                    # 基准情形：出口
        return 1
    return n * factorial(n - 1)   # 递归步骤：问题缩小一圈

print(factorial(5))

你会看到：

120

调用像洋葱一样展开：factorial(5) 等 factorial(4)，它又等 factorial(3)……直到 factorial(1) 直接返回 1，答案再一层层乘回来：1 × 2 × 3 × 4 × 5 = 120。

经典第二题：斐波那契

数列 1, 1, 2, 3, 5, 8……每个数都是前两个之和：

def fib(n):
    if n <= 2:                          # 基准情形：前两个数都是 1
        return 1
    return fib(n - 1) + fib(n - 2)      # 递归步骤：前两个之和

print(fib(1), fib(2), fib(3), fib(4), fib(5), fib(6))

你会看到：

1 1 2 3 5 8

优雅！但埋个伏笔：这个朴素版很慢——同一个数会被反反复复算好多遍（比如算 fib(6) 时 fib(4) 被算了 2 次，数字越大重复越夸张）。怎么治？下一章的"记住答案"专门收拾它。

递归 vs 循环

同一个阶乘，循环也能写：

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

print(factorial_loop(5))

你会看到：

120

两者能互相改写。选哪个？问题长得像树，用递归；问题是一条线，用循环。

逐概念解读

记忆口诀

递归两件套：出口 + 缩小；每层调用都要离出口更近。

动手改

1. 算一算 factorial(10)（提示：答案是 3628800），再想想 factorial(0) 会返回什么
2. 给 fib 加一行 print("算", n)，跑 fib(6)，数数同一个数被算了几遍
3. 用循环写出"1 加到 n"（n=100 得 5050），再用递归重写一遍

下一章：贪心与动态规划，治一治慢递归 🐸