递归

✨ 什么是递归？¶

递归（Recursion） 是一种解决问题的方法，它使得一个函数在定义时调用自己。

我们用一个经典的定义来说明：

递归定义：当一个问题可以通过更小规模的相同问题来解决，并且存在一个明确的终止条件，这种方法就是递归。

🔁 递归的执行过程¶

可以这样理解：递归是一种“不断分解问题”的过程。

我们每次递归，都是把一个大问题，分解成一个更小的问题，然后继续解决更小的问题。

当问题被分解到最简单的情况（也就是我们设定的“终止条件”）时，我们就可以直接给出答案；然后再一步步返回每一层的答案。

类比：找人帮忙的故事¶

假设你要找出 $1 + 2 + \dots + 5$ 的和，但你不想一次做完。

于是你去问你的朋友：你能帮我算出 $1 + 2 + 3 + 4 + 5$ 的和吗？

他想了想，说：我不知道，但我可以问另一个人算 $1 + 2 + 3 + 4$ 的和，然后再加上 $5$。

这个人也去问别人，直到有一个人说：我知道 $1$ 的值是 $1$。

然后他告诉上面一个人答案是 $1$；上面那个人加上 $2$，变成 $3$，继续告诉上一个人。直到最开始问问题的人得到结果是 $15$。

这就是递归的执行方式：

一层一层地向下拆解问题（像递话一样传下去）
然后一层一层地把答案传回来（像传回话一样）

📦 递归函数的三要素¶

递归函数一般包括以下 三要素：

1. 终止条件（Base Case）¶

必须要有！防止函数无限调用。

例如：

if (n == 0) return;

2. 递归公式（递推关系）¶

将大问题转化为小问题的表达式或逻辑。

例如：

\[ f(n) = f(n - 1) + f(n - 2) \]

3. 递归调用（Self-call）¶

函数自身调用自身，并逐步向终止条件靠近。

🛠️ 常见递归例题¶

例题1：返回 $1 + 2 + … + n$¶

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

例题2：返回 $n!$¶

众所周知：$n! = n * (n - 1)!$，根据这个容易写出如下的递归代码。

int fac(int n) 
{
    if (n == 0) return 1;
    return n * fac(n - 1);
}

例题3：返回第 $n$ 个斐波那契数¶

斐波那契数列的定义为：

\[\texttt{fib(n)}=\begin{cases} 1, &\texttt{if } n\leq 2\\ \texttt{fib}(n-1)+\texttt{fib}(n-2), &\texttt{otherwise} \end{cases}\]

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

备注：第 $n$ 个斐波那契数列：$1, 1, 2, 3, 5, 8, 13, ...$

⚠️ 递归算法的注意事项¶

避免无限递归，确保有 Base Case
避免重复计算（考虑转化为动态规划）
不要在递归中使用太多变量重复调用，除非有算法优化

🧠 进阶：记忆化递归（Memoization）¶

在递归问题中，如果我们反复计算相同的子问题，会导致效率非常低。比如上面的 fib(n)，会重复计算很多次 fib(3)、fib(4) 等。

记忆化递归 是一种在递归基础上进行优化的技术，方法是在函数中加一个“备忘录”，记录已经计算过的结果，下次再遇到就直接返回。

✅ 优点¶

大幅度降低时间复杂度
编码简单，易于理解

🚀 示例：记忆化递归实现斐波那契数列¶

const int N = 1e5 + 5, mod = 998244353;
int a[N];

int fib(int n) 
{
    if (n == 1 || n == 2) return 1;
    if (a[n] != -1) return a[n]; // 如果计算过就直接返回
    return a[n] = (fib(n - 1) + fib(n - 2)) % mod;
}

int main()
{
    memset(a, -1, sizeof(a));
    int n;
    cin >> n;
    cout << fib(n);
}

memset，按照字节赋值

memset(a, 0, sizeof(a)); 数组均初始化为为 $0$。
memset(a, -1, sizeof(a)); 数组均初始化为为 $-1$。
memset(a, 0x3f, sizeof(a)); 极大值。int 大约为 $10$ 亿多。long long 大约为 $4\times 10^{18}$。
memset(a, 0xc0, sizeof(a)); 极小值。int 大约为 $-10$ 亿多。long long 大约为 $-4\times 10^{18}$。

后两个主要用在求最值时的初始化。

多组数据谨慎使用 memset

例如：本题为多组数据，第一行输入 $t$ 代表测试数据组数。

先输入一个 $n$，代表数字个数
然后输入 $n$ 个空格隔开的数字代表 $a_1,a_2,\ldots,a_n$

数据范围：

$n <= 10^5$
$t <= 10^5$
一个测试点内所有 $n$ 的和不超过 $10^5$
- 例如：、$t = 10^5$，$n$ 只能取到 $1$。

常见 TLE 如下

int a[100005]; 

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(a, 0, sizeof(a)); 
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
    }
}

只需要清空 a[1]，但是 memset 把 $a[0] \sim a[100004]$ 全清空了导致 TLE。因为此时的计算量是 $t\times (10^5+5)>10^8$。

⏱️ 时间复杂度分析：¶

普通递归：指数级 $O(2^n)$
记忆化递归：线性时间 $O(n)$，每个子问题只计算一次