递归与动态规划的对比：从自顶向下递归到自底向上动态规划的转化

一、先用大白话搞懂递归和动态规划

1.1 用生活场景理解递归

想象你在一个大型商场里找一家特定的店铺。你站在当前楼层，先看这层的店铺，如果没找到，就走到上一层楼，重复同样的动作。这就是一种"自己调用自己"的逻辑——你不需要知道一共有多少层，你只需要一个规则：如果当前层找不到，就去上一层继续找。这就是递归。递归的本质就是把一个大问题拆成跟它一样的小问题，然后让小问题自己去解决。

但递归有个明显的毛病：如果你在三层找过了，后来又从一层开始，走到三层时不会记得你已经找过了，又重复找一遍。这就造成了大量重复计算，效率极低。

1.2 用生活场景理解动态规划

现在换一个思路。你不再从一层一层往上找，而是把每一层都提前找一遍，把结果记在一个本子上。当你真正需要某一层的结果时，直接翻本子就行。这就是动态规划的核心思想——把已经算过的结果存起来，下次直接拿来用，不再重复劳动。

动态规划（Dynamic Programming，简称DP）并不是什么高深的概念，它就是"用空间换时间"的一种策略。我们用一个表格或者数组，把每一小步的结果都记录下来，最后通过组合这些小结果，得到最终答案。

二、递归的核心原理与实现

2.1 递归的本质

递归之所以能让很多复杂问题变得简单，是因为它提供了一种"分而治之"的思路。你不需要一次性想清楚所有步骤，只需要想清楚"当前这一步怎么做"，然后信任"剩下的步骤会按照同样的逻辑去做"。

这种思路在很多场景中非常自然，比如计算阶乘、遍历目录结构、处理树形数据等。

2.2 递归的两个基本条件

写递归代码时，必须保证两件事：一是必须有一个"基准情况"（也叫终止条件），否则递归会无限下去；二是每次递归调用时，问题的规模必须变小，朝着终止条件靠近。

下面用一个最简单的例子来看。我们以Python为技术栈，计算阶乘：

# 技术栈：Python 3

def factorial(n):
    """
    计算 n 的阶乘（n!）
    递归思路：n! = n * (n-1)!
    基准情况：0! = 1
    """
    if n == 0:
        # 基准情况：递归的出口，防止无限递归
        return 1
    # 递归步骤：把大问题变成小问题
    return n * factorial(n - 1)

# 调用示例
result = factorial(5)
print(f"5! = {result}")  # 输出：120

这段代码非常简洁，但问题也很明显：当 n 很大时，Python 默认有递归深度限制（通常是 1000），会抛出 RecursionError。而且每次递归调用都会创建新的栈帧，占用内存。

2.3 递归中的重复计算问题

接下来看一个经典问题——斐波那契数列。斐波那契数列的规则是：前两项是 1 和 1，从第三项开始，每一项都是前两项之和。

# 技术栈：Python 3

def fib_recursive(n):
    """
    递归计算斐波那契数列的第 n 项
    注意：这个写法存在大量重复计算！
    """
    if n <= 1:
        # 基准情况
        return n
    # 递归计算
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# 调用示例
print(f"第10项斐波那契数：{fib_recursive(10)}")  # 输出：55

看起来没问题，但实际运行时你会发现，当 n 稍大一些（比如 n=40），程序会变得非常慢。为什么？因为 fib_recursive(3) 被计算了多次，fib_recursive(2) 也被计算了多次，越往底层重复越多，时间复杂度呈指数级增长。

我们可以画一下 fib_recursive(5) 的调用树来直观理解：

                         fib(5)
                    /              \
               fib(4)              fib(3)
              /     \              /     \
          fib(3)   fib(2)      fib(2)   fib(1)
         /    \    /   \       /   \
     fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
     /  \
  fib(1) fib(0)

可以看到，fib(3) 被计算了 2 次，fib(2) 被计算了 3 次。随着 n 增大，这种重复计算呈指数级膨胀。

三、自顶向下递归（带记忆化缓存）

3.1 什么是自顶向下

自顶向下递归就是保留递归的写法，但在每次计算后把结果存起来，下次遇到同样的问题直接返回缓存的结果。这种方式既保留了递归代码的简洁性，又避免了重复计算。

核心工具是"记忆化"（Memoization）——你算过的结果，下次直接用。

3.2 手动实现记忆化

我们不用装饰器，手动实现记忆化，这样能更清晰地看到原理：

# 技术栈：Python 3

def fib_memo(n, memo={}):
    """
    带记忆化缓存的斐波那契计算
    memo 字典用于存储已计算过的结果
    """
    # 基准情况
    if n <= 1:
        return n
    
    # 如果已经计算过，直接返回缓存结果
    if n in memo:
        return memo[n]
    
    # 计算并存入缓存
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# 调用示例
print(f"第50项斐波那契数：{fib_memo(50)}")
# 注意：手动传 memo 字典可以避免默认参数的陷阱

3.3 使用装饰器实现记忆化（更优雅）

Python 标准库提供了一个装饰器 functools.lru_cache，可以非常方便地实现记忆化：

# 技术栈：Python 3

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_lru(n):
    """
    使用 lru_cache 装饰器实现记忆化
    maxsize=None 表示缓存不限制大小
    本质上是把函数当作一个"带缓存的函数"来调用
    """
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)

# 调用示例
print(f"第50项斐波那契数：{fib_lru(50)}")
print(f"缓存信息：{fib_lru.cache_info()}")

lru_cache 的工作方式是：函数第一次被调用时正常计算，结果存入缓存；下次传入相同的参数时，直接从缓存中取结果，不再重新计算。这本质上还是"自顶向下"——我们从一个大的 n 出发，一步步递归到小的 n。

四、自底向上动态规划

4.1 什么是自底向上

自底向上动态规划的做法完全不同：我们不再从大问题出发递归，而是从最小的问题开始，一步步往上构建答案。就像盖房子，先打地基，再一层一层往上砌。

核心工具是"DP 表"——一个数组或表格，用来存储每一步的结果。

4.2 DP表的使用方式

我们仍然以斐波那契数列为例，用自底向上的方式实现：

# 技术栈：Python 3

def fib_dp(n):
    """
    自底向上动态规划计算斐波那契数列的第 n 项
    思路：从第0项开始，逐项计算，存入dp数组
    """
    # 基准情况处理
    if n <= 1:
        return n
    
    # 创建 dp 表，dp[i] 表示第 i 项斐波那契数
    dp = [0] * (n + 1)
    dp[0] = 0  # 第0项
    dp[1] = 1  # 第1项
    
    # 自底向上填充 dp 表
    for i in range(2, n + 1):
        # 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# 调用示例
print(f"第50项斐波那契数：{fib_dp(50)}")
print(f"dp表前10项：{[fib_dp(i) for i in range(10)]}")

4.3 空间优化：滚动数组

注意到 dp 表中第 i 项只依赖前两项，所以我们不需要保存所有历史结果，只保留前两项就够了。这叫做"滚动数组优化"：

# 技术栈：Python 3

def fib_dp_optimized(n):
    """
    空间优化版本：只保留前两项
    时间复杂度 O(n)，空间复杂度 O(1)
    """
    if n <= 1:
        return n
    
    # 只保留前两项的值
    prev2 = 0  # dp[i-2]
    prev1 = 1  # dp[i-1]
    
    for i in range(2, n + 1):
        # 当前项 = 前两项之和
        current = prev1 + prev2
        # 滚动：把后一项推到前面
        prev2 = prev1
        prev1 = current
    
    return prev1

# 调用示例
print(f"第50项斐波那契数：{fib_dp_optimized(50)}")

这个版本只用两个变量来存储状态，空间效率极高。

五、从递归到动态规划的转化过程

5.1 三步转化法

从自顶向下递归转化为自底向上动态规划，通常遵循三个步骤：

第一步：定义状态。 想清楚 dp 数组的每个位置代表什么含义。比如 dp[i] 表示"解决到第 i 步时的最优结果"。

第二步：写出状态转移方程。 也就是想清楚"当前状态是怎么从之前的状态推导出来的"。这通常就是从递归公式中提取出来的。

第三步：确定初始状态和填充顺序。 初始状态就是基准情况（递归的终止条件），填充顺序则是从小到大遍历，保证计算当前值时，所依赖的所有前置值都已经算好了。

5.2 完整示例：爬楼梯问题

爬楼梯问题的描述是：你站在楼梯底部，每次可以爬 1 阶或者 2 阶，请问爬到第 n 阶一共有多少种不同的爬法？

先看递归写法：

# 技术栈：Python 3

def climb_stairs_recursive(n):
    """
    递归方式解决爬楼梯问题
    状态转移：第n阶的走法 = 第(n-1)阶的走法 + 第(n-2)阶的走法
    因为最后一步要么是爬1阶（从n-1阶来），要么是爬2阶（从n-2阶来）
    """
    if n == 1:
        return 1  # 只有一种走法：直接爬1阶
    if n == 2:
        return 2  # 有两种走法：1+1 或 2
    
    # 状态转移方程
    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

再看记忆化版本：

# 技术栈：Python 3

def climb_stairs_memo(n, memo={}):
    """
    记忆化缓存版本
    """
    if n in memo:
        return memo[n]
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    memo[n] = climb_stairs_memo(n - 1, memo) + climb_stairs_memo(n - 2, memo)
    return memo[n]

最后转化为自底向上动态规划：

# 技术栈：Python 3

def climb_stairs_dp(n):
    """
    自底向上动态规划版本
    
    步骤1 - 定义状态：dp[i] 表示爬到第i阶的走法总数
    步骤2 - 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
    步骤3 - 初始状态：dp[1]=1, dp[2]=2
              填充顺序：从 i=3 到 n
    """
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    dp = [0] * (n + 1)
    dp[1] = 1  # 第1阶只有1种走法
    dp[2] = 2  # 第2阶有2种走法
    
    for i in range(3, n + 1):
        # 第i阶的走法 = 从第(i-1)阶爬1步过来 + 从第(i-2)阶爬2步过来
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# 调用示例
print(f"爬5阶楼梯的走法数：{climb_stairs_dp(5)}")  # 输出：8
print(f"爬10阶楼梯的走法数：{climb_stairs_dp(10)}")  # 输出：89

5.3 完整示例：最长公共子序列

最长公共子序列（LCS）问题是动态规划的经典应用。给定两个字符串，找出它们的最长公共子序列的长度。

先写递归版本：

# 技术栈：Python 3

def lcs_recursive(s1, s2):
    """
    递归方式求最长公共子序列长度
    
    思路：
    - 如果两个字符串当前字符相同，则长度加1，继续比较剩下的部分
    - 如果不同，则取"去掉s1当前字符"和"去掉s2当前字符"两者的较大值
    """
    # 基准情况：任一个字符串为空，公共子序列长度为0
    if len(s1) == 0 or len(s2) == 0:
        return 0
    
    # 当前字符相同，公共子序列长度+1
    if s1[0] == s2[0]:
        return 1 + lcs_recursive(s1[1:], s2[1:])
    
    # 当前字符不同，取两种情况的最大值
    return max(
        lcs_recursive(s1[1:], s2),   # 跳过s1的第一个字符
        lcs_recursive(s1, s2[1:])    # 跳过s2的第一个字符
    )

再写自底向上动态规划版本：

# 技术栈：Python 3

def lcs_dp(s1, s2):
    """
    自底向上动态规划求最长公共子序列长度
    
    步骤1 - 定义状态：
            dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符的 LCS 长度
    
    步骤2 - 状态转移方程：
            如果 s1[i-1] == s2[j-1]：
                dp[i][j] = dp[i-1][j-1] + 1
            否则：
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    步骤3 - 初始状态：
            dp[0][j] = 0（s1为空字符串）
            dp[i][0] = 0（s2为空字符串）
            填充顺序：i 从 1 到 len(s1)，j 从 1 到 len(s2)
    """
    m, n = len(s1), len(s2)
    
    # 创建 dp 表，大小为 (m+1) x (n+1)
    # dp[i][j] 表示 s1[:i] 和 s2[:j] 的LCS长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 填充 dp 表（自底向上）
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                # 当前字符匹配，LCS长度+1
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # 当前字符不匹配，取较大的那个
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # dp[m][n] 就是最终的LCS长度
    return dp[m][n]

# 调用示例
s1 = "ABCBDAB"
s2 = "BDCAB"
lcs_length = lcs_dp(s1, s2)
print(f"字符串1: {s1}")
print(f"字符串2: {s2}")
print(f"最长公共子序列长度: {lcs_length}")  # 输出：4

# 额外功能：回溯找出LCS本身
def lcs_dp_with_path(s1, s2):
    """
    不仅返回LCS长度，还回溯找出LCS本身
    通过 dp 表逆向追踪找到公共子序列的字符
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i - 1][j] > dp[i][j - 1]
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # 回溯找出LCS
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs.append(s1[i - 1])  # 当前字符属于LCS
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1  # 往上走
        else:
            j -= 1  # 往左走
    
    lcs.reverse()  # 反转得到正确的顺序
    return dp[m][n], ''.join(lcs)

length, lcs_string = lcs_dp_with_path("ABCBDAB", "BDCAB")
print(f"LCS长度: {length}, LCS字符串: {lcs_string}")  # 输出：4, BCAB

六、应用场景分析

6.1 适合递归的场景

递归非常适合处理那些天然具有递归结构的问题。比如文件系统目录的遍历——每个目录里可能有文件，也可能有子目录，子目录里又可能有子子目录，这种层层嵌套的结构用递归来写非常直观。再比如二叉树的遍历（前序、中序、后序），以及分治算法（快速排序、归并排序）等。

另外，当问题规模较小、对性能要求不高时，递归写法的可读性往往更好。比如处理一棵只有几百个节点的树，用递归遍历比用迭代写要清晰得多。

6.2 适合动态规划的场景

动态规划适合那些具有"最优子结构"和"重叠子问题"特征的优化类问题。

"最优子结构"是指大问题的最优解可以由小问题的最优解组合而成。比如最短路径问题，从起点到终点的最短路径，一定包含从起点到中间某个点的最短路径。

"重叠子问题"是指递归过程中会重复解决相同的子问题。比如斐波那契数列，fib(5) 需要计算 fib(4) 和 fib(3)，而 fib(4) 也需要计算 fib(3)，fib(3) 就被重复计算了。

典型的动态规划应用场景包括：背包问题（0-1背包、完全背包）、最长公共子序列、最长递增子序列、编辑距离、矩阵链乘法、区间DP、树形DP等。

七、技术优缺点对比

7.1 递归的优缺点

优点方面： 代码简洁，逻辑清晰，尤其适合处理树形结构、分治问题。递归写法的思维模式与数学归纳法一致，容易验证正确性。Python 中的 lru_cache 装饰器让记忆化变得非常简单。

缺点方面： 递归调用开销大，每次调用都要在栈上创建新的帧，保存局部变量和返回地址。递归深度受限于系统栈大小，Python 默认是 1000 层。没有记忆化时，时间复杂度往往呈指数级，性能极差。调试困难，多层嵌套的递归调用栈不容易跟踪。

7.2 动态规划的优缺点

优点方面： 避免重复计算，时间复杂度通常是多项式级别，性能优秀。通过迭代实现，没有栈溢出的风险。空间可以通过滚动数组等技术进一步优化。

缺点方面： 状态的定义和转移方程的设计需要一定的思维训练，不像递归那样直观。代码相对冗长，尤其是多维 DP 表的情况。边界条件的处理容易出错，需要仔细检查。

八、注意事项

8.1 栈溢出风险与递归深度限制

Python 默认递归深度限制是 1000，你可以通过 sys.setrecursionlimit() 来调整，但不建议设得太大，否则可能导致段错误（程序崩溃）。

# 技术栈：Python 3

import sys

# 查看当前递归深度限制
print(f"当前递归深度限制：{sys.getrecursionlimit()}")

# 适当调整（谨慎使用，过大会导致段错误）
sys.setrecursionlimit(5000)

# 测试深递归
def deep_recursion(n):
    if n == 0:
        return 0
    return deep_recursion(n - 1)

print(f"深递归测试结果：{deep_recursion(4999)}")

8.2 空间优化技巧

动态规划的空间优化是一个重要技巧。如果 dp 表中第 i 行只依赖第 i-1 行，那么就不需要保存所有行，只需要用两个一维数组交替使用即可。如果进一步，如果 dp[i][j] 只依赖 dp[i-1][j] 和 dp[i][j-1]，那甚至可以用一维数组原地更新。

# 技术栈：Python 3

def knapsack_2d(weights, values, capacity):
    """
    0-1背包问题：二维dp表版本
    
    weights: 物品重量列表
    values:  物品价值列表  
    capacity: 背包容量
    
    返回值：能装下的最大总价值
    """
    n = len(weights)
    # dp[i][w] 表示前i个物品、容量为w时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 不选第i个物品
            dp[i][w] = dp[i - 1][w]
            # 选第i个物品（前提是容量够）
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                )
    
    return dp[n][capacity]


def knapsack_1d(weights, values, capacity):
    """
    0-1背包问题：一维dp表空间优化版本
    
    注意：一维数组必须从右往左遍历，否则会重复使用同一个物品
    """
    n = len(weights)
    # 一维 dp 数组：dp[w] 表示容量为 w 时的最大价值
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 关键：从右往左遍历，保证每个物品只被选一次
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(
                dp[w],
                dp[w - weights[i]] + values[i]
            )
    
    return dp[capacity]


# 调用示例
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

result_2d = knapsack_2d(weights, values, capacity)
result_1d = knapsack_1d(weights, values, capacity)

print(f"二维dp结果：{result_2d}")
print(f"一维dp结果：{result_1d}")
print(f"两种结果一致：{result_2d == result_1d}")  # 输出：True

8.3 状态压缩的适用条件

空间优化（状态压缩）是有条件的。不是所有的 DP 问题都能压缩空间。一般来说，如果状态转移只依赖于相邻的几个状态，就可以压缩；如果依赖于前面任意位置的状态，压缩会比较困难。判断的时候画一下 dp 表，看看转移方程里引用的位置关系就清楚了。

8.4 时间复杂度的估算

递归如果没有记忆化，时间复杂度往往是指数级的 O(2^n)。加上记忆化后，时间复杂度降低到 O(n)（因为每个状态只计算一次）。自底向上 DP 的时间复杂度通常就是状态转移的次数，等于 dp 表中所有格子数乘以每个格子的计算代价。比如斐波那契的 O(n)，二维 LCS 的 O(mn)，背包问题的 O(ncapacity) 等。

九、文章总结

递归和动态规划本质上是同一枚硬币的两面。递归是自顶向下，从一个大的问题出发，层层分解，直到触及基准情况再层层返回。动态规划是自底向上，从最小的问题开始，一步步构建答案。

从实际开发的角度来看，选择哪种方式取决于几个因素：问题规模大的时候，动态规划的迭代方式更安全，不会栈溢出；问题结构天然递归（如树遍历）的时候，递归写法更自然、代码更简洁；需要频繁调试和修改的时候，迭代方式的动态规划更容易在任意位置插入调试信息。

转化练习是非常有效的学习方式。你可以先从递归写法开始，因为递归更接近问题的自然描述；然后加上记忆化，理解缓存的工作原理；最后再转化为自底向上的 DP，体会从"拆解问题"到"构建答案"的思维转变。

记住三个核心步骤：定义状态、写出转移方程、确定初始条件和填充顺序。掌握了这套方法论，你就能应对绝大多数动态规划问题了。