递推与递归#

0. 引入#

递推：从小到大，自己“走过去”。实现多是循环。
递归：把大问题交给“更小的自己”先做；有**递(下潜)与归(返回)**两阶段。

举两个简单的例子：

1
int sum(int n) {
2
  int res = 0;
3
  for (int i = 1; i <= n; i++) {
4
      res += i;
5
  }
6
  return res;
7
}

1
int sum(int n) {
2
  if (n == 1) return 1;   // 递归出口
3
  return sum(n - 1) + n;  // 先递，再归
4
}

alt text

把 sum(1..n) 写成递：求 sum(1..n-1)；归：再加 n。
一个 5 层小“调用栈”：sum(5) 压栈到 sum(1) 再一层层返回。

例如：

我们熟悉的数学公式：

f(n) = 10 + 2\times(n-1)

递推公式（状态转移方程）：

f(1) = 10

f(n)=f(n-1)+2,(n>1)

1. 方法与模板#

1.1 三步方法#

定义清楚：f[i] 或 solve(x) 表示什么？
边界：最小规模的答案？如 n==0/1、空集、叶子结点。
关系：大的如何由小的组成？（先后/限制/组合）

1.2 三个模板#

(A) 递推（for 循环）

1
// 以 f[i] 为例
2
vector<int> f(n+1);
3
f[0] = 基值0; f[1] = 基值1;
4
for (int i = 2; i <= n; ++i) {
5
    f[i] = 由 f[i-1], f[i-2] ... 推出;
6
}

(B) 递归（带记忆化，可选）

1
unordered_map<int,int> memo;
2
int solve(int x){
3
    if (x <= 边界) return 边界值;
4
    if (auto it = memo.find(x); it != memo.end()) return it->second;
5
    int ans = 通过 solve(更小规模) 得到;
6
    return memo[x] = ans;   // 仅为“去重复”
7
}

(C) 回溯（做选择 → 递归 → 撤销选择）

1
vector<int> path; // 当前选择
2
void dfs(int u /*深度或下标*/){
3
    if (到达目标/长度) { 记录答案; return; }
4
    for (auto choice : 当前可选集){
5
        path.push_back(choice);           // 做选择
6
        dfs(u + 1);                       // 递
7
        path.pop_back();                  // 撤销
8
    }
9
}

一个语法#

lambda表达式

Lambda表达式是一种在被调用的位置或作为参数传递给函数的位置定义匿名函数对象（闭包）的简便方法。Lambda表达式的基本语法如下：

[capture list] (parameter list) -> return type { function body }

下面一个例子就可以很好的理解：

add(a, b)的函数形式

1
int add(int a, int b) {
2
  return a + b;
3
}

add(a, b)的lambda表达式

1
auto add = [&](auto a, auto b) {
2
  return a + b;
3
};

2. 入门例子#

2.1 Fibnacci数列（两种写法）#

Fibnacci数列如下：

\left\{\begin{matrix} f(1)=1 \\ f(2)=1 \\ f(n)=f(n-1)+f(n-2) & n>2 \end{matrix}\right.

递推

1
void solve() {
2
  int n;
3
  cin >> n;
4
  auto fib = [&](auto n) {
5
    if (n < 2) {
6
        return n;
7
    }
8
    int a=0, b=1;
9
    for (int i = 2; i<=n; i++){
10
        auto c = a + b;
11
        a = b;
12
        b = c;
13
    }
14
    return b;
15
  };
16
  cout << fib(n) << endl;
17
}

递归 + 记忆化

Fibnacci数列同样可以由递归来求，我们既然想求 $f(n)$ ，那么我们就需要知道 $f(n-1)$ 和 $f(n-2)$ ，同时递归终点是1和0，于是得到下面代码

1
 int fib(int n) {
2
   if(n == 0 || n == 1) {
3
       return n;
4
   }
5
   return fib(n - 1) + fib(n - 2);
6
 }

递归树#

对于我们递归求Fibnacci数列，我们每⼀次递归产⽣了两个分⽀fib(n - 1)和fib(n - 2)，我们可以画出下⾯的图

alt text

可以看出我们递归树的节点数量是 $2^{n}$ 数量级的，所以这种递归求斐波那契数列时间复杂度为 $O(2^{n})$ ，空间复杂度为 $O(n)$ ，虽然空间复杂度不打，但有一个非常巨大的时间复杂度，而递推就是 $O(n)$ 的时间复杂度，非常优秀。

但是我们可以通过增加记忆化，来优化时间复杂度。

1
unordered_map<int, int> memo;
2

3
void solve() {
4
  int n;
5
  cin >> n;
6
  function<int(int)> fib = [&](int n) {
7
    if (n < 2) {
8
      return n;
9
    }
10
    if (memo.count(n)) {
11
      return memo[n];
12
    }
13
    return memo[n] = fib(n - 1) + fib(n - 2);
14
  };
15
  cout << fib(n) << endl;
16
}

从上述可以看出递推和递归各有优劣，我们需要根据不同的使用场景，合适的选择使用递推还是递归，简单总结优劣势如下：

递归

优势：

时间复杂度低： $O(n)$ ，每个状态只算一次。

空间复杂度低：只需常数空间 $O(1)$ （用两个变量存储即可）。

执行效率高：循环写法比递归少了函数调用开销。

容易避免栈溢出：不依赖系统调用栈。

劣势

可读性稍弱：不像递归那样直观地对应数学公式。

复杂问题时代码冗长：对于一些树形/分治类问题，递推写法可能很复杂，不如递归简洁。

使用场景

数列型问题（斐波那契、爬楼梯、动态规划等），只依赖前几个状态。

大规模计算，尤其是 $n$ 很大时（如 $10^6$ ）。

递推

优势

代码简洁直观：直接对应数学定义，逻辑清晰。

容易写出初版代码：方便快速实现和验证。

劣势

时间复杂度高：指数级，如 $O(2^n)$ 。

重复计算严重：子问题被多次求解。

可能栈溢出：递归层数太深会导致程序崩溃。

使用场景

仅适合小规模 $n$ 。

树遍历、分治问题等天然适合递归的结构。

递归 + 记忆化

优势

时间复杂度降为 $O(n)$ ：避免了重复计算。

代码简洁：既保持递归的直观，又有较好性能。

更接近数学定义：容易和公式一一对应。

劣势

需要额外存储： $O(n)$ 空间来保存子问题结果。

比迭代慢一些：递归函数调用开销 + 哈希表/数组存储。

使用场景

需要递归思维清晰表达的动态规划问题（如树形 DP、区间 DP）。

问题较复杂时，递推不好直接写，递归+记忆化更自然。

最后简单总结为几点：

n 较小用递归。

n 较大用递推。

问题天然递归结构（树、分治、区间DP） → 用递归 + 记忆化。

问题线性、依赖前几个状态 → 优先用递推，代码更高效。

2.2 爬楼梯#

递推关系：dp[i] = dp[i-1] + dp[i-2]。

1
void solve() {
2
  int n;
3
  cin >> n;
4
  V<int> dp(n);
5
  dp[0] = 1, dp[1] = 2;
6
  for (int i = 2; i < n; i++) {
7
    dp[i] = dp[i - 1] + dp[i - 2];
8
  }
9
  cout << dp[--n] << endl;
10
}

3. 重点例题：P1028《数的计算》#

题意：以 n 开头，后一项 ≤ 前一项的一半，问序列个数。 讲解顺序（对标你讲义第 6–7 页）

递归思路： $f(n) = 1 + \sum_{1}^{\frac{n}{2} } f(i)$ ；1 表示“只取自己”。
为什么“纯递归会超”：递归树里大量重复子问题。
两种可过的方法：
- 记忆化递归；
- 递推 + 前缀和把内层求和降到 O(1)。

代码 A：记忆化递归

1
int memo[N];
2
bool vis[N];
3

4
void solve() {
5
  int n;
6
  cin >> n;
7
  function<int(int)> F = [&](int x) -> int {
8
    if (x == 1) {
9
      return 1;
10
    }
11
    if (vis[x]) {
12
      return memo[x];
13
    }
14
    vis[x] = true;
15
    long long s = 1;
16
    for (int i = 1; i <= x / 2; ++i) s += F(i);
17
    return memo[x] = s;
18
  };
19
  cout << F(n) << endl;
20
}

代码 B：递推 + 前缀和

1
void solve() {
2
  int n;
3
  cin >> n;
4
  V<int> f(n + 1), pre(n + 1);
5
  f[1] = pre[1] = 1;
6
  for (int i = 2; i <= n; i++) {
7
    f[i] = 1 + pre[i / 2];
8
    pre[i] = pre[i - 1] + f[i];
9
  }
10
  cout << f[n] << endl;
11
}

提示

先写“意义—边界—关系”，再选实现：能递推就递推；若递推式很难直接写、或本质是在“枚举结构”，再考虑递归/回溯。

练习2 把代码 A 改成“统计函数被调用次数”（全局 cnt++），与代码 B对比。

4. 回溯入门：P1036《选数》#

题意：n 个数里选 k 个，使和是素数，问方案数（n ≤ 20，完全够回溯）。思路：组合枚举。参数设计：idx（当前位置）、cnt（已选个数）、sum（当前和）。

标准写法

1
void solve() {
2
  int n, k, ans = 0;
3
  cin >> n >> k;
4
  V<int> a(n);
5
  cin >> a;
6
  auto prime = [&](auto x) {
7
    if (x < 2) {
8
      return false;
9
    }
10
    for (int d = 2; d * d <= x; d++) {
11
      if (x % d == 0) {
12
        return false;
13
      }
14
    }
15
    return true;
16
  };
17
  function<void(int, int, int)> dfs = [&](int idx, int cnt, int sum) {
18
    if (cnt == k) {
19
      ans += prime(sum);
20
      return;
21
    }
22
    if (idx == n) {
23
      return;
24
    }
25
    if (n - idx < k - cnt) {
26
      return;
27
    }
28
    dfs(idx + 1, cnt + 1, sum + a[idx]);
29
    dfs(idx + 1, cnt, sum);
30
  };
31
  dfs(0, 0, 0);
32
  cout << ans << endl;
33
}

要点

“回溯三步”不要错位：做选择 → 递归 → 撤销选择。
剪枝思路：如果 n-idx < k-cnt，再怎么递归也不可能凑满——立刻返回。

练习3

加“剪枝 2”：若输入全为正数，可设一个“当前和上界”，超了就停。
把“组合枚举”改成“字典序列举”？（提示：把 for 改为从 i=idx 往后选，或维护 path。）

5. 收束与强化#

5.1 汉诺塔（理解“先分后合”）#

把 3 个盘的移动顺序打印出来，“先把 n-1 移到中柱 → 移第 n 个 → 再把 n-1 移到目标”。

1
  function<void(int, char, char, char)> hanoi = [&](int n, char A, char B,
2
                                                    char C) {
3
    if (n == 0) return;
4
    hanoi(n - 1, A, C, B);
5
    cout << A << " -> " << C << "\n";
6
    hanoi(n - 1, B, A, C);
7
  };

5.2 要点#

边界：n==0/1、空集/空指针是否返回正确？
收敛：每次递归参数都在“变小/更近边界”吗？
重复计算：需要就记忆化；能改“递推”最好。
栈深：递归太深（>1e5）改迭代或手动栈。
类型：计数尽量 long long。
回溯：有没有撤销？

5.3 课后练习#

P1028《数的计算》：分别用记忆化递归与前缀和递推提交，记录时间差；
P1036《选数》：把“素数判定”改成“和是完全平方数”；
完成vj对应的题目；
理解归并而非背诵。