递归和递推

请注意,本文编写于 127 天前,最后修改于 127 天前,其中某些信息可能已经过时。

递归和递推实则是两个互逆的过程。

递归从问题本身出发,寻找问题相似的部分,利用分而治之或简而治之的思想,将庞大的问题划分为小问题,再通过边界条件的限定,得出答案。代码一般比较简洁,但阅读起来确实思维的逆向过程,可能会不容易理解,且遇到输入规模很大的问题,容易因为函数的多次调用导致堆栈溢出。

递推从简单的实例出发,发掘小问题之间的规律,再扩展延伸满足整个问题的条件,进而求解。代码符合人的正向思考过程,易于理解,不过循环嵌套显得冗余,相同问题代码量一般要比递归的解法多。

下面通过一些例子一步一步地讲述两种思想的思考过程。

指数型枚举

题目链接

题目是这样的:从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。

其实这是一道高中学排列组合时的一道数学题,想必大家都有印象。当时学习过一个结论,即上述问题的选择方案共有 2^n 种,那么这个结论是怎么来的呢,我当时的数学老师是这样证明的:从 1~n 的每一个数,都有选与不选两种可能,那么对于 n 个数来讲,就有 2 2 …… * 2(共 n 个2相乘) 种可能。

递归的解法也可以这样考虑,所以就有了下面的算法:

#include <iostream>

using namespace std;

int n;

void dfs(int start, int state)
{
    if (start == n)
    {
        for (int i = 0; i < n; i++)
        {
            if (state >> i & 1)
                cout << i +  1 << ' ';
        }
        cout << endl;
        return ;
    }
    
    dfs(start + 1, state);
    dfs(start + 1, state | 1 << start);
    
}

int main() 
{
    cin >> n;
    dfs(0, 0);
    
    return 0;
}

其中核心的函数是 dfs() 第一个参数代表从第几个数开始,第二个参数代表当前的选择情况,使用了一个 int 型的变量来模拟,把它想象成二进制的表示形式,选取第 i 个数,就把它的第 i 位置为 1,等到触发递归边界条件时,就通过 state 将此次的选取情况输出出来。

其中 dfs 递归调用的两句与上述提到的方法相同,分为选取本位和不选取本位的思想递归调用,这也符合递归分而治之的思想。

至于递推的思想,就类似于我们第一次面对这种问题的想法,有规律地一个一个枚举,例如:1, 2, 3, 12, 13, ……

这里依然用 state 的二进制表示形式来记录选取的情况,例如 n = 3,即

000 -> \n
001 -> 1
010 -> 2
100 -> 3
011 -> 1 2
101 -> 1 3
110 -> 2 3
111 -> 1 2 3

这样思路就比较清晰了,列举 n 位二进制的所有情况,再将值为1的位算作选取输出,实现代码如下:

#include <iostream>

using namespace std;

int n;

int main() 
{
    cin >> n;
    for (int i = 0 ; i < 1 << n; i++)
    {
        for (int j = 0; j < n; j++) 
        {
            if (i >> j & 1)
                cout << j + 1 << ' ';
        }
        cout << endl;
    }
    return 0;
}

关于用 state 表示枚举情况这个小技巧,讲的玄乎一点也可以称为状态压缩

组合型枚举

题目链接

这道题是组合数的枚举,也就是数学中的 $A_m^n$,从 m 个数中选取 n 个数的所有情况。

这题不同的地方是选取的元素个数是固定的,即 m,所以我们可以利用这一点来作为递归的边界条件。

代码如下:

#include <iostream>

using namespace std;

int n, m;

void dfs(int u, int sum, int state)
{
    if (sum == m)
    {
        for (int i = 0; i < n; i++)
            if (state >> i & 1)
                cout << i + 1 << ' ';
            cout << endl;
            return;
    }
    if (u == n || sum + n - u < m) return;
    
    dfs(u + 1, sum + 1, state | 1 << u);
    dfs(u + 1, sum, state);
}

int main() 
{
    cin >> n >> m;
    dfs(0, 0, 0);
    
    return 0;
}

排列型枚举

题目链接

这道题与第一题不同的地方也是选取的数目是固定的 n,这样递归分类的方法就不能是选和不选了,而是对每个位置来说,填入的元素是什么。

代码如下:

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> path;

void dfs(int u, int state)
{
    if (u == n)
    {
        for (auto x : path) cout << x << ' ';
        cout << endl;
        return;
    }
    
    for (int i = 0; i < n; i++)
    {
        if (!(state >> i & 1))
        {
            path.push_back(i + 1);
            dfs(u + 1, state | 1 << i);
            path.pop_back();
        }
    }
    
}

int main() 
{
    cin >> n;
    dfs(0, 0);
    return 0;
}

添加新评论