迭代、递归、回溯和动态规划

通俗解释：

这几个概念都涉及"重复解决问题"，但思维方式和应用场景有本质差异。用日常场景类比：

1. 迭代
   像每天存钱罐存10元，存满为止。每次存钱都是相同操作，用循环实现，依赖前一次结果（当前总额）推动进度。迭代是用已知步骤逐步逼近目标，代码常用for/while循环。

2. 递归
   像俄罗斯套娃，大问题拆成小问题，解法完全相同。比如算5的阶乘，先算4的阶乘，再乘以5。代码特征是函数自己调用自己，直到触发终止条件（如n=1时返回1）。

3. 回溯
   像走迷宫，遇到死路就退回岔路口换方向。通过试错探索所有可能路径，常用于穷举问题（如八皇后）。代码实现通常是递归+撤销操作（比如棋盘上落子后撤回）。

4. 动态规划
   通过将问题分解为子问题并存储子问题的解来优化递归。像背单词时先背简单词再记复杂词。将问题分解为相互关联的子问题，并存储子问题的解避免重复计算。比如斐波那契数列，算f(5)需要f(4)和f(3)，而f(4)又需要f(3)和f(2)，此时存下中间结果能大幅减少计算量。

---

区别与联系：

维度	迭代	递归	回溯	动态规划
核心思想	循环推进，旧值推新值	自我调用，分解问题	试错探索，撤销选择	存储子问题解，避免重复
代码结构	循环语句	函数调用自身	递归+状态回退	递归或循环+记忆化存储
典型场景	数值计算、简单重复任务	树/图结构、分治问题	排列组合、路径搜索	最优化问题（最短路径等）
空间效率	通常较低（无栈开销）	栈空间可能溢出	路径状态占用内存	需要额外存储子问题解
思维方向	自底向上（从小推大）	自顶向下（从大拆小）	路径探索（穷举+剪枝）	子问题递推（最优决策）

---

关键关系：

• 递归和迭代可相互转换（如用栈模拟递归），但递归更直观，迭代更节省内存。
• 回溯本质是递归的应用，通过DFS遍历解空间，适合需要“试错”的场景。
• 动态规划常被看作“递归+记忆化”，但也可用迭代实现。与回溯的区别在于动态规划有重叠子问题和最优子结构，而回溯处理的问题可能无重复子问题（如八皇后）。

一句话总结：
迭代是手动循环，递归是自动分解，回溯是带撤销的递归，动态规划是聪明的递归（存结果防重复）。