3.3.3 递归：调用栈保存尚未完成的现场

递归函数必须有终止条件，并让每次调用向它靠近。调用时系统栈保存返回地址、参数、局部变量等栈帧；子调用结束后，最近挂起的调用最先恢复，天然符合 LIFO。

long long fact(int n){ if(n<0) throw invalid_argument("n");
 return n<=1 ? 1 : n*fact(n-1); }

推演 fact(4)：依次压入参数 4、3、2、1；到基础情况返回 1，随后逆序计算 2*1、3*2、4*6 得 24。时间 $O(n)$，递归栈空间 $O(n)$，不能因为代码只有一行递归就写 $O(1)$ 空间。

递归树有多分支时，调用次数可能急剧增长。朴素 Fibonacci 满足 $T(n)=T(n-1)+T(n-2)+O(1)$，存在大量重复子问题，时间为指数级；记忆化把每个状态只算一次，降为 $O(n)$。

将尾递归或简单线性递归改为显式循环，可减少栈深风险；树遍历等需要记住多个待处理分支时，可用显式栈模拟。是否优化取决于语言是否保证尾调用优化，不能想当然。

错解反馈：只有递归式没有基础情况会无限调用；参数不缩小会永远到不了基础情况；只分析单层工作忽略调用次数；把“系统自动管理栈”误认为无需计入空间。

迁移题：递归求数组前 $n$ 项和，写出基础情况与规模变化。答案可设 sum(a,0)=0，sum(a,n)=sum(a,n-1)+a[n-1]。独立验收：能画出调用与返回两阶段，并分别写时间和最大栈深。