当前位置:网站首页>递归思想
递归思想
2022-08-04 08:30:00 【小艾菜菜菜】
什么是递归
首先我觉得我们要清楚什么是递归
递归在于不断调用自己的函数,层层深入,直到遇到递归终止条件后层层回溯,其思想与dfs的思想不谋而合;因此,可以使用递归来实现dfs。
递归的进入比较容易理解,但是递归的回溯是在计算机底层执行的,我们无法看到。因此,递归究竟是如何完成的,成为了理解递归的一大难点,也是理解递归的唯一一个难点。
理解递归
让我们来看一下这样一个简单的递归程序:
#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,我们可以看到,它的输出是
我们可以清楚的看到,哪个数字进入了递归,又有哪个数字回溯了。
为什么会产生这样的结果?请看下面这幅图,它解释了递归函数的调用全过程
这样,我们就能理解,为什么首先输出的是Recursive program backtracking — 1了
如果还不是很理解,请看下面的图,我们从u = 0 回退到了u = 1,再直接回退到u = 2,再回退到u = 3
递归程序在回退完成前,return会使得计算机继续依次执行上一层函数调用后的代码。
再结合一道题来进一步理解递归思想的应用过程
全排列
解题思路
如何用dfs 解决全排列问题?
注意: dfs 最重要的是搜索顺序。
对于全排列问题, 以 n = 3为例,可以这样进行搜索:
具体实现过程描述如下:
假设有三个空位,从前往后填数字,每次填一个位置,填的数字不能和前面的一样。
开始的时候,三个空位都是空的:__ __ __
首先填写第一个空位,第一个空位可以填 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
这时候,空位填完,无法继续填数,所以这是一种方案,输出。
剩下的以此类推哦~
代码实现
变量的说明:
用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]; //判断数字是否用过
void dfs(int u)
{
if (n == u) //数字填完,输出
{
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; // 放入空位置
st[i] = true; // 数字备用修改状态
dfs(u + 1); // 填写下一个位置
path[u] = 0; // 回溯之前可以将空位置设置为0
st[i] = false; // 回溯取出i
}
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
总结
个人觉着dfs模板题,推荐完全背下来。递归的思想也要好好的理解并掌握。
最后如果还是不太懂这递归的思想,推荐看这篇博客
边栏推荐
猜你喜欢
『递归』递归概念与典型实例
【NOI模拟赛】纸老虎博弈(博弈论SG函数,长链剖分)
MySQL BIGINT 数据类型
Recommend several methods that can directly translate PDF English documents
1161. Maximum Level Sum of a Binary Tree
【虚幻引擎UE】UE5基于Gltf加载插件实现gltf格式骨骼动画在线/本地导入和切换
【论文笔记】Understanding Long Programming Languages with Structure-Aware Sparse Attention
经典递归回溯问题之——解数独(LeetCode 37)
24.循环神经网络RNN
[STM32] STM32F103 series name and package, memory
随机推荐
Implementation of redis distributed lock
为什么手动启动GBase 8c数据库中GTM节点,起不来。显示“Run cmd failed:scp: /tmp/gtm_gtm1.server: Permission denied”
Thread类的基本使用。
Interpretation of new features | MySQL 8.0 online adjustment REDO
【UE虚幻引擎】UE5实现动态导航样条线绘制
使用单调栈解决接雨水问题——LeetCode 42 接雨水+单调栈说明
第一次用postgreSQL,想装主从,用的12.7 tar.gz版本。安装好后没在 share目录下找到样例配置recovery.conf.sample,是安装方式不对,还是路径不对?
金仓数据库 KDTS 迁移工具使用指南 (4. BS 版使用说明)
Cross-species regulatory sequence activity prediction
智汇华云 | 华云软件定义网络 DCI介绍
阿里云的数据库系统怎么升级更新的www.zgysffm.com怎么加快访问速度?
【论文笔记】Dynamic Convolution: Attention over Convolution Kernels
Distributed Computing MapReduce | Spark Experiment
解决循环依赖import cycle not allowed的最佳解决办法
高等代数_证明_幂等矩阵一定能够相似对角化
从零开始的tensorflow小白使用指北
一天搞定JDBC02:开启事务
leetcode 22.7.31(1)两数之和 (2)整数除法
【NOI模拟赛】纸老虎博弈(博弈论SG函数,长链剖分)
Distributed Computing Experiment 4 Random Signal Analysis System