LANSGANBS

With a determined mindset, no obstacle is insurmountable.

统计加载中...

公告

如需添加友链，可以在任意文章下评论，并留下网站名称,链接,介绍和头像链接。

关于本站

1592 字

8 分钟

递推与递归

2025-08-23

2025-10-04

算法竞赛

算法与数据结构

统计加载中...

递推与递归#

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) 再一层层返回。

把 add(a, b) 写成递归：

alt text

例如：

我们高中熟悉的通项公式：

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

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

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

1. 方法与模板#

1.1 三步方法#

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

1.2 三个模板#

(A) 递推

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 斐波那契数列#

定义：

f(0)=0,\quad f(1)=1,\quad f(n)=f(n-1)+f(n-2)\ (n\ge 2)

递推 $O(n)$

1
long long fib_iter(int n) {
2
  if (n < 2) return n;
3
  long long a = 0, b = 1;
4
  for (int i = 2; i <= n; ++i) {
5
    long long c = a + b;
6
    a = b, b = c;
7
  }
8
  return b;
9
}

递归 + 记忆化 $O(n)$

1
long long fib_memo(int n, vector<long long>& memo) {
2
  if (n < 2) return n;
3
  if (memo[n] != -1) return memo[n];
4
  return memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
5
}

快速倍增 $O(logn)$

1
pair<long long,long long> fib_fast(long long n) {
2
  if (n == 0) return {0, 1};
3
  auto [a, b] = fib_fast(n >> 1);     // a=F(k), b=F(k+1)
4
  long long c = a * (2*b - a);        // F(2k)
5
  long long d = a*a + b*b;            // F(2k+1)
6
  if ((n & 1) == 0) return {c, d};
7
  else              return {d, c + d};
8
}

递归树：

alt text

朴素递归会重复计算同一子问题（重叠子问题），导致指数级调用次数。记忆化避免重复计算，每个 n 只算一次。

小结

依赖前几个状态 → 优先迭代（快且省内存）。
需要自顶向下表达式清晰 → 递归+记忆化。
超大 n 或取模 → 快速倍增。

2.2 爬楼梯（基础 + 常见变体）#

基础版：每次上 1 或 2 阶，求到第 n 阶的方法数。

dp[i] = dp[i-1] + dp[i-2]，dp[1]=1, dp[2]=2

1
long long climb2(int n) {
2
  if (n <= 2) return n;
3
  long long a = 1, b = 2;
4
  for (int i = 3; i <= n; ++i) {
5
    long long c = a + b;
6
    a = b, b = c;
7
  }
8
  return b;
9
}

2.3 数字三角形（递推与记忆化二选一）#

递推

1
int n;
2
cin >> n;
3
vector<vector<int>> a(n+1, vector<int>(n+1, 0));
4
for (int i = 1; i <= n; ++i)
5
  for (int j = 1; j <= i; ++j)
6
    cin >> a[i][j];
7

8
for (int i = n - 1; i >= 1; --i)
9
  for (int j = 1; j <= i; ++j)
10
    a[i][j] += max(a[i+1][j], a[i+1][j+1]);
11

12
cout << a[1][1] << '\n';

记忆化

1
int n;
2
vector<vector<int>> a, memo;
3
int solve(int i, int j) {
4
  if (i == n) return a[i][j];
5
  int &res = memo[i][j];
6
  if (res != INT_MIN) return res;
7
  res = a[i][j] + max(solve(i+1,j), solve(i+1,j+1));
8
  return res;
9
}

2.4 快速幂#

1
long long qpow(long long a, long long b, long long mod) {
2
  long long res = 1 % mod;
3
  a %= mod;
4
  while (b > 0) {
5
    if (b & 1) res = res * a % mod;
6
    a = a * a % mod;
7
    b >>= 1;
8
  }
9
  return res;
10
}

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

题意：以 n 开头，后一项 ≤ 前一项的一半，问序列个数（“只取自己”也算一种）。

推导：

f(n) = 1 + \sum_{1}^{\frac{n}{2} } f(i)

方法 A：记忆化

方法 B：递推 + 前缀和 $O(n)$

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

题意：n 个数里选 k 个，使和是素数，求方案数（n ≤ 20）。

组合回溯
拓展：位枚举（非递归）

1
int count_prime_sum(const vector<int>& a, int k) {
2
  int n = a.size(), ans = 0;
3
  for (int mask = 0; mask < (1 << n); ++mask) {
4
    if (__builtin_popcount((unsigned)mask) != k) continue;
5
    int s = 0;
6
    for (int i = 0; i < n; ++i)
7
      if (mask >> i & 1) s += a[i];
8
    ans += is_prime(s);
9
  }
10
  return ans;
11
}

5. 一个经典问题#

5.1 汉诺塔#

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

6. 拓展练习#

6.1 P1464《函数 w》#

1
long long memo[21][21][21];
2
bool vis[21][21][21];
3

4
long long w(int a, int b, int c) {
5
  if (a <= 0 || b <= 0 || c <= 0) return 1;
6
  if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
7
  if (vis[a][b][c]) return memo[a][b][c];
8
  vis[a][b][c] = 1;
9
  long long &res = memo[a][b][c];
10
  if (a < b && b < c)
11
    res = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
12
  else
13
    res = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
14
  return res;
15
}

6.2 P1025《数的划分》#

把 n 划分成 k 个正整数的和（顺序不计，非降约束）

1
int n, k, ans;
2
void dfs(int pos, int last, int sum) {
3
  if (pos == k) { ans += (sum == n); return; }
4
  for (int x = last; x <= n; ++x) {
5
    if (sum + x + (k - pos - 1) * x > n) break; // 剪枝：最小填充也超了
6
    dfs(pos + 1, x, sum + x);
7
  }
8
}

6.3 括号生成（回溯，约束计数）#

1
void gen_paren(int n) {
2
  string path; vector<string> ans;
3
  function<void(int,int)> bt = [&](int open, int close) {
4
    if ((int)path.size() == 2*n) { ans.push_back(path); return; }
5
    if (open < n) { path.push_back('('); bt(open+1, close); path.pop_back(); }
6
    if (close < open) { path.push_back(')'); bt(open, close+1); path.pop_back(); }
7
  };
8
  bt(0, 0);
9
  // 输出 ans
10
}

6.4 全排列（回溯就地交换）#

1
void perm(vector<int> a, int u, vector<vector<int>>& all) {
2
  if (u == (int)a.size()) { all.push_back(a); return; }
3
  for (int i = u; i < (int)a.size(); ++i) {
4
    if (i != u && a[i] == a[u]) continue; // 若需要去重：先排序 + 这一行
5
    swap(a[i], a[u]);
6
    perm(a, u + 1, all);
7
  }
8
}

递推与递归

https://lansganbs.cn/posts/算法竞赛/递推与递归/

作者

LANSGANBS

发布于

2025-08-23

许可协议

CC BY-NC-SA 4.0

分治思想（归并排序）

米津玄师《打上花火》歌词及罗马音发音