登录
递归 VS 动态规划：从 “无限套娃计算器” 到 “积木式解题神器”
就占用你
5分钟，让你搞懂递归和DP算法！
前言
你有没有试过：对着计算器按 “× 上一个数”，按到手指酸？或者自己照镜子，镜子里面有个自己，镜子的镜子里面还有个自己？这就是递归 —— 像台 “无限套娃计算器”，算大数能把自己 “算死机”；而动态规划是 “积木式解题神器”，从最小块开始拼，再复杂的题都能稳准狠搞定。
一、递归：“套娃计算器” 的用法
递归就俩关键：找 “套娃公式”（规律）+ 找 “最小娃”（出口）
例 1：算阶乘 —— 套娃停不下来？
如果要你计算5的阶乘，你会怎么做？大部分人第一想法应该都是：直接一个for循环不就完事了吗？没错：
function mul(n) {
let num = 1;
for(let i = n; i >= 1; i--){
num *= i;
}
return num;
}
console.log(mul(5));
但是你用你聪明的脑袋想了又想，阶乘是 “5! = 5×4×3×2×1”，套娃公式是 “n! = n × (n-1)!”（大娃里塞小娃）；最小娃是 “1! = 1”（塞到最小的娃就停）。好像这样也能写出来！
看代码（递归版阶乘）：
function mul(n) {
// 最小娃：1!直接返回 1
if(n == 1){
return 1;
}
// 套娃公式：大娃=自己×小娃
return n * mul(n - 1);
}
console.log(mul(5));
我嘞个豆，答案✅️了，这就是我们今天的主角--大名鼎鼎的递归。但这计算器有 bug：例如算mul(50000)会 “套娃太多死机”（栈溢出）。在我写的浅拷贝 VS 深拷贝这篇文章中有掘u问到了这个问题。所以递归一般在非必要情况下使用，因为数据一大就会爆栈。
例 2：斐波那契数列 —— 套两层娃？
斐波那契是 “1,1,2,3,5……”，套娃公式是 “第 n 项 = 第 n-1 项 + 第 n-2 项”（一个娃里塞俩小娃）；最小娃是 “第 1、2 项 = 1”。
function fb(n) {
// 最小娃：前两个直接返回 1
if(n == 1 || n == 2){
return 1;
}
// 套娃公式：自己=左边娃+右边娃
return fb(n - 1) + fb(n - 2);
}
console.log(fb(5));
这计算器更费电：算fb(100)要重复掏同一批娃，卡到你怀疑人生～，这就是递归，好理解但难用，接下来我们开始经典算法--动态规划！
二、动态规划：“积木神器” 怎么拼？
动态规划是 “反着来”—— 不用拆娃，直接从 最小积木块（已知结果） 开始，一块一块拼出最终答案，像搭乐高一样稳。
例：爬楼梯 - 力扣（LeetCode）
有一个思路，那就是直接暴力通项公式，看看官方题解：
var climbStairs = function(n) {
const sqrt5 = Math.sqrt(5);
const fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
return Math.round(fibn / sqrt5);
};
但是这里我们用算法思想，也就是动态规划。积木公式：第 n 级的拼法 = 第 n-1 级拼法（最后加 1 块）+ 第 n-2 级拼法（最后加 2 块）。
看代码（动态规划版爬楼梯）：
var climbStairs = function (n) {
// 积木盒dp：存每级台阶的拼法数
let dp = [];
// 基础积木：0级（起点）和1级各1种拼法
dp[0] = 1;
dp[1] = 1;
// 从2级开始，用现有积木拼新台阶
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
// 第n级的拼法就是dp[n]
return dp[n];
};
console.log(climbStairs(5));
这神器不卡不崩，再大的 n 都能轻松搞定～
总结：套娃计算器 vs 积木神器
- 递归（套娃计算器）：上手快，但算大数容易 “死机”；
- 动态规划（积木神器）：从基础块开拼，稳、准、快，复杂题克星。
我最后总结这样一份表格，希望能够帮到各位：
| 维度 | 递归（Recursion） | 动态规划（Dynamic Programming, DP） |
|---|---|---|
| 核心思想 | 把大问题拆解为规模更小的子问题，通过调用自身解决子问题，最终合并子问题结果得到原问题解 | 将大问题拆解为重叠子问题，通过存储子问题的解（记忆化 / 表格）避免重复计算，自底向上或自顶向下求解 |
| 问题特征 | 1. 问题可自然拆解为独立子问题（无大量重复计算）2. 问题具有递归结构（如树形结构、分治场景）3. 子问题规模递减且无重叠 | 1. 问题具有重叠子问题（子问题被重复求解）2. 问题具有最优子结构（原问题最优解由子问题最优解组成）3. 存在状态转移关系 |
| 适用场景 | 1. 分治算法（如归并排序、快速排序）2. 树形结构遍历 / 操作（如二叉树的遍历、求深度、路径和）3. 排列组合枚举（如全排列、子集生成）4. 回溯算法（如 N 皇后、迷宫问题）5. 问题子问题无重叠，递归深度可控 | 1. 优化类问题（如最短路径、最大收益、最小代价）2. 计数类问题（如不同路径数、解码方式数）3. 子问题大量重复的场景（如斐波那契数列、背包问题）4. 状态可清晰定义且存在转移关系的问题 |
| 实现方式 | 1. 纯递归（无记忆化，直接调用自身）2. 递归 + 记忆化（Top-Down DP，属于 DP 的一种） | 1. 自顶向下（记忆化递归）2. 自底向上（迭代 + 表格，如二维 / 一维 DP 数组） |
| 时间复杂度 | 纯递归：若存在重叠子问题，时间复杂度指数级（如斐波那契纯递归为 O (2ⁿ)）；无重叠子问题时为 O (n) 或 O (nlogn)（如归并排序） | 消除重复计算，时间复杂度通常为 O (n)、O (nm) 等多项式级别（如斐波那契 DP 为 O (n)，01 背包为 O (nm)） |
| 空间复杂度 | 纯递归：递归调用栈深度（如二叉树递归遍历为 O (h)，h 为树高）；若递归深度过大可能栈溢出 | 自底向上 DP：存储状态的数组 / 表格空间（如 O (n) 或 O (nm)）；可优化空间（如滚动数组），无栈溢出风险 |
| 代码风格 | 代码简洁、直观，符合问题的自然拆解逻辑，易编写和理解 | 需手动定义状态和转移方程，代码相对复杂，但效率更高 |
| 典型例子 | 1. 二叉树的前 / 中 / 后序遍历2. 归并排序 / 快速排序3. 全排列 / 组合总和4. 汉诺塔问题5. 回溯法解 N 皇后 | 1. 斐波那契数列（优化版）2. 01 背包 / 完全背包问题3. 最长公共子序列（LCS）4. 最短路径（Floyd-Warshall/Dijkstra 的 DP 思想）5. 最大子数组和（Kadane 算法） |
| 局限性 | 1. 重叠子问题导致重复计算，效率低2. 递归深度过大易引发栈溢出（如 n=10000 的斐波那契递归）3. 函数调用开销 | 1. 需明确状态定义和转移方程，对问题建模要求高2. 不适用于子问题无重叠的场景（反而增加空间开销） |
