波仔
⌨️ 第四章 流程图与算法
📄 一句话概括

递归＝函数调用自己：每一层【改小参数】交给下一层，到基线条件收工层层返回——它优雅得像定义本身，但每一层都要压一层栈，没有出口的递归就是 Stack Overflow；尾递归是它的省栈改写，可惜 CPython 偏不优化。

📝 本节和前面几节的关系

4-3 的循环是【转圈】，递归是【套娃】——两口气能互相改写。回收 3-16 的函数调用栈（递归深度＝栈叠多高）与树莓派课第九章的 while True（硬件里同理不能没有出口）。

一、递归：自己调用自己

写递归只缺两样——基线条件（什么时候停）与递归条件（怎么改小）：

def factorial(n):          # n 的阶乘：n! = n x (n-1)!
    if n <= 1:             # 基线：1! = 1，到此为止
        return 1
    return n * factorial(n - 1)   # 递归：改小一档交给下一层

print(factorial(5))        # 120

factorial(5) 的展开：5 x factorial(4) → 4 x factorial(3) → … → factorial(1) 返回 1 → 层层乘回来得 120。每层只信【下一层会给对答案】，自己只管乘——这种【我不管你怎么算，你返回对的我就能算对】的信任结构，正是递归的灵魂。

递归最适合【问题长得像自己缩小版】的活儿：树的遍历（3-17 的子树就是缩小版树）、目录扫描（文件夹套文件夹）、汉诺塔、快排（4-13 就靠它）。

二、栈与深度：递归的物理账

每次函数调用压一层栈帧（3-16），递归 N 层就叠 N 层——栈的空间是有限的：

三、尾递归：可以不叠栈的递归

普通递归返回后还有事干（乘 n）——必须留着栈帧等；尾递归把【收尾计算】挪到递归调用之前完成，调用后无事可做：

def fact_tail(n, acc=1):
    if n <= 1:
        return acc
    return fact_tail(n - 1, acc * n)   # 调用是最后一步：后面没账要算

这种形态编译器可以【复用当前栈帧】（叠一层变原地循环）——Kotlin 有 tailrec、Scala 编译器自动优化。但 CPython 明确不做尾递归优化（Guido 2026 年前的多次表态：保留栈 traceback 的可读性）——在 Python 里尾递归只是理论形态，深度照爆；真要循环就老实写循环。

四、动手 Demo：递归与循环对跑

def fact(n):
    return 1 if n <= 1 else n * fact(n - 1)

print(fact(10))        # 3628800

def fib(n):            # 斐波那契：递归的代价展示
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print([fib(i) for i in range(10)])   # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

def fib_loop(n):       # 同一件事循环写：不叠栈、不重复算
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_loop(30))    # 832040（fib(30) 递归版要算一百多万次调用）

看到什么算成功：3628800、十个斐波那契数、832040。

读结果：fib 递归版每层分两叉、大量重复计算（fib(30) 递归调用上百万次，循环版 30 步）——递归优雅但有账：栈深度×重复计算；能轻松改循环的改循环，改不动的（树、分治）才用递归。

五、30 秒实验

跑 def boom(): return boom()\nboom()——一秒内 RecursionError。没有基线条件的递归就是这个下场；C 语言里同样代码是无声崩溃（栈溢出），连报错都没有。

六、常见误区

  1. 【递归比循环高级，能用递归就用】——错。递归是【问题形状吻合】时的自然表达（树、分治）；线性求和硬用递归是叠栈表演——选结构看问题形状，不看玄学。
  2. 【尾递归在任何语言都优化】——错。Kotlin／Scala／函数系语言优化；CPython 明确不优化——Python 里深度超过约 1000 层照样 RecursionError。
  3. 【RecursionError 是玄学上限】——不是玄学。它就是调用栈叠到 1000 层的物理限制；基线条件写对、深度可控，就永远不会遇到。
自测三问（点开对答案） 1. **递归函数必须具备哪两个部分？** 答：基线条件（停的时候）与递归条件（怎么把参数改小交给自己）——缺基线就是无限递归。 2. **为什么递归太深会栈溢出？** 答：每次调用压一层栈帧，递归 N 层叠 N 层，栈空间有限——CPython 约 1000 层上限，超了 RecursionError。 3. **尾递归是什么、Python 里管用吗？** 答：递归调用是函数最后一步、后面没有计算，编译器可复用栈帧；但 CPython 不做优化——Python 里深度照爆，改循环才实在。

相关笔记