composing-programs-zh 递归函数完全指南：树形递归 vs 线性递归，斐波那契深度对比

composing-programs-zh 递归函数完全指南：树形递归 vs 线性递归，斐波那契深度对比

【免费下载链接】composing-programs-zh🦊 CS61A 教材 Composing Programs 的中文翻译项目地址: https://gitcode.com/gh_mirrors/co/composing-programs-zh

递归函数是计算机科学中最经典、也是新手最容易卡壳的概念。本文基于伯克利 CS61A 教材《Composing Programs》的中文翻译项目 composing-programs-zh，用最经典的斐波那契数列，带你看懂递归函数的两大流派——线性递归与树形递归，并学会用记忆化一招提升效率。

一、什么是递归函数？两大必备要素

函数体内直接或间接调用自身的函数，就是递归函数。写 Python 递归不需要任何特殊语法，但每个正确的递归函数都离不开两个要素：

💡 核心心法：每次递归调用都必须让问题变简单，这样才能最终落到基准情况，否则就是无限递归 + 栈溢出。

一个最直观的入门例子是"各位数字之和"：18117 的数字和 = 1811 的数字和 + 7，一层层剥到只剩个位数即可。教材在 sicp/1/7.md 中用这个例子完整演示了递归的展开与回收过程。

二、线性递归：像剥洋葱一样层层递进

线性递归指函数体内只有一个递归调用，调用链像一条直线延伸下去。求阶乘就是经典案例：

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

线性递归的特点一目了然：

• ✅ 结构简单：参数每轮缩小，一路直达基准情况
• ✅ 容易理解：像剥洋葱，结果从最深处逐层"展开"回来
• ⚠️ 空间开销：调用链深度为 n，需要保留 n 个中间帧

教材特别强调"递归的信仰之跃"：验证正确性时，只需相信fact(n-1)能算对，再检查n * fact(n-1)即可——这本质上就是一次归纳法证明，能帮你摆脱"逐层跟踪每一步"的焦虑。

三、树形递归：斐波那契为什么会爆炸

树形递归指一个函数直接调用自己多次：每个调用分出多个小调用，小调用再分叉，像树枝越分越细，故而得名。

斐波那契数列的递归定义几乎是数学定义的直接翻译，优雅得让人心动：

def fib(n): if n == 1: return 0 if n == 2: return 1 else: return fib(n - 2) + fib(n - 1)

但优雅 ≠ 高效。下面这张图展示了计算fib(6)时的完整调用树，问题一目了然：

仔细数一数：fib(3)出现了 3 次，fib(2)出现了 5 次——同样的子问题被重复计算！这种冗余计算是树形递归的通病，函数调用次数甚至比斐波那契数列本身增长得还快。教材在 sicp/2/8.md 中实测：仅仅计算fib(19)，就要调用函数10946次。

四、深度对比：树形递归 vs 线性递归

📌选型口诀：问题能"一步步剥"（阶乘、求和）就用线性递归；问题天然要"分头处理"（斐波那契、分割数）就用树形递归——但要做好性能优化的准备。

五、记忆化：树形递归的最快优化方案

"重复计算"有一个经典解法——记忆化（Memoization）：把算过的结果存进缓存，第二次调用fib(25)时直接返回缓存值，不再重新递归。

教材把记忆化实现为一个高阶函数，几行代码就能包装任意函数：

def memo(f): cache = {} def memorized(n): if n not in cache: cache[n] = f(n) return cache[n] return memorized

效果非常直观。同样的fib(6)，加上记忆化后调用树变成这样：

对比上一张图，三种颜色的含义：

• 🔵 蓝色 = 真正执行的函数调用（明显变少）
• 🟤 红色 = 缓存命中，直接复用已有结果
• ⚪ 灰色 = 根本不再执行的子树

凭借记忆化，每个不同输入下fib实际只被调用一次，时间复杂度从指数级直接降到线性级——这就是"把树递归变回线性"的魔法。

六、去哪系统学习？教材对应章节

想系统掌握递归函数，建议按教材章节顺序阅读（均在本仓库中）：

写在最后

一句话总结：线性递归是"剥洋葱"，树形递归是"长树"。斐波那契数列是同时理解这两种模式的最佳老师——先用树形递归写出优雅的直译版，再用记忆化把它优化成线性效率，正是递归函数从"写对"走向"写快"的完整旅程。

【免费下载链接】composing-programs-zh🦊 CS61A 教材 Composing Programs 的中文翻译项目地址: https://gitcode.com/gh_mirrors/co/composing-programs-zh