递归

题单类型：官方题单

创建人：

ACGO官方

题数：20题

收藏题单

完成度：0/20

递归

1. 递归常用结构

递归常见三种形态：

线性递归：每次只递归调用一次，例如阶乘、辗转相除法
树形递归：一次递归调用多次，形成递归树，例如斐波那契、分形图案
分治递归：把大问题分成几个“相同类型的小问题”，分别递归后再合并，例如生成字符串、快速排序思想等

2. 解题基本套路

做递归题时按这四步想，基本不会乱：

结束条件：最小子问题怎么直接算
分解方式：大问题怎么拆成小问题
递归调用：把小问题交给递归函数
合并结果：把小问题答案组合成大问题答案

3. 数值计算类

3.1 类别定义

通过递归公式计算数学序列或函数值的题目。这类题通常直接根据数学递推关系实现算法，如阶乘、斐波那契等经典例子。

3.2 鉴别方法

题目中出现了第 $n$ 项
给出了如何计算的方法
数据范围较小（或递归深度不会太大）

3.3 思路技巧

找出问题的结束条件和递推关系，将大问题缩小为更小的子问题递归求解，直到触及结束条件返回结果。

3.4 伪代码

下面用“辗转相除法”做模板：

// 目标：计算 gcd(a, b)
// 思想：gcd(a, b) = gcd(b, a%b)
// 结束：当 b == 0 时，答案就是 a

int gcd(int a, int b) {
    // 1) 结束条件：b 为 0，说明除尽了
    if (b == 0) return a;

    // 2) 分解：把大问题 gcd(a, b) 变成更小的 gcd(b, a%b)
    // 3) 递归调用：交给 gcd(b, a%b) 去算
    return gcd(b, a % b);

    // 4) 合并：这里不需要额外合并，因为递归返回值就是答案
}

3.5 典型题目

辗转相除法
递归函数(一)
递归函数(二)
猴子上台阶

4. 模型构造类

4.1 类别定义

使用递归模拟状态变化或解题过程，常见于谜题（如汉诺塔、约瑟夫环）等。

4.2 思路技巧

每一步模拟当前状态并递归推进。通过递归传递当前状态参数（例如起点、终点、辅助点、当前规模等）。

4.3 鉴别方法

存在“步骤模拟”
涉及状态转移、多种操作尝试

4.4 伪代码

用汉诺塔做模板：

// 目标：把 n 个盘子从 A 移到 C，B 作为辅助
// 关键想法：先搬走上面 n-1 个，再搬最大盘，再搬回 n-1 个

void hanoi(int n, char A, char B, char C) {
    // 1) 结束条件：只有 1 个盘子，直接从 A 移到 C
    if (n == 1) {
        print(A, "->", C);
        return;
    }

    // 2) 分解：把“搬 n 个盘子”拆成 3 件事
    // (1) 先把 n-1 个从 A 搬到 B（用 C 辅助）
    hanoi(n - 1, A, C, B);

    // (2) 再把最大的那一个从 A 搬到 C
    print(A, "->", C);

    // (3) 最后把 n-1 个从 B 搬到 C（用 A 辅助）
    hanoi(n - 1, B, A, C);

    // 3) 递归调用：就是上面两次 hanoi(...)
    // 4) 合并结果：输出顺序就是合并（先子问题1，再一步，再子问题2）
}

4.5 典型题目

A96813.凋灵骷髅
A559.汉诺塔

5. 分形图案类

5.1 类别定义

按照递归规律生成自相似图形的题目。这类题要求输出经过 $n$ 次递归后的图案。整体图案由缩小的子图案重复构成，整体与局部具有相似结构。

5.2 思路技巧

确定基础图形（ $n=0$ 或 $n=1$ 时的简单图案）作为结束条件
找出更高层如何由若干个子图案拼出来（位置、大小缩放）
用二维数组保存图像，递归函数通常带四个参数表示范围： $(x_1,y_1,x_2,y_2)$
最后把二维数组输出

5.3 鉴别方法

需要输出“分形结构”或“图案形状”
具有“整体结构与局部结构相似”的自相似特性

5.4 伪代码

下面给一个通用“在二维数组里画分形”的模板。具体画法取决于题目。

// 画布是 board[][]，初始都填空格 ' '
// draw(level, x1, y1, size) 表示在 (x1,y1) 左上角，边长 size 的正方形区域里画第 level 层图案

void draw(int level, int x1, int y1, int size) {
    // 1) 结束条件：level==0 时，画一个最小基础图形
    // 例如画一个点（或画一个小方块、一个字符等）
    if (level == 0) {
        board[x1][y1] = '*';
        return;
    }

    // 2) 分解：更高层由若干个“更小的子图形”拼成
    // 假设每层把 size 缩小为 size/2（只是示例，具体看题）
    int half = size / 2;

    // 3) 递归调用：把子图画到指定位置
    // 下面只是示例：画 3 个子图（左上、右上、左下）
    draw(level - 1, x1,        y1,        half);
    draw(level - 1, x1,        y1 + half, half);
    draw(level - 1, x1 + half, y1,        half);

    // 4) 合并结果：不用额外做事，因为子图已经直接写进 board[][] 里了
}

5.5 典型题目

A82885.分形图（一）
A82886.分形图（二）

6. 递归生成串的索引 / 计数查询（不展开长串）

6.1 类别定义

给定由递归规则定义的长串或层叠结构，要求在不显式构造完整结果的前提下，回答第 $k$ 位字符、前 $X$ 位计数等查询。常见两类：

1）同步替换型

给定字母表（符号集合） $\Sigma$ 和替换规则表：

初始串： $S^{(0)}=S$
替换规则：对每个符号 $x\in\Sigma$ ，给定字符串 $R(x)\in\Sigma^*$
同步替换（第 $t$ 轮到 $t+1$ 轮）：
$S^{(t+1)} = R\big(S^{(t)}_1\big)+R\big(S^{(t)}*2\big)+\cdots+R\big(S^{(t)}*{|S^{(t)}|}\big)$

常见查询：给定 $t,k$ ，求 $S^{(t)}[k]$ （从左到右第 $k$ 位，下标从 $1$ 开始）。

2）层叠拼接型

基础层： $S^{(0)}=A$
递归层：
$S^{(L)}=X_1+S^{(L-1)}+X_2+S^{(L-1)}+\cdots+X_k$
其中 $X_1,\dots,X_k$ 为固定块， $+$ 表示拼接。

6.2 思路技巧

A. 同步替换型（第 $k$ 位字符查询）

A1. 关键预处理：展开长度 $len[i][x]$

定义： $len[i][x]$ 表示“从单字符 $x$ 出发，替换 $i$ 轮后的长度”。

$len[0][x]=1$
若 $R(x)=c_1c_2\cdots c_m$ ，则
$len[i+1][x]=\sum_{j=1}^{m}len[i][c_j]$

长度爆炸，需要截断：

$len[i+1][x]=\min(len[i+1][x],INF),\qquad INF\ge k_{\max}$

A2. 查询：先定位块，再下钻

因为

$S^{(t)}=R^{(t)}(S_1)+R^{(t)}(S_2)+\cdots+R^{(t)}(S_{|S|})$

所以第 $k$ 位先落在某个字符块 $R^{(t)}(S_j)$ ，再进入该块内部继续找。

A3. 伪代码

// 目标：回答 Query(t, k) = S^(t)[k]，k 从 1 开始
// 核心：不生成串，只用 len 来“跳段定位”

const long long INF = 1e18;

// ---------- 1) 预处理 len[i][x] ----------
// len[i][x]：从单字符 x 出发，替换 i 次后长度
for (char x : Sigma) {
    len[0][x] = 1;                 // i=0 时就是自己，长度 1
}

for (int i = 0; i < Tmax; i++) {
    for (char x : Sigma) {
        len[i + 1][x] = 0;         // 先清零，准备加总
        for (char c : R[x]) {      // R[x] 是替换串
            len[i + 1][x] += len[i][c];
            if (len[i + 1][x] > INF) len[i + 1][x] = INF; // 截断防爆
        }
    }
}

// ---------- 2) Solve(t, x, k)：在单字符展开里找第 k 位 ----------
char Solve(long long t, char x, long long k) {
    // 含义：在 R^(t)(x) 中找第 k 个字符（k 从 1 开始）

    while (t > 0) {
        // 这一层：x 会变成 R[x] = c1 c2 ... cm
        // 并且：R^(t)(x) = R^(t-1)(c1) + R^(t-1)(c2) + ...

        for (char c : R[x]) {
            long long seg = len[t - 1][c];     // 当前段 R^(t-1)(c) 的长度

            if (k > seg) {
                // k 不在这一段里：跳过整段
                k -= seg;
            } else {
                // k 在这一段里：进入这一段继续找
                x = c;                         // 进入子字符
                t = t - 1;                     // 层数减少
                break;                         // 去下一层 while
            }
        }
    }

    // t==0 时：R^(0)(x) 就是 x 自己，答案就是 x
    return x;
}

// ---------- 3) Query(t, k)：先在初始串 S 上定位块 ----------
char Query(long long t, long long k) {
    long long tt = min(t, (long long)Tmax);    // t 太大时截到 Tmax（len 只算到这里）

    // S^(tt) = R^(tt)(S[0]) + R^(tt)(S[1]) + ...
    // 所以第 k 位必在某个块里，逐块跳过即可
    for (int j = 0; j < S.size(); j++) {
        char x = S[j];
        long long block = len[tt][x];          // 这一块的长度

        if (k > block) {
            // 第 k 位不在这块里：跳过整块
            k -= block;
        } else {
            // 第 k 位在这块里：进入块内部继续找
            return Solve(tt, x, k);
        }
    }

    return '?'; // 一般题目保证 k 合法，不会到这里
}

B. 层叠拼接型

B1. 预处理：每层长度 $len[L]$ 与总计数 $cnt[L]$

$len[L]=|S^{(L)}|$
$cnt[L]$ 表示 $S^{(L)}$ 中目标符号 $\sigma$ 的总出现次数

若

$S^{(L)}=X_1+S^{(L-1)}+X_2+S^{(L-1)}+\cdots+X_k$

则

$len[L]=|X_1|+len[L-1]+|X_2|+len[L-1]+\cdots+|X_k|$

$cnt[L]=c(X_1)+cnt[L-1]+c(X_2)+cnt[L-1]+\cdots+c(X_k)$

其中 $c(X)$ 表示块 $X$ 中 $\sigma$ 的出现次数（同样要对 $len,cnt$ 做 $INF$ 截断）。

B2. 前缀计数函数 $f(L,n)$

$f(L,n)$ ： $S^{(L)}$ 的前 $n$ 个字符里， $\sigma$ 出现次数。

思路：从左到右扫构造式的每一段：

整段吃完：直接加整段贡献
只吃一部分：固定块算前缀，子结构递归到 $f(L-1,\cdot)$

B3. 伪代码

// 目标：f(L, n) = S^(L) 的前 n 个字符中，sigma 的出现次数
// 核心：能整段吃下就不递归，吃不下才递归

const long long INF = 1e18;

// f(L, n)：n 可以是 0..len[L]
long long f(int L, long long n) {
    // 1) 取前 0 个字符：答案一定是 0
    if (n <= 0) return 0;

    // 2) 前缀覆盖整串：直接返回整串计数
    if (n >= len[L]) return cnt[L];

    // 3) 到最底层：S^(0)=Base，是固定串，直接数 Base 的前 n 个
    if (L == 0) return count_sig_in_prefix(Base, n);

    long long ans = 0;

    // 4) 从左到右扫描 “这一层的拼接公式”
    // formula_of_level_L 是一个段序列：段要么是固定块 X，要么是子结构 S(L-1)
    for (segment : formula_of_level_L) {
        if (n <= 0) break; // 已经取够前缀了

        if (segment is fixed block X) {
            // 5) 固定块：最多取 take 个
            long long take = min(n, (long long)|X|);

            // 6) 加上 X 的前 take 个字符里 sigma 的数量
            ans += count_sig_in_prefix(X, take);

            // 7) 前缀长度减少
            n -= take;

        } else {
            // 8) 子结构段：就是 S(L-1)
            long long take = min(n, len[L - 1]);

            if (take == len[L - 1]) {
                // 9) 子结构整段被取完：直接加总数，不递归
                ans += cnt[L - 1];
            } else {
                // 10) 子结构只取一部分：必须递归到下一层
                ans += f(L - 1, take);
            }

            // 11) 前缀长度减少
            n -= take;
        }
    }

    return ans;
}

6.3 典型题目

层叠拼接型（汉堡汉堡汉）
同步替换型（字字字字符串）

【前置知识点】
1、排序

【后置衔接知识点】
1、深度优先搜索
2、广度优先搜索

【思维导图】

【题目知识点分类】

递归

递归