递归、回溯与动态规划入门

递归是函数调用自身的编程技巧，回溯是「递归 + 撤销选择」的穷举思想，动态规划（DP）则是在有重叠子问题的问题上用「记忆化 / 递推」避免重复计算。三者层层递进，是算法面试从「数据结构题」走向「思维题」的分水岭。

递归：先想终止条件

写递归只要两步：找终止条件（base case），找递推关系（子问题如何拼成原问题）。以阶乘为例，f(n) = n × f(n-1)：

def fact(n):
    if n <= 1:
        return 1            # 终止条件
    return n * fact(n - 1)  # 递推：把 n 的问题交给 n-1
print(fact(5))              # 输出：120

递归天然有「递 + 归」两个阶段：先一路向下分解，再一路向上返回结果。注意递归深度过大会栈溢出，且朴素递归常伴有大量重复计算。

回溯：做选择与撤销选择

回溯用于穷举所有可能（全排列、组合、子集、八皇后）：每层递归尝试一个选择，继续深入，返回后撤销刚才的选择（backtrack），让下一分支从头开始：

def permute(nums):
    res, path, used = [], [], [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])      # 收集一个完整排列
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True           # 做选择
            path.append(x)
            backtrack()              # 深入下一层
            path.pop()               # 撤销选择
            used[i] = False
    backtrack()
    return res
print(permute([1, 2, 3]))            # 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

「撤销」是回溯的灵魂：不撤销会导致不同分支互相污染。

动态规划：重叠子问题 + 最优子结构

如果一个问题可以拆成子问题，且子问题会重复出现（重叠子问题）、原问题的最优解由子问题最优解组成（最优子结构），就适合用 DP。典型如爬楼梯：到第 n 阶 = 到 n-1 阶再走 1 步 + 到 n-2 阶再走 2 步，即 dp[n] = dp[n-1] + dp[n-2]。

从朴素递归到 DP 的三级跳

以斐波那契为例展示三种写法，感受复杂度差异：

def fib_rec(n):              # ① 朴素递归：大量重复计算
    return n if n < 2 else fib_rec(n - 1) + fib_rec(n - 2)
# 时间复杂度 O(2^n)，fib_rec(40) 已明显变慢

memo = {}
def fib_memo(n):             # ② 记忆化递归（自顶向下 + 缓存）
    if n in memo:
        return memo[n]
    memo[n] = n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]
print(fib_memo(50))          # 输出：12586269025，瞬间完成

def fib_dp(n):               # ③ 动态规划（自底向上填表）
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
print(fib_dp(50))            # 输出：12586269025

记忆化递归与 DP 本质相同：都把每个子问题只算一次，时间从 O(2^n) 降到 O(n)。

复杂度与面试要点

• 递归时间由递归树节点数决定；回溯是穷举，复杂度通常为指数级（如全排列 O(n!)）。
• DP 时间 = 状态数 × 每个状态的转移代价：爬楼梯是 O(n)×O(1)=O(n)，可滚动数组把空间压到 O(1)。
• 高频题：爬楼梯、打家劫舍、最长递增子序列、背包问题、编辑距离。
• 判断口诀：求「个数 / 最值」且子问题重叠 → DP；求「所有方案 / 具体路径」→ 回溯；能画递归树、能写状态转移方程，就抓住了核心。

小结：递归提供思考框架，回溯用撤销实现穷举，DP 用缓存消除重复计算；把斐波那契的递归、记忆化、DP 三种写法吃透，就迈进了算法思维的大门。