递归_专项题单练习

递归

1. 递归常用结构

递归常见三种形态：

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

------

2. 解题基本套路

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

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

------

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 类别定义

自相似

5.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 类别定义

1）同步替换型

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

2）层叠拼接型

基础层：$S^{(0)}=A$
递归层：

6.2 思路技巧

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

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

$len[0][x]=1$
若 $R(x)=c_1c_2\cdots c_m$，则

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

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$ 的总出现次数

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

整段吃完：直接加整段贡献
只吃一部分：固定块算前缀，子结构递归到 $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、广度优先搜索

【思维导图】

【题目知识点分类】

竞赛

考级认证

学习入口

递归

递归