C++ 算法技巧 — 递推与递归 (Iteration & Recursion)

章节概述

递推通过已知值逐步推导未知值；递归将大问题分解为同结构的小问题。
两者方向相反但本质相通：递推是自底向上，递归是自顶向下。

核心原理

1. 递推 — 自底向上

递推的三要素：

初始条件: 递推的种子值（如 f[0]=0, f[1]=1）
递推公式: 当前项如何由前面项推导（如 f[n]=f[n-1]+f[n-2]）
方向: 从已知出发，逐步计算到目标

递推通用框架:

初始化边界条件: f[0], f[1], ...
for i = 2 to n:
    f[i] = derive(f[i-1], f[i-2], ...)
输出 f[n]

2. 递归 — 自顶向下

递归的三要素：

基准情况 (Base Case): 直接求解的终止条件
递归分解: 将 n 的问题分解为 n-1 的子问题
组合: 将子问题结果组合得大问题结果

fn solve(n):
    if n <= 1: return base_value      // 基准
    return combine(solve(n-1), ...)    // 递归 + 组合

3. 递推 vs 递归

特性	递推	递归
方向	自底向上	自顶向下
实现	循环 + 数组	函数调用 + 栈
空间	O(n) 数组或 O(1) 滚动	O(n) 递归栈 + O(n) 缓存
风险	无	递归过深导致栈溢出

4. 卡特兰数 (Catalan Number)

递推: $f [0] = 1, f [n] = \sum_{i = 0}^{n - 1} f [i] \cdot f [n - 1 - i]$

通项: $f [n] = \frac{C ( 2 n , n )}{n + 1}$

应用: 栈输出序列数、二叉树形态数、合法括号序列数。

关键数据结构

B_栈_Stack — 递归本质使用系统调用栈
I_树_Tree_BST_AVL — 树的递归遍历、分治建树
Q_排序_八大排序_Sorting — 归并/快排的分治递归思想

P1028 [NOIP2001 普及组] 数的计算

题目: 给出 n，求有多少个数列满足：第一个数为 n，后面每个数不超过前一个数的一半，
直到不能再加数为止。

思路: 递推公式 f[n] = 1 + Sum_{i=1}^{n/2} f[i]，其中 f[1]=1。

#include <iostream>
using namespace std;
int f[1001];
 
int main() {
    int n;
    cin >> n;
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i / 2; j++)
            f[i] += f[j];
        f[i]++;
    }
    cout << f[n] << endl;
    return 0;
}

P1036 [NOIP2002 普及组] 选数

题目: 已知 n 个整数，任选 k 个相加，求和为素数的方案数。

思路: DFS 递归枚举组合，对每个组合判断和是否为素数。

#include <iostream>
using namespace std;
int n, k, a[21], ans;
 
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}
 
void dfs(int idx, int cnt, int sum) {
    if (cnt == k) {
        if (isPrime(sum)) ans++;
        return;
    }
    if (idx >= n) return;
    dfs(idx + 1, cnt + 1, sum + a[idx]);
    dfs(idx + 1, cnt, sum);
}
 
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

P1044 [NOIP2003 普及组] 栈

题目: 一个操作数序列 1,2,…,n，通过一个栈进行 push 和 pop 操作。问可能的输出序列总数。

思路: 这就是卡特兰数问题。递推公式: f[0]=1, f[n] = Sum_{i=0}^{n-1} f[i] * f[n-1-i]。

#include <iostream>
using namespace std;
int f[20];
 
int main() {
    int n;
    cin >> n;
    f[0] = f[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < i; j++)
            f[i] += f[j] * f[i - 1 - j];
    cout << f[n] << endl;
    return 0;
}

P1164 小A点菜

题目: 小A有 M 元钱，N 种菜每种有且只有一份，价格分别为 a_i。问刚好花完 M 元的点菜方案数。

思路: 01 背包方案数问题。dp[j] 表示花费 j 元的方案数，dp[0]=1，转移: dp[j] += dp[j-a[i]]。

#include <iostream>
using namespace std;
int dp[10001];
 
int main() {
    int n, m, a;
    cin >> n >> m;
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        cin >> a;
        for (int j = m; j >= a; j--)
            dp[j] += dp[j - a];
    }
    cout << dp[m] << endl;
    return 0;
}

RootStack

探索

C++ 算法技巧 — 递推与递归 (Iteration & Recursion)

章节概述

核心原理

关键数据结构

P1028 [NOIP2001 普及组] 数的计算

P1036 [NOIP2002 普及组] 选数

P1044 [NOIP2003 普及组] 栈

P1164 小A点菜

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接