recursive thinking

什么是递归

First of all I think we need to be clear about what recursion is
递归在于不断调用自己的函数,层层深入,直到遇到递归终止条件后层层回溯,其思想与dfs的思想不谋而合;因此,可以使用递归来实现dfs.
递归的进入比较容易理解,但是递归的回溯是在计算机底层执行的,我们无法看到.因此,递归究竟是如何完成的,It has become a major difficulty in understanding recursion,It is also the only difficulty in understanding recursion.

理解递归

让我们来看一下这样一个简单的递归程序：

#include<iostream>
using namespace std;

int n;

void func(int u){
    
    if(u == 0) return;
    cout << "Recursive program goes to the next level --- " << u << endl;
    func(u-1);
    cout << "Recursive program backtracking --- " << u <<endl;
    return;
}
int main(){
    
    cin >> n;
    func(n);
    return 0;
}

输入3,我们可以看到,它的输出是

我们可以清楚的看到,Which number goes into the recursion,Which number backtracks again.
为什么会产生这样的结果？请看下面这幅图,It explains the whole process of calling recursive functions

这样,我们就能理解,Why is it output firstRecursive program backtracking — 1了
如果还不是很理解,请看下面的图,我们从u = 0 回退到了u = 1,Go back directly to u = 2,再回退到u = 3

A recursive program before the rollback is complete,returnIt will make the computer continue to execute the code after the function call of the previous layer in turn.

Combined with a question to further understand the application process of recursive thinking

全排列

解题思路

如何用dfs 解决全排列问题？
注意： dfs 最重要的是搜索顺序.
对于全排列问题, 以 n = 3为例,可以这样进行搜索：

The specific implementation process is described as follows：
假设有三个空位,从前往后填数字,每次填一个位置,The numbers to be filled in cannot be the same as the previous ones.

开始的时候,三个空位都是空的：__ __ __

首先填写第一个空位,第一个空位可以填 1,填写后为：1 __ __

填好第一个空位,填第二个空位,第二个空位可以填 2,填写后为：1 2 __

填好第二个空位,填第三个空位,第三个空位可以填 3,填写后为： 1 2 3

这时候,空位填完,无法继续填数,所以这是一种方案,输出.

然后往后退一步,退到了状态：1 2 __ .剩余第三个空位没有填数.第三个空位上除了填过的 3 ,没有其他数字可以填.

因此再往后退一步,退到了状态：1 __ __.第二个空位上除了填过的 2,还可以填 3.第二个空位上填写 3,填写后为：1 3 __

填好第二个空位,填第三个空位,第三个空位可以填 2,填写后为： 1 3 2

这时候,空位填完,无法继续填数,所以这是一种方案,输出.

然后往后退一步,退到了状态：1 3 __ .剩余第三个空位没有填数.第三个空位上除了填过的 2,没有其他数字可以填.

因此再往后退一步,退到了状态：1 __ __.第二个空位上除了填过的 2,3,没有其他数字可以填.

因此再往后退一步,退到了状态：__ __ __.第一个空位上除了填过的 1,还可以填 2.第一个空位上填写 2,填写后为：2 __ __

填好第一个空位,填第二个空位,第二个空位可以填 1,填写后为：2 1 __

填好第二个空位,填第三个空位,第三个空位可以填 3,填写后为：2 1 3
这时候,空位填完,无法继续填数,所以这是一种方案,输出.

And so on for the rest~

代码实现

变量的说明：
用path 数组保存排列,当排列的长度为 n 时,是一种方案,输出.
用st 数组表示数字是否用过.当st[i]为true 时,i 已经被用过了,st[i] 为 false 时,i 没被用过.
dfs(i) 表示的含义是：在path[i] 处填写数字,然后递归的在下一个位置填写数字.
回溯：第 i 个位置填写某个数字的所有情况都遍历后, 第 i 个位置填写下一个数字.

#include<iostream>

using namespace std;

const int N = 10;
int n;
int path[N]; // 保存序列
bool st[N]; //Determine if the number is used

void dfs(int u)
{
    
    if (n == u)  //Complete the numbers,输出
    {
    
        for (int i = 0; i < n; i++) printf("%d ",path[i]);
             puts(""); 
            return;
    }

      
    for (int i = 1; i <= n; i++)
    {
    
        if (!st[i])
        {
    
            path[u] = i; // Put into empty space
            st[i] = true; // Digital alternate modification status
            dfs(u + 1); // 填写下一个位置
            path[u] = 0; // An empty position can be set to before backtracking0
            st[i] = false; // Backtracking outi
        }
    }
}

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

总结

个人觉着dfs模板题,It is recommended to take it down completely.The idea of ​​recursion should also be well understood and mastered.

Finally, if you still don't understand the idea of ​​recursion,推荐看这篇博客

https://blog.csdn.net/lltqyl/article/details/106604387