-递归 Lecture 5 - Recursion
-递归 Lecture 5 - Recurs
搞懂递归调用、终止条件、复杂度与常见边界
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
-递归 Lecture 5 - Recurs
搞懂递归调用、终止条件、复杂度与常见边界
Lecture 5 Introduction
你有没有遇到过：打开一个文件夹，里面还有一个，再打开还有一个……这就是「递归」——一个东西里包含着结构相同、规模更小的自己。本讲我们就把这种思维彻底拆开。
最里层无法再拆的 = 基例；每层都套着一个更小的同类 = 递推
Iterative Algorithms
上页我们讲了递归——函数调用自己、把问题拆成更小的同类子问题。但同样的事，用循环也能做，而且往往更省空间。
递归每次产生新实例嵌套（栈帧叠加），迭代在同一容器上反复更新状态（循环变量）
Recursive Algorithms
上一页迭代算法是用同一个动作循环往复地推进；递归走的是另一条路——把问题拆成规模更小的同类子问题，然后让函数在执行中调用自己。
每层套娃内嵌更小的同形套娃，最里层是实心不可拆的——对应递归调用与终止条件
Inductive Reasoning
递归算法会写了，可怎么证明它对所有输入都对？这时要回到它背后的数学逻辑：归纳推理。
第 1 级站稳 + 任意级都能迈上下一级 → 任意高度都能走到
Factorial
上一节归纳法告诉我们：验证 base case + 证明归纳步 = 全命题成立。阶乘的递归定义正是这个证明结构的『计算版』——把『推出 n+1』换成『调用 n 自己』。
打开大娃，里面是个更小的自己；最里层那只空心小娃就是 0! = 1
Towers of Hanoi
阶乘递归只调用自身一次。汉诺塔每次「自己调两次自己」——递归的真正威力，要靠这座塔才完整展露。
得先腾空它上面所有的箱子——中转柱就是临时仓库
Fibonacci
阶乘只回头看一步：F(n)=n·F(n-1)。但 Fibonacci 要回头看两步：F(n)=F(n-1)+F(n-2)——一次调用分成两个子调用，节点数随之呈指数膨胀。
到第 n 阶可从前一阶跨 1 步，或从再前一阶跨 2 步
Demo: Fibonacci
上一页我们见识了 Fibonacci 数列——定义优雅，三行就能写成函数。但真正运行起来，朴素递归慢得不优雅。今天拆开调用树，看看代价藏在哪里。
算过的 F(k) 写进小本子，下次直接抄——memo 本意就是「记住」
Recursion on Strings
Fibonacci 用「两个更小的自己」算出答案。字符串更直接：每次削掉一个字符，剩下的还是字符串——天然就是递归的形状。
每层处理最外圈，剩余仍是同类结构，直到最里面的物品（base case）
Demo: Palindromes
前页我们把递归用在字符串上，现在看一个最经典的递归字符串问题——回文判断。它的递归结构简直是为这个问题量身定做的。
每步各看一字符，外层匹配才能进入内层；走到中间相遇即完成
Global Variables
Global Variables：定义、要点与典型应用
本节要点
- ✓递归三件套：base case、缩小规模、信任子问题的解
- ✓递归 = 数学归纳法的程序化对应
- ✓代价不只在调用栈：朴素斐波那契是O(2ⁿ)
- ✓递归中改全局变量=跨层共享状态，要管好出口
- ✓递归能想到，迭代就能做到；选哪种看问题结构
课后思考
先独立思考，再对照参考答案。三问分别覆盖核心回顾、应用与边界迁移。
参考答案base case 对应归纳基础，递归步骤对应归纳假设——先验证最小情形成立，再假设更小一层成立推出当前成立。
参考答案reverse(s) = reverse(s[1:]) + s[0]。先递归到最深层（空串或单字符为 base case），逐层回溯时把首字符拼到尾部。
参考答案fib(n−1) 与 fib(n−2) 会各自重复计算 fib(n−3)，子问题指数级重叠 → 时间复杂度 O(2ⁿ)。需记忆化或改迭代。