C++递归与暴力枚举

1.递归#

递归（Recursion）：一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法

在C++中，除main函数以外的函数均可调用自身（在C语言中main函数的递归是被允许的，C++标准中不允许这样，但部分编译器（g++，Visual C++等）为兼容C语言仍然允许main函数递归），这种操作称为递归。

1.1 递归的应用#

看如下问题

输入长度 $l(0<l\leq129,l=2^n+1,n\in N^*)$ ，输出以下图形

|                                                               |
|                               |                               |
|               |               |               |               |
|       |       |       |       |       |       |       |       |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
\\l==65

对于以上问题，不难看到，除第一行外，每一行都在前一行的基础上把段空白的中点填上了'|'直到没有空白，即到达了第 $log\_2(l-1)$ 行或填了 $log\_2(l-1)$ 次

于是，我们可以对分别第 $n(n\in[0,log_2(l-1)])$ 行进行递归，每次递归把对应区间中点填上'|'，分别递归n层，有如下代码

#include<iostream>
#include<cmath>
using namespace std;

char chs[130];

void subdivide(int,int,int);
int main()
{
    int l;
    cin >> l;
    int n = log2(l-1);
    for(int i = 0;i < l;i ++) chs[i]=' ';
    chs[0]='|';
    chs[l-1]='|';
    chs[l]='\0';
    for(int i = 0;i <= n;i ++)
    {
            subdivide(0,l-1,i);
            cout << chs << endl;
    }
}

void subdivide(int beg,int end,int num)
{
    if(!num) return;
    int mid = (beg+end)/2;
    chs[mid]='|';
    subdivide(beg,mid,num-1);
    subdivide(mid,end,num-1);
}

在以上问题中，我们把一个大的问题（绘制一个图形），难以解决的问题拆分成一个小的，相对易于解决的问题（分别绘制两边的图形），然后再分，直到分解为一个可以解决的问题（num==1时，问题变为在区间中点绘制'|'），这就是递归。

1.2 递归思想及递推#

用上一节结尾的方法考虑以下问题：

P1255 数楼梯
楼梯有 $N$ 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。

分析可得，上到N阶有两种方法，从N-1阶上或N-2阶上，而且上到1阶只有一种方法，上到2阶有两种方法，那么我们就可以把N阶这样的问题分解为N-1阶和N-2阶这样的小问题，进而分解为1阶和2阶这样可以解决的问题

有以下递归式

$ans(N)=\begin{cases} ans(N-1)+ans(N-2),N>2 \\ 2,N=2 \\ 1,N=1 \end{cases}$

我们把从1到N每一阶的走法数量称为该问题的一个状态，那么这些状态共同组成了这个问题状态空间，而第一阶和第二阶的走法数量是我们已知的，那么这两个状态就是这个问题的问题边界，递归的过程就是以原问题为起点尝试寻找把状态空间缩小到已知的问题边界的路线,再通过该路线反向回溯的遍历方式

以上问题可使用以下代码描述

#include<iostream>

long long ans(int);

int main()
{
    int n;
    std::cin >> n;
    std::cout << ans(n);
    return 0;
}

long long ans(int n)
{
    if(n <= 2) return n;
    return ans(n-1)+ans(n-2);
}

显然，该程序遍历了所有从N到1和到2的路线，其时间复杂度为 $O(n[(\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n])$ ，当 $N=5000$ 时，这个数字已经达到了 $10^{1063}$ 级别，时间绝对无法通过要求

经分析，程序主要问题在于不同的 $n$ 对应 $n-1$ $n-2$ 会重复，即遍历每条路线的过程中都会求解路线中的每个状态，存在大量重复，可以加入去重

#include<iostream>
#include<cstring>

long long ans(int);

long long sta[5005];

int main()
{
    memset(sta,0,sizeof(sta));
    int n;
    std::cin >> n;
    std::cout << ans(n);
    return 0;
}

long long ans(int n)
{
    if(sta[n]) return sta[n];
    if(n <= 2) return n;
    return sta[n]=ans(n-1)+ans(n-2);
}

理论上来说，该程序在遇到已经求解过的状态后会直接返回值，时间复杂度为 $O(n)$ 可以通过，但当 $n=5000$ 时答案在 $10^{1059}$ 数量级，long long也存不下，需要使用高精度，此处不再赘述

我们换一个角度

如果我们从一开始就从1阶，2阶推出3阶、4阶直到N阶，是否就可以从根源上避免重复？即从问题边界向原问题正向拓展，我们把这样的方法叫做递推

#include<iostream>

long long ans[5005];

int main()
{
    ans[1]=1;
    ans[2]=2;
    int n;
    std::cin >> n;
    for(int i = 3;i <= n;i ++)
    {
        ans[i]=ans[i-1]+ans[i-2];
    }
    std::cout << ans[n];
    return 0;
}

不难看出，递推就是从问题边界正向推导到原问题，而递归就是从原问题反向归纳到问题边界，最后利用函数回溯来回到原问题解决问题

整体来说，递推无论从代码复杂度还是逻辑思维的方面都优于递归，但是当遇到问题边界不明了，难以使用递推，或者存在多个与原问题相似的状态空间，这时判断是否达到原问题，以及达不到原问题的尝试都会浪费大量时间，这时递归就会比较好用；同理，当存在多个与问题边界类似的状态，原问题不明了的时候也会出现递推优于递归。而往往大部分问题只能选择其中之一，如第一个问题就难以使用递推，这时就要我们作出判断。

例题1 P1706 全排列问题
例题2 P1760 通天之汉诺塔
例题3 P1044 栈
例题4 P2660 zzc种田
例题5 P2799 国王的魔镜

1.3 递归的底层原理#

以下代码

int fun(int);

int main()
{
    int i = 12;
    int j = fun(14);
    return 0;
}

int fun(int i)
{
    return i++;
}

经过编译

g++ -S ./t.cpp

产生了如下汇编助记符文件

_main:
    pushl   %ebp            #将EBP压入栈
    movl    %esp, %ebp      #将ESP移到EBP
    subl    $32, %esp       #ESP减32
    movl    $12, 28(%esp)   #将12保存在ESP加28对应的内存地址（以字节为单位）
    movl    $14, (%esp)     #将14保存在ESP对应内存地址
    call    __Z3funi        #将EIP程序计数器的值压入栈（占8字节），将__Z3funi的地址保存在EIP
    movl    %eax, 24(%esp)  #将EAX寄存器的值移到ESP加24对应的内存地址
    movl    $0, %eax        #将0保存在EAX
    leave                   #弹出栈帧
    ret                     #弹出栈顶，并将栈顶的值保存到EIP，结束程序
__Z3funi:
    pushl   %ebp            #将EBP压入栈
    movl    %esp, %ebp      #将ESP移到EBP
    movl    8(%ebp), %eax   #将EBP加8对应的内存地址的值移到EAX
    leal    (%eax), %edx    #将EAX的值加1保存在EDX
    movl    %edx, 8(%ebp)   #将EDX移到ESP加8对应的内存地址
    popl    %ebp            #弹出栈顶，并将栈顶的值保存到EBP，实现弹出栈帧
    ret                     #弹出栈顶，并将栈顶的值保存到EIP，结束函数
#省略伪指令及部分不相关指令

从中可以看出，在调用函数fun（编译后为__Z3funi）后，程序直接将EBP基址寄存器压入栈，将ESP栈指针寄存器的值设为新的EBP，这将使原函数栈帧得到保留，所有数据仍然存在栈中

在递归中，如果一个递归层数过多，就会导致栈空间过大，而一般的编译器对栈空间的大小是有严格限制的，一旦超出便会导致运行时异常（Runtime Exception）程序将直接退出，后果不堪设想

该问题的解决方法是尽量避免过大的递归，函数调用中避免传递大型复合数据结构，将大型递归转换为循环等

2.暴力枚举#

一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数

暴力枚举指列举一个问题所有可能从而得出答案的方法

暴力枚举在程序设计往往是最有效而最低效的方法，往往能在正式比赛中获得一部分分数

2.1 简单枚举#

看如下问题

P2089 烤鸡
猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10 种配料（芥末、孜然等），每种配料可以放 1 到 3 克，任意烤鸡的美味程度为所有配料质量之和。
现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 10 种配料的所有搭配方案。

可以看到这题就是让我们在1,2,3中挑出10个数使其和为n，这个数据量并不算大可以直接用一个嵌套循环解决

#include<iostream>

using namespace std;

int ans[60000][10];

int main()
{
    int n;
    cin >> n;
    if(n<10||n>30)
    {
        cout << 0;
        return 0;
    }
    int sum = 0;
    for(int a = 1;a <= 3;a ++)
        for(int b = 1;b <= 3;b ++)
            for(int c = 1;c <= 3;c ++)
                for(int d = 1;d <= 3;d ++)
                    for(int e = 1;e <= 3;e ++)
                        for(int f = 1;f <= 3;f ++)
                            for(int g = 1;g <= 3;g ++)
                                for(int h = 1;h <= 3;h ++)
                                    for(int i = 1;i <= 3;i ++)
                                        for(int j = 1;j <= 3;j ++)
                                        {
                                            if(a+b+c+d+e+f+g+h+i+j==n)
                                            {
                                                ans[sum][0]=a;
                                                ans[sum][1]=b;
                                                ans[sum][2]=c;
                                                ans[sum][3]=d;
                                                ans[sum][4]=e;
                                                ans[sum][5]=f;
                                                ans[sum][6]=g;
                                                ans[sum][7]=h;
                                                ans[sum][8]=i;
                                                ans[sum][9]=j;
                                                sum++;
                                            }
                                        }
                                        cout << sum << endl;
                                        for(int i = 0;i < sum;i ++)
                                            cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << " " << ans[i][4] << " " << ans[i][5] << " " << ans[i][6] << " " << ans[i][7] << " " << ans[i][8] << " " << ans[i][9] << endl;
                                        return 0;
}

这也就是最原始的暴力枚举：枚举每一种情况，判断符不符合答案，但是答案实际情况往往不会这么理想

P2241 统计方形
有一个 $n \times m$ 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

如果暴力枚举，最先想到的自然是枚举两个点确定一个矩形，此时时间复杂度为 $O(n^2m^2)$ ，在本题显然无法通过

我们可以换一种枚举策略

事实上当我们给出一个点后，以该点为端点的矩形数量都可以通过数学计算得出：对于点 $(x,y)$ ，以其为端点的矩形数量恰好是 $mn$ （棋盘上除了它所在行和所在列以外的点数，点数总共为 $(m+1)(n+1)=mn+m+n+1$ ， $(m+1)(n+1)-(m+1)-(n+1)+1=mn$ ）而正方形数量恰好是以其为中心的两条斜直线上点长度，可用 $min(x,y)+min(n-x,y)+min(x,m-y)+min(n-x,m-y)$ 计算，矩形数减掉正方形数即为长方形数

#include<iostream>
#include<cmath>

using namespace std;

int main()
{
    long long n,m,a=0,b=0;
    cin >> n >> m;
    for(long long x = 0; x<= n;x ++)
        for(long long y = 0; y <= m;y ++)
        {
            long long sq = min(x,y)+min(n-x,y)+min(x,m-y)+min(n-x,m-y);
            b+=sq;
            a+=m*n;
            a-=sq;
        }
    a/=4;
    b/=4;
    cout << b << " " << a;
    return 0;
}

用该方法枚举出的结果会出现同一个矩形枚举4个端点的过程中枚举了4遍，所以结果要除以4

如何免去这个重复的枚举呢

我们可以只枚举右下角的端点，那么对于每个点我们就只用考虑左上的矩形了

#include<iostream>
#include<cmath>

using namespace std;

int main()
{
    long long n,m,a=0,b=0;
    cin >> n >> m;
    for(long long x = 0; x<= n;x ++)
        for(long long y = 0; y <= m;y ++)
        {
            long long sq = min(x,y);
            b+=sq;
            a+=x*y;
            a-=sq;
        }
    cout << b << " " << a;
    return 0;
}

如果改用边长来枚举，那么这个算法还能继续优化，此处不再赘述

综上所述，从不同角度枚举往往能带来不同的枚举量，如何选择枚举的角度和如何减少枚举量是暴力枚举问题最核心的问题

2.2 子集枚举#

P1157 组合的输出
排列与组合是常用的数学方法，其中组合就是从 $n$ 个元素中抽出 $r$ 个元素（不分顺序且 $r \\\\le n$ ），我们可以简单地将 $n$ 个元素理解为自然数 $1,2,\\\\dots,n$ ，从中任取 $r$ 个数。
现要求你输出所有组合。

如何枚举一个集合中的元素？

对于某个全集的一个子集，那么全集中的每一个元素只有两种状态：在这个子集中或者不在这个子集中，利用这一特性，我们就可以用一个二进制数字表示一个集合的子集。在这个数字中，每位对应全集中的一个元素，0表示不在子集中，1表示在子集中，那么一个有 $n$ 个元素的集合的所有子集就可以用数字 $0$ 到 $2^n-1$ 表示，可以以此实现子集枚举

注意：C++中的位运算#

C++中的整数采用补码表示法，最高位0表示非负数，1表示负数，非负数表示值与实际值是一样的，而负数则需要在实际值上减掉 $2^n$ 来表示，对于4位的数字使用补码表示法有以下几个示例

0000:0(0)
0001:1(1)
1111:-1(15)
1110:-2(14)
1000:-8(8)
0111:7(7)
//二进制数:补码表示数(实际值)

C++中存在以下几个常用位运算符

& //按位与
| //按位或
^ //按位异或
<< //左移位
>> //右移位

其中&、|就是对每一位进行与、或

&按位与存在以下性质：一个操作数为1时保持另一个数不变，一个操作数为0时返回0，故常用在掩码运算、二进制下的数位分离

^按位异或(也写作XOR)存在以下性质：两个操作数相同则输出0，不同则输出1（按位）

当一个操作数为1时，相当于对另一个操作数取反，当一个操作数为0时，相当于保持另一个操作数不变

(A << n) == A*pow(2,n)

(1 << n) == pow(2,n)

(A >> n) == A/pow(2,n)

以上所有均不处理溢出，这也意味着左移位导致符号位改变时会引发很多不必要的麻烦

回到子集枚举，由位运算的性质，我们可以得出以下式子

$A \cup B$ A|B

$A\cap B$ A&B

$C^A_B$ A^B

$A \in B$ (B>>(n-1))&1

$A \subset B$ ((A|B)==B)&&((A&B)==A)

回到题目本身

题目要求我们字典序输出，那么我们只要从 $2^n -1$ 反向枚举到 $0$ ，再让最高位表示1就行了

代码如下

#include<cstdio>

int n,r;
int ans[30];

int main()
{
    scanf("%d %d",&n,&r);
    for(int set = (1<<n)-1;set>=0;set--)
    {
        int index = 0;
        for(int i = 1;i <= n;i++)
        {
            if((set>>(n-i))&1)ans[index++]=i;
        }
        if(index == r)
        {
            for(int i = 0;i < r;i ++) printf("%3d",ans[i]);
            printf("%c",'');
        }
    }
}

2.3 排列枚举#

排列枚举，即枚举所有元素的排列，对于这样的组合问题，我们有一个简便方法

STL中的algorithm头文件中提供了两个函数next_permutation(begin,end)和prev_permutation(begin,end)分别提供区间 $\[begin,end)$ 中元素的下一个排列和上一个排列（按字典序），当没有可用排列时返回0

P1706 全排列问题

本题已经用递归做过一次，但是用现在的排列枚举会更简单

由于 $1,2,3,\dots,n$ 的排列就是字典序最小的排列，故从这里开始循环调用next_permutation(begin,end)就可以保证枚举所有排列

#include<cstdio>
#include<algorithm>

int main()
{
    int ans[10];
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n; i++)
    {
        ans[i]=i+1;
    }
    do
    {
        for(int i = 0;i < n; i++)
            printf("%5d",ans[i]);
        printf("%c",'');
    }while(std::next_permutation(ans,ans+n));
    return 0;
}

例题1 P1088 火星人
例题2 P1014 Cantor表
例题3 P1469 找筷子