调用栈处理递归时，每次调用压入新栈帧，内存线性增长易致栈溢出；尾递归优化可复用栈帧，但python不支持；转为迭代最可靠，空间复杂度降至o(1)；辅以记忆化、深度限制等手段进一步优化。
调用栈处理递归时，每次函数调用都会在栈上压入一个新栈帧，里面存参数、返回地址、局部变量。递归越深，栈帧越多，内存占用线性增长；一旦超出系统栈空间限制，就会触发栈溢出（如 Segmentation fault 或 RecursionError）。
递归调用时栈帧怎么一层层堆起来
函数每调用自己一次，就生成一个独立栈帧。比如 factorial(5) 会依次压入 factorial(5)、factorial(4)、factorial(3)、factorial(2)、factorial(1) 五个帧——哪怕只是算个阶乘，也要占五份内存。这些帧不会提前释放，必须等最深层返回后，才逐层弹出。中间任何一层的局部变量、计算中间值都得一直留着，直到回溯完成。
尾递归优化：复用栈帧，避免堆积
如果递归调用是函数最后执行的操作（即“尾位置”），且返回值不参与后续计算，编译器或运行时就可能把当前栈帧直接覆盖，而不是新建一个。这样无论递归多少层，实际只用一个栈帧的空间。
- 普通递归：
return n * factorial(n-1)——n *还要等子调用返回才能算，不能复用 - 尾递归写法：
return factorial_tail(n-1, acc * n)—— 调用完直接返回，无后续操作 - 注意：Python 不支持自动尾调用优化；JavaScript（严格模式）、Scheme、Scala 等语言支持；C/C++/Rust 编译器在开启优化后可能做类似转换
转成迭代：彻底绕开调用栈
用循环+显式变量替代隐式栈，是最可靠、跨语言通用的优化方式。尤其适合线性递归（如遍历链表、计算累加、二分查找）。
- 把递归参数变成循环变量（如用
while (n > 0)替代if (n == 0) return; else f(n-1)） - 把需回溯的状态（如中间结果、路径记录）存为普通变量或栈/队列结构
- 例如阶乘：用
result = 1; while (n > 1) { result *= n; n--; }替代递归，空间复杂度从 O(n) 降到 O(1)
其他实用优化手段
不是所有递归都能轻松改写为尾递归或迭代，这时可结合问题特性补充优化：
- 记忆化（Memoization）：缓存已算过的子问题结果，避免重复调用（如斐波那契），降低实际递归次数
- 限制最大深度：主动检查递归层数，超限时抛错或降级处理，防失控
- 手动模拟栈：对树/图遍历类递归，用数组或容器模拟调用栈，控制内存分配位置（如堆上分配而非栈）
- 分治剪枝：在归并、快排等场景中，小规模子问题改用迭代或插入排序，减少深层递归
