对于递归函数或者深搜函数,有时候因为其调用本身的性质所以会难以理解。以如下dfs函数为例:
void dfs(...){ //外部dfs
if(...) {...}
for(...){
...;
dfs(...); //内部dfs
...;
}
}
要想在遇到深搜问题时很快写出dfs(),只记模板是不行的,需要理解dfs()内部的功能。这里有个常有的误区:为了理解dfs,就去一层层分析堆栈,分析一个一个函数的调用过程、输出结果。最后自己会晕掉。其实递归函数内部调用的函数是自己或者不是自己没什么区别,我们理解它的时候只把这个内部调用的函数当做其他函数即可。
理解dfs的方法:
第一步:准确表达出该dfs()函数的功能,先不去管它是怎么实现的,把它看成一个黑箱子,你要能准确说出它的功能,并且精确到它的参数的变化、输出的结果是什么。
第二步:开始阅读dfs()函数的代码,我们要开始探索dfs()是怎么实现的了。但这时候若遇到内部dfs()调用,就把这个内部dfs()用第一步的功能黑箱代替。这是关键:我们只想知道外部dfs()是怎么实现的,内部dfs()我们不想知道(虽然两者等同,但必须区别对待), 内部dfs()只是一个普通的函数,替换成任何其他 f() 都不会影响它的结构,我们只要知道它在这里的功能就够了!
现在来实践一下,比如我们要求1到N中和为M的所有组合,并且按字典顺序打印出来。dfs()代码如下。
void dfs(int begin, int sum, vector<int>& path) {
if (sum == 0) {
//输出解并且返回
for (int i = 0; i < path.size(); i++) i == 0 ? cout << path[i] : cout << " " << path[i];
cout << endl;
return;
}
//遍历begin之后直到数组末尾n的每一个数
//用i<=sum作为for循环的终止条件,可以起到剪枝的效果
for (int i = begin+1; i <= n&&i <= sum; i++) {
path.push_back(i);
dfs(i, sum - i, path);
path.pop_back();
}
}
理解过程:第一步先说出dfs(begin,sum,path)的功能:找出begin到N中和为sum的所有组合,存入path并且打印。 说出这个功能是不需要它的具体实现的。第二步看函数体,这时候再遇到内部dfs()就用下划线部分代替。
void dfs(int begin, int sum, vector<int>& path) {
if (sum == 0) {
当前path就是解,打印,返回;
}
//遍历后面的所有数字i
for (int i = begin+1; i <= n&&i <= sum; i++) {
把i放入path;
找到i到N间所有和为sum-i的组合并且存入path并打印;
把i从path中删除;
}
}
更多推荐
理解递归函数/DFS函数的方法
发布评论