递推、递归学习笔记

Update on 2021/10/1：对文章进行优化，修复 $\LaTeX$。

前言

各位~~在座的在站的在躺的在趴的以及以各种奇奇怪怪的姿势出现在电脑前的~~大佬们大家好，虽然我知道你们都是大佬，但是这篇博客，我还是会把你们当成萌新来讲解的（。

好了，废话不多说，下面进入正题。

概念

递推

mjl：从已知道的若干项出发，利用递推关系依次推算出后面的未知项的方法，我们称为递推算法。

做递推算法最关键的是找出递推式，然后再求出最简单的情况的值并存在数组里。

这个要直接求出值的情况个数要根据递推式来看。

比如说，如果一个递推式是 $f(i)=f(i-3)+f(i-2)$，那么我们需要把 $1,2,3$ 的情况都先写出来，然后从 $4$ 开始循环。

递推模板：

#include<cstdio>
const int maxn=...;
int a[maxn]={需要存的最简单的情况};
int main(){
    int n;
    scanf("%d",&n);
    for(int i=...;i<=n;i++){
        递推式;
    }
    printf("%d",a[n]);
}

递归

mjl：从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。

当然这是算法方面的解释，递归其实就是套娃函数自己调用自己，只不过比纯粹的套娃要难$10^8$ 些罢了（。

从算法的角度来说，显然无限套娃是没有意义的，所以我们也需要一个递归的出口来结束递归。

因为递归变化较多，模板不太好写，就不写了。

区别与联系

之所以把递推和递归放在一起讲说明他们是有共同点的，根据本人为数不多的做题经验（一定要多刷题啊！awa），可以发现递推和递归都是要推出在一个规律下，不同值对应的不同结果之间的关系，从而推出答案的值，也都需要一个出口来结束程序。

mjl：而递推与递归的不同之处在于，递归是从未知到已知，逐步接近解决问题的过程，而递推从已知到未知。

翻译成人话就是：递推是从小到大一点一点推，而递归是一个栈的结构——先从最终结果出发，一点一点往前推，直到推到出口，再根据出口的数值把答案推出来。

最直观的图：

（↑以 $f(x)=f(x-1)+x$ 且 $f(1)=1$ 举例，求 $f(5)$，递推与递归的区别与联系）

递推递归的 5 种模型

递推递归有一些模型，这些模型可以在递推和递归中通用。

1. 斐波那契数列（Fibonacci）

这是一种很简单的递推模型。

这种模型一般都是，此时第 $x$ 项数据与前面的数据有直接的数值关联（一般来说是很明显的倍数关系）。

例题-铺砖1

原题链接（CQBZOJ）

有 $2\times n$ 的一个长方形方格道路，只有一种的 $1\times 2$ 砖去铺，总共有多少种铺法？（$0\le n\le 45$）

很明显可以看到末尾的砖块（只是末尾）有两种放法：

竖着放一块；
横着放两块。

我们在放最新的第 $i$ 列，即末尾的砖块时，这两种放法对应着 $i-1$ 和 $i-2$ 的情况，如下图。

所以可以看出这是一道很经典的 Fibonacci 递推的题目。

递推式：$a_i=a_{i-1}+a_{i-2}$

$80$ 分代码（很简单）：

#include<cstdio>
int f(int n){
    if(n==1)return 1;
    if(n==2)return 2;
    else return f(n-1)+f(n-2);
}
int main(){
    int n;
    scanf("%d",&n);
    printf("%d",f(n));
    return 0;
}

至于为什么是 $80$ 分，这里先不说，看到后面就知道了。

2.汉诺塔（Hanoi）

汉诺塔本身的问题是把若干从小到大堆叠的圆盘借助一根辅助的柱子从一根柱子移到另一根柱子上，要求一次只能移动一个，而且大的不能压在小的上面。

我们研究最原始的问题。

例题-汉诺塔问题

原题链接（CQBZOJ）

有三个柱子，其中一根上从大到小叠着 $n$ 个圆盘。现在需要移动这些圆盘，规则如下：

一次只许移动一个盘；
任何时候、任何柱子不允许把大盘放在小盘上面；
可使用任一一根立柱暂存圆盘。

问：如何使用最少步数实现 $n$ 个盘子的移动？打印出具体移动方案。

数据范围：$1\le n\le 18$

我们可以假设这三根柱子分别为 $A$，$B$，$C$，我们把 $n$ 个盘子从 $A$ 借助 $B$ 移到 $C$ 上。

如果只有一个盘子，我们就直接移。

只有一个盘子

如果有两个以上的盘子，我们就分 $3$ 步做：

第一步：把上面 $n-1$ 个盘子从 $A$ 借助 $C$ 移到 $B$ 上，腾出 $C$ 的位置；

第一步

第二步：把留在 $A$ 上的最大的圆盘移到 $C$ 上；

第二步

第三步：把暂时放在 $B$ 上的其他圆盘从 $B$ 借助 $A$ 移到 $C$ 上。

第三步

而第一步和第三步怎么移过去，就需要继续把这个问题分解成最大的和其他的问题，直到只剩下一个圆盘，就直接移过去。

递推式（只求步数不求过程）：$a_i=2\times a_{i-1}+1$

要求输出过程只能用递归。

AC 代码：

#include<cstdio>
//n：圆盘数量，a、b、c：柱子编号
void h(int n,char a,char b,char c){
    if(n==0)return;
    h(n-1,a,c,b);           //第一步
    printf("%c->%c\n",a,c); //第二步
    h(n-1,b,a,c);           //第三步
}
int main(){
    int n;
    scanf("%d",&n);
    h(n,'A','B','C');
    return 0;
}

3.平面分割

用一些两两相交但是不会三个及以上相交的圆把平面分成若干个区域。

最简单的情况

观察答案，我们会发现：

$ans_2-ans_1=2$

$ans_3-ans_2=4$

$ans_4-ans_3=6$

$……$

很明显的差等差数列。发现这个之后规律就出来了：

递推式：$a_i=a_{i-1}+2\times (i-1)$

#include<cstdio>
int a[105]={0,2};
int main(){
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        a[i]=a[i-1]+2*(n-1);
    }
    printf("%d",a[n]);
}

4.卡塔兰数（Catalan）

难点来了！这玩意儿很难，主要是规律很难发现，而且做题也不容易看出来。

卡塔兰数本来是将一个 $n$ 边形通过不相交的对角线分成若干个三角形，求这个 $n$ 边形有多少种不同的划分方法。

最原始的题目：

原题链接（CQBZOJ）

要解决这个题目，首先我们需要一个 $n$ 边形：

n 边形

然后我们再选定一个 $i$（$2\leq i \leq n-1$）点，把 $1$ 到 $i$ 和 $n$ 到 $i$ 两条对角线连起来，把这个 $n$ 边形分成三个部分：（$i$ 以 $3$ 为例）

把这个多边形切了

可见，这个 $n$ 边形被分成了一个 $i$ 边形、一个三角形和一个 $(n-i+1)$ 边形。

而这个 $i$ 边形和 $(n-i+1)$ 边形可以用相同的方法去求解。

每个满足条件的 $i$ 点都可以选一遍。

所以这个递推式就是这样的：

$a_i=a_2\times a_{n-2+1}+a_3\times a_{n-3+1}+a_4\times a_{n-4+1}+\ldots+a_{n-1}\times a_2$

（当然要记住，$a_2=0$，但是我们在计算的时候，为了计算的准确，我们规定 a[0]=a[1]=a[2]=1，最后再把 $a_2$ 改回去。）

用求和公式表达就是：

$a_i=\sum_{j=2}^{n-1} \limits a_j\times a_{n-j+1}$

作为一个初学者，我并不明白 $\sum$ 这玩意儿是啥意思，其实它叫”求和符号“，具体大家去网上搜吧。

（这里就用递推了好理解一些，注意开 long long，不然会炸。）

a[0]=a[1]=a[2]=1;
for(int i=3;i<=n;i++){//从3开始枚举 
    for(int j=2;j<=i-1;j++){
        a[i]+=a[j]*a[i-j+1];
    } 
} 
a[2]=0;

好了讲完了理论我们就来看看实际应用。

例题-编程社买书

原题链接（CQBZOJ）

为了进一步提高编程能力，编程社的 $2n$ 个同学决定去购买《信息学奥赛一本通》，书的价格为 $50$ 元。卖书的书店没有零钱找补，但是有一个特殊的找零装置，放入这个装置的钱只能从最上面的一张拿。其中，$n$ 个同学手中仅有一张 $50$ 元，另外 $n$ 个同学手中仅有一张 $100$ 元。请问一共有多少种排队方案使得所有的同学都可以买到书？$(1\leq n\leq100)$

这道题的关键是：如何看出这是一道卡塔兰。

样例+打表？显然不是。

首先，不难发现，不管我们遍历到哪个位置，这个位置和他前面的位置中，$50$ 元的数量必须比 $100$ 多或相等。可以看出：第一个人必须拿 $50$。

我们在 $2-2n$ 这个区域中随机选一个人，编号为 $i$（不管他拿的是什么钱）。

如果前 $i$ 个人可以做到拿 $50$ 的数量 $\ge$ 拿 $100$ 的数量，那么这种情况就可以算一种正确答案。

而我们从第二个人开始，一直选到第 $2n$ 个人，就是所有的情况。

我们把这 $2n$ 个人分成了 $3$ 个部分，这不就是卡塔兰数吗？

代码需要高精度，大家可以自行复制板子：）。

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
string a[10005];
string add(string a1,string b1){
    int a[10005]={},b[10005]={},c[10005]={};
    string c1;
    int lena=a1.size();
    int lenb=b1.size(); 
    for(int i=0;i<lena;i++) a[lena-i]=a1[i]-'0';
    for(int i=0;i<lenb;i++) b[lenb-i]=b1[i]-'0';
    int lenc=1;
    while(lenc<=lena||lenc<=lenb){
        c[lenc]+=a[lenc]+b[lenc];
        c[lenc+1]=c[lenc]/10;
        c[lenc]%=10;
        lenc++; 
    } 
    while(!c[lenc]) lenc--;
    while(lenc>=1) c1+=c[lenc--]+'0';
    return c1;
}
string mul(string a1,string b1){
    int a[10005]={},b[10005]={},c[10005]={};
    if(a1=="0"||b1=="0") return "0";
    string c1;
    int lena=a1.size();
    int lenb=b1.size();
    for(int i=0;i<lena;i++)	a[lena-i]=a1[i]-'0';
    for(int i=0;i<lenb;i++) b[lenb-i]=b1[i]-'0';
    int lenc;
    for(int i=1;i<=lena;i++){
        for(int j=1;j<=lenb;j++){
            lenc=i+j-1;
            c[lenc]+=a[i]*b[j];
            c[lenc+1]+=c[lenc]/10;
            c[lenc]%=10;
            lenc++;
        }
    }
    lenc=lena+lenb;
    while(!c[lenc]) lenc--;
    while(lenc>=1) c1+=c[lenc--]+'0';
    return c1;
}
int main(){
    int n;
    scanf("%d",&n);
    a[0]=a[1]="1";
    for(int i=2;i<=n;i++){ // 注意这个地方还是和板子略微有一些区别，至于为什么，请读者自行思考
        for(int j=1;j<=i;j++){
            a[i]=add(a[i],mul(a[j-1],a[i-j]));
        }
    }
    cout<<a[n];
    return 0;
}

5.第二类 Stirling 数

这是个二维递推的模型，也就是说，有两个值在影响结果。第二类 Stirling 数的本质是排列组合（个人理解），题目没有固定的解题公式，但是会有非常紧密的联系，大家可以看看下面的三个例子。

例题1-合理放球

原题链接（CQBZOJ）

$n$ 个各不相同球放入 $m$ 个相同的盒子里，球全部放完后，要求最后没有空盒，求不同的放法总数。（$0 < n,m\leq 20$）

我们可以用一个二维数组存放答案。然后假如说我们要把$i$个球放在$j$个盒子里，那么有三种特殊情况：

$i=1$：因为题目要求顺序不算，所以只有在一个盒子里放。$a_{1,j}=1$；
$j=0$：因为没有盒子，所以没办法放。$a_{i,0}=0$；
$j=1$：因为只有一个盒子，所以只能都放在这个盒子里。$a_{i,1}=1$。

还有三种普通情况：

$i<j$

这种一个就不用说了吧，这种情况肯定是没有了（因为不能有空盒子）。$a_{i,j}=0$；

注意：上面的 $i=1$ 如果这这里满足条件的话也要变成 $0$，所以特殊情况和普通情况需要分开判断。
也就是说这里不能再用 else if 了。

$i=j$

这种情况也很简单，因为不能有空盒子，所以只能每个盒子放一个球。$a_{i_j}=1$；

$i>j$

本题考点。

首先我们分析一下有 $i$ 个球分到 $j$ 个盒子里的情况，可以分析出来两种变成这样的方式：

先把 $i-1$ 个球放到 $j$ 个盒子里面，再往里面加一个球；
先把 $i-1$ 个球放到 $j-1$ 个盒子里面，然后再加一个装了一个球的盒子。

第一种情况因为不管加在哪个盒子里都可以，所以有 $j$种方法。第二种只有一个方法。

所以递推式为：$a_{i,j}=a-{i-1,j-1}+j\times a_{i-1,j} $

最后加上其他的东西，组合成 AC 代码~（注意开 long long）：

#include<cstdio>
long long a[25][25];
int main(){
    int m,n;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i==1)a[1][j]=1;
            else if(j==0)a[i][0]=0;
            else if(j==1)a[i][1]=1;
            if(i<j)a[i][j]=0;
            else if(i==j)a[i][j]=1;
            else a[i][j]=a[i-1][j-1]+j*a[i-1][j];
        }
    }
    printf("%lld",a[n][m]);
    return 0;
}

例题2-危险物质

有 $n$ 个存放危险物质的坑，坑排列在一条直线，要求有危险物质的两个坑之间至少要有 $m$ 个空坑。对于给定的 $n$ 和 $m$ ，求安全存放危险物质的方案总数 $\text{mod}\ 5000011$ 之后的结果。（$1\le m\le n\le 10^5$）

这也是有两个数字会影响结果，但是~~你就算是看看数据范围也可以发现~~这道题只需要一个一维数组就够了。

首先我们需要 $n$ 个排成一列的坑：

然后我们看向最后一个坑，它有填与不填两种情况。

如果不填的话，那么前面的坑就可以~~为所欲为~~，只要放置方法合理就行了。

但是如果填呢？

往最后的坑放危险物质

那么这个坑前面的 $m$ 个坑就不能填了，只有往前到第 $n-m-1$ 个坑的时候才可以随便填。

所以递推式为：$a_i=a_{i-1}+a_{i-m-1}$

（批注：前面那部分表示此坑不填，后面那部分表示此坑要填）

接下来我们要注意一下递推的另一个条件，也就是最简单的情况。

现在 $m$ 不知道，那么我们怎么得出最简单的情况呢？

可以发现，如果 $n$ 小于 $m+2$ 的话，那么最多只能填一个或者不填，也就是 $n+1$ 种情况，所以我们可以用循环来解决这个问题。

AC 代码如下：

#include<cstdio>
int a[100005]={1,2};
int main(){
    int m,n;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        if(i<m+2)a[i]=i+1;
        else a[i]=(a[i-1]+a[i-m-1])%5000011;
    }
    printf("%d",a[n]);
    return 0;
}

例题3-核电站

一个核电站有 $N$ 个放核物质的坑，坑排列在一条直线上。如果连续 $M$ 个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。对于给定的 $N$ 和 $M$，求不发生爆炸的放置核物质的方案总数。（$2≤N≤50,2≤M≤5$）

方法类似上面两道题的融合，一共有三种特殊的情况：

如果坑的个数小于不能连续的个数，直接随便放，就是$2^n$；
如果坑的个数等于不能连续的个数，就只有全放一种不行，为$2^n-1$;
如果坑的个数大于不能连续的个数，那就把它分成两个部分看，放和不放。不放就随便，放的话需要让前面连续 $m+1-1$ 个坑不能连续放（因为前面的有最后一个坑放的可能性所以要 $+1$）。

最后算出来为：

$a_i=2\times a_{i-1}$
$a_i=2\times a_{i-1}-1$
$2\times a_{i-1}-a_{i-m-1}$

往循环里一套 AC 代码就出来了。

#include<cstdio>
long long a[55]={1};
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        if(i>m)a[i]=2*a[i-1]-a[i-m-1];
        else if(i==m)a[i]=2*a[i-1]-1;
        else a[i]=2*a[i-1];
    }
    printf("%lld",a[n]);
    return 0;
}

递归的优化——记忆化递归

你们还记得那个 $80$ 分的斐波那契数列吗？~~要是不记得了可以去前面再看看。~~为什么它是 $80$ 分呢？

因为它超时了……~~（废话）~~

TLE

那么怎么解决这个问题呢？

~~用递推就可以了( •̀ ω •́ )y~~

~~说得好像有道理……~~不过这并不妨碍我们介绍另一种方法，就是记忆化递归。(●ˇ∀ˇ●)

记忆化递归是一种典型的以空间换取时间的优化。我们用一个数组储存每一种情况的值，如果我们以后再调用到这个值我们就直接调用，不需要计算了。

除了斐波那契数列，我们还有另外一个记忆化的题目：

例题-递归函数

对于一个递归函数$w(a, b, c)$。

如果$a <= 0\ or\ b <= 0\ or\ c <= 0$就返回值 $1$。

如果$a > 20\ or\ b > 20\ or\ c > 20$就返回 $W(20,20,20)$。

如果 $a < b$ 并且 $b < c$ 就返回 $w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)$，

其它别的情况就返回

$w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)$。

这是个简单的递归函数，但实现起来可能会有些问题。

$|a|, |b|, |c| < 30$

这道题很简单，照着他的写就可以了，主要还是记忆化。

我们定义一个三维数组来存储解（ll 指long long）：

1	ll s[35][35][35];

然后每次递归之前都判断一下这个值是不是已经算过了，如果算过了就直接返回：

1	if(s[x][y][z]!=0)return s[x][y][z];

如果没有算过，那么我们算完了之后要把这个值存到数组里（一个例子）：

1	if(x<y&&y<z)return s[x][y][z]=w(x,y,z-1)+w(x,y-1,z-1)-w(x,y-1,z);

这样我们的代码就轻轻松松的 AC 了：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,s[35][35][35];
ll w(ll x,ll y,ll z){
    if(x<=0||y<=0||z<=0)return 1;
    if(x>20||y>20||z>20)return w(20,20,20);
    if(s[x][y][z]!=0)return s[x][y][z];
    if(x<y&&y<z)return s[x][y][z]=w(x,y,z-1)+w(x,y-1,z-1)-w(x,y-1,z);
    return s[x][y][z]=w(x-1,y,z)+w(x-1,y-1,z)+w(x-1,y,z-1)-w(x-1,y-1,z-1);
}
int main(){
    while(scanf("%lld %lld %lld",&a,&b,&c)){
        if(a==-1&&b==-1&&c==-1)return 0;
        printf("w(%lld,%lld,%lld)=%lld\n",a,b,c,w(a,b,c));
    }
    return 0;
}