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 递归不需要任何特殊语法但每个正确的递归函数都离不开两个要素要素作用斐波那契中的体现基准情况停止条件最简单输入直接返回fib(1)0、fib(2)1递归调用把问题拆成更小的同类子问题fib(n-1) fib(n-2) 核心心法每次递归调用都必须让问题变简单这样才能最终落到基准情况否则就是无限递归 栈溢出。一个最直观的入门例子是各位数字之和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 线性递归对比维度线性递归树形递归每层递归调用数1 次多次斐波那契是 2 次调用结构形状一条直线一棵分叉的树典型例子阶乘、数字之和斐波那契、整数分割数时间代价斐波那契线性 O(n)迭代/线性写法指数级 O(2ⁿ)空间代价与深度 n 成正比与树深 n 成正比反而较小代码表达力简洁几乎是数学定义的直译新手常见坑忘记基准情况冗余计算导致超慢选型口诀问题能一步步剥阶乘、求和就用线性递归问题天然要分头处理斐波那契、分割数就用树形递归——但要做好性能优化的准备。五、记忆化树形递归的最快优化方案重复计算有一个经典解法——记忆化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实际只被调用一次时间复杂度从指数级直接降到线性级——这就是把树递归变回线性的魔法。六、去哪系统学习教材对应章节想系统掌握递归函数建议按教材章节顺序阅读均在本仓库中章节内容文件路径1.7 递归函数基准情况、线性递归、互递归、树形递归sicp/1/7.md1.6 高阶函数高阶函数——实现记忆化的关键工具sicp/1/6.md2.8 效率如何测量递归代价、记忆化优化sicp/2/8.md2.9 树与递归递归的进阶应用树形数据结构sicp/2/9.md写在最后一句话总结线性递归是剥洋葱树形递归是长树。斐波那契数列是同时理解这两种模式的最佳老师——先用树形递归写出优雅的直译版再用记忆化把它优化成线性效率正是递归函数从写对走向写快的完整旅程。【免费下载链接】composing-programs-zh CS61A 教材 Composing Programs 的中文翻译项目地址: https://gitcode.com/gh_mirrors/co/composing-programs-zh创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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 递归不需要任何特殊语法但每个正确的递归函数都离不开两个要素要素作用斐波那契中的体现基准情况停止条件最简单输入直接返回fib(1)0、fib(2)1递归调用把问题拆成更小的同类子问题fib(n-1) fib(n-2) 核心心法每次递归调用都必须让问题变简单这样才能最终落到基准情况否则就是无限递归 栈溢出。一个最直观的入门例子是各位数字之和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 线性递归对比维度线性递归树形递归每层递归调用数1 次多次斐波那契是 2 次调用结构形状一条直线一棵分叉的树典型例子阶乘、数字之和斐波那契、整数分割数时间代价斐波那契线性 O(n)迭代/线性写法指数级 O(2ⁿ)空间代价与深度 n 成正比与树深 n 成正比反而较小代码表达力简洁几乎是数学定义的直译新手常见坑忘记基准情况冗余计算导致超慢选型口诀问题能一步步剥阶乘、求和就用线性递归问题天然要分头处理斐波那契、分割数就用树形递归——但要做好性能优化的准备。五、记忆化树形递归的最快优化方案重复计算有一个经典解法——记忆化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实际只被调用一次时间复杂度从指数级直接降到线性级——这就是把树递归变回线性的魔法。六、去哪系统学习教材对应章节想系统掌握递归函数建议按教材章节顺序阅读均在本仓库中章节内容文件路径1.7 递归函数基准情况、线性递归、互递归、树形递归sicp/1/7.md1.6 高阶函数高阶函数——实现记忆化的关键工具sicp/1/6.md2.8 效率如何测量递归代价、记忆化优化sicp/2/8.md2.9 树与递归递归的进阶应用树形数据结构sicp/2/9.md写在最后一句话总结线性递归是剥洋葱树形递归是长树。斐波那契数列是同时理解这两种模式的最佳老师——先用树形递归写出优雅的直译版再用记忆化把它优化成线性效率正是递归函数从写对走向写快的完整旅程。【免费下载链接】composing-programs-zh CS61A 教材 Composing Programs 的中文翻译项目地址: https://gitcode.com/gh_mirrors/co/composing-programs-zh创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考