理解递归函数DFS函数的方法

admin管理员组

文章数量:1794759

理解递归函数/DFS函数的方法

对于递归函数或者深搜函数，有时候因为其调用本身的性质所以会难以理解。以如下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