递归入门：从数列递推到多分支搜索

递归是算法入门的第一个核心坎，本质就是把数学里的递推关系写成代码，核心思想是分治：要解决一个大问题，先解决更小规模的同类型问题，用小问题的结果推导出大问题的答案。

我们从最基础的数列递推入手，一步步讲到双分支递归、递归树、记忆化优化，最后延伸到多分支递归，全程对应洛谷入门原题。

一、单分支递归：从递推公式直接翻译

最容易理解的递归都来自数列递推，这类递归只有一个递归调用入口，也叫单分支递归，是所有递归的基础，对应洛谷最入门的递归题。

1. 入门例1：数列求和（对应 P5722 数列求和）

题目：计算 $1+2+3+\dots+n$ 的和。

递推关系非常直观：

• 前n项的和 = 第n项 + 前n-1项的和
• 写成公式：$f(n) = n + f(n-1)$
• 终止条件：当 $n=1$ 时，和就是1，即 $f(1)=1$

直接翻译成递归代码：

int f(int n) {
    if(n == 1) return 1;    // 终止条件：最小规模问题，直接返回答案
    return n + f(n - 1);    // 递推关系：大问题拆成更小的同类型问题
}

2. 入门例2：等差数列

递推公式：$A_n = A_{n-1} + d$，首项为 $a_1$
同样可以直接翻译为递归：

int a1, d;
int f(int n) {
    if(n == 1) return a1;
    return f(n - 1) + d;
}

递归的固定代码结构

所有递归函数都由两部分构成：

1. 终止条件（回溯终点）：问题小到不能再拆分时，直接给出答案，防止无限递归栈溢出
2. 递推关系：把大问题拆解成一个或多个更小的同类型问题，调用自身求解

理解递归的第一原则：不要试图逐层跟踪每一次调用。只要保证终止条件正确、递推关系正确，递归结果就一定正确。

二、双分支递归：上台阶与二叉递归树

单分支递归和普通循环没有本质区别，真正体现递归特性的是多分支问题。最经典的就是上台阶问题，和斐波那契数列（对应 B2032）完全同源。

问题引入：上台阶

有n级台阶，每次可以走1级或者2级，问走到第n级一共有多少种不同的走法？

递推推导

要走到第n级，只有两种可能的来路：

1. 从第n-1级走1步上来
2. 从第n-2级走2步上来

因此总走法 = 到n-1级的走法 + 到n-2级的走法
公式：$f(n) = f(n-1) + f(n-2)$
终止条件：

• $f(1) = 1$（1级台阶只有1种走法）
• $f(2) = 2$（2级台阶有2种走法：1+1、直接走2步）

基础递归代码

int f(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    return f(n - 1) + f(n - 2);
}

二叉递归树：看清递归执行过程

这个函数每次会分裂出两个递归调用，执行过程画出来就是一棵二叉树。我们以n=5为例：

                f(5)
              /      \
          f(4)        f(3)
        /    \      /    \
      f(3)  f(2)  f(2)  f(1)
      /  \
    f(2) f(1)

每一个叶子节点（f(1)、f(2)）都会触发终止条件，直接返回值，然后结果一层层向上汇总，最终得到f(5)的答案。

致命问题：重复子问题

仔细观察这棵树：f(3)被重复计算了2次，f(2)被重复计算了3次。当n变大时（比如n=40），重复节点会指数级爆炸，程序直接超时。

三、记忆化递归：剪掉重复的树枝

既然大量节点被重复计算，优化思路就很直接：把算过的结果存起来，下次再用到时直接返回，不用重新计算。这就是记忆化，也叫记忆化搜索，本质是一种剪枝。

实现步骤

1. 开一个记忆化数组 mem[]，初始值全部设为-1，表示该位置还没算过
2. 进入函数先判断：如果 mem[n] != -1，说明已经算过，直接返回存储的结果
3. 没算过就正常递归计算，算完后把结果存入 mem[n]，再返回

完整记忆化代码（对应 B2032 斐波那契类题目）

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 7;
int mem[N]; // 记忆化数组，存已经算过的结果

int f(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    if(mem[n] != -1) return mem[n]; // 算过了，直接返回，不再递归
    return mem[n] = f(n-1) + f(n-2); // 算完存进数组，再返回
}

signed main() {
    int n;
    cin >> n;
    memset(mem, -1, sizeof(mem)); // 初始化：全部标记为未计算
    cout << f(n) << endl;
    return 0;
}

加了记忆化之后，递归树里每个节点只会被计算一次，时间复杂度直接从 $O(2^n)$ 降到 $O(n)$，n=1e5 都不会超时。

四、多分支递归：数的计算与多叉递归树

双分支递归只有两个调用入口，更复杂的问题里，每次递归会分裂出多个分支，这时候就要用循环来生成递归调用，对应多叉递归树。最经典的例题就是洛谷 P1028 数的计算。

问题引入（P1028 数的计算）

给出正整数n，按如下规则操作：

1. 原数本身算一个；
2. 可以在左边加一个不超过原数一半的自然数；
3. 加完之后继续按规则处理，直到不能再加为止。
   问一共能生成多少个不同的数。

递推推导

定义 f(n)：以n为原数，能生成的数的总个数。
根据规则：

• n自己算1个
• 左边可以加 1、2、…、n/2，每个数又对应各自的生成数量
  因此公式：$f(n) = 1 + f(1) + f(2) + \dots + f(\lfloor n/2 \rfloor)$
  终止条件：$f(1) = 1$（只能生成自己）

循环+递归：实现多分支

因为有 n/2 个分支，不可能一个个写出来，用循环遍历所有可能的加数，每个都触发一次递归：

int f(int n) {
    if(n == 1) return 1;
    int res = 1; // 自己本身算1个
    for(int i = 1; i <= n/2; i++) { // 循环遍历所有可加的数
        res += f(i);
    }
    return res;
}

多叉递归树

以n=6为例，递归树是一棵多叉树：

          f(6)
      /    |    \
    f(1)  f(2)  f(3)
           |      |
          f(1)   f(1)

每个节点的分支数量等于 n/2，越往下分支越少。如果不加记忆化，同样会有大量重复计算，比如 f(1) 会被调用很多次，n大了同样会超时。

加上记忆化

和双分支的写法完全一致，加一个记忆化数组即可：

int mem[N];
int f(int n) {
    if(n == 1) return 1;
    if(mem[n] != -1) return mem[n];
    int res = 1;
    for(int i = 1; i <= n/2; i++) {
        res += f(i);
    }
    return mem[n] = res;
}

加完记忆化后，每个 f(i) 只会计算一次，直接把时间复杂度压到线性级别。

五、递归的通用思考步骤

不管是单分支、双分支还是多分支递归，思考方式都是统一的：

1. 定义函数含义：明确 f(n) 代表什么，比如「第n项的值」「n级台阶的走法数」「n能生成的数的个数」
2. 找终止条件：找到最小规模的、可以直接给出答案的情况
3. 找递推关系：想清楚大问题怎么拆成更小的同类型问题
4. 判断是否加记忆化：如果存在重复子问题，就加记忆化数组剪枝

刚接触递归时，多画递归树是最好的理解方法。画几次就能直观看到程序的执行路径，以及哪里存在重复计算，自然就能写出正确的优化代码。

对应洛谷题目清单