【算法】递归总结：循环与递归的区别？递归与深搜的关系？

递归算法总结：搞清楚递归与循环、深搜之间的联系。

1.递归 与 循环(迭代)？

所谓 递归，就是函数自己调用自己
所谓 循环，就是做重复代码处理

在某一层面上，可以认为递归就是循环的另一种写法，循环也是递归的另一种写法。
两者都有个关键的共同点：重复子问题

下面我以遍历vector举例：现在有一个数组，请分别用循环和递归的两种不同方式去对他们进行遍历。

#include 
#include
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