1 · 递归与迭代

S - 什么场景：编写算法时需要处理重复的计算逻辑（如树遍历、动态规划、回溯搜索）

C - 什么冲突：

• 递归代码简洁、直观，易于理解问题结构，但消耗栈空间、可能栈溢出
• 迭代代码显式管理状态、空间效率高、不会栈溢出，但需要手工维护复杂的状态机制

Q - 什么问题：如何在这两者之间做出正确选择？什么时候该用递归，什么时候该用迭代？

A - 回答问题：

• 优先递归：问题具有自然的树形/分治结构（如二叉树遍历、分治算法、回溯搜索）且递归深度可控
• 必须迭代：递归深度过大（深层树、大规模搜索空间）或语言/环境限制（Python无TCO）
• 两者可转换：理解递归与迭代的本质关联，需要时可手工转换

---

递归：自相似结构，将问题拆解为子问题 迭代：状态推进，维护若干状态，不断更新直到结束

递归和迭代通常可以相互转换；递归借助隐式栈，迭代借助显式状态。

递归 -> 迭代：显示使用栈/队列/状态变量保存数据； 迭代 -> 递归：基线条件=循环结束，递归调用=下一轮循环；

本质都是：状态 + 终止条件 + 状态转移规则 + 结果处理； 在某个状态空间里，按照某种转移规则不断演化，直到满足终止条件，并在过程中维护或构造结果。

1.1 · 尾递归优化

尾递归：递归调用是函数做的最后一件事

因为调用自身后，函数没有别的事情做了，所以可以复用这一栈帧（编译期优化）：

return f(next(x))
# 优化成goto语句 ---->
x = next(x)
goto function_start

尾递归优化利用了”尾调用等价于状态跳转”这一性质。

1.2 · DP 动态规划#

DP 是一种基于状态定义和状态转移的优化方法，既可以写成递归，也可以写成迭代。

递归 + 缓存 = 记忆化搜索 = 自顶向下 DP 迭代 + 状态表 = 自底向上 DP