递归算法总结：搞清楚递归与循环、深搜之间的联系。
1.递归 与 循环(迭代)？
所谓 递归，就是函数自己调用自己
所谓 循环，就是做重复代码处理
在某一层面上，可以认为递归就是循环的另一种写法，循环也是递归的另一种写法。
两者都有个关键的共同点：重复子问题
下面我以遍历vector举例：现在有一个数组，请分别用循环和递归的两种不同方式去对他们进行遍历。
#include <iostream> #include<vector> using namespace std; void dfs(vector<int>& v, int i) { if (i == v.size()) return; cout << v[i++] << " "; dfs(v, i); } int main() { vector<int> v = { 1,2,3,4,5,6,7,8,9 }; //用循环的方式 for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; //用递归的方式 dfs(v,0); cout << endl; return 0; }
结论：我们可以看到，循环和递归在某一层面上是等价的，只不过写法不同而已。
那像二叉树的前序中序后序遍历用循环怎么进行处理呢？因为每个节点在用完之后，后面还可能会用到，所以想要用循环写出来，得借用栈这个数据结构即可。不过写起来很麻烦。
具体参见：【数据结构】树、二叉树与堆（长期维护）
结论：虽然循环与递归可以相互转换，但是有些题适合用递归写，有些题适合用循环写。比如上面我举的vector遍历的例子，一般这种单层面递归就用循环比较合适，而像多叉树遍历这种多方面递归，就适合用递归去写。
2.递归 与 深搜？
深度优先搜索，比如将树按照左、右、中的树顺序进行遍历。
而具体的代码实现，用递归去写是比较方便的。
说白了，递归的展开图与深度优先遍历高度相似。
EOF
