先附上原题：
给定两个数n和k，写出所有k个数字的组合，数值范围从1~n，并且每一个组合中的数字不得重复。
这道题目首先想到的是利用多重循环，比如说在k=2的情况下，那代码应该是这样的，有两重循环：
for ( i = 1 to n)
for (j = i + 1 to n)
但是如果说k=10呢，难道也要写10重循环？更何况k本身是一个未知的变量。
我们同样以原题上的例子为例，假如第一个数取1，那第二个数就可以取2，3或者4；如果第一个数取2，那第二个就能取3或者4……脑海中是不是马上浮现出一颗树？大致应该是这样一幅图：
首先我们从根节点出发到达节点1，然后是节点2，遍历的过程中将其放入一个数组中，当数组中的元素个数到达k时，将这一组合保存。然后从节点2返回到节点1，将刚才数组中的最后一个元素清除掉，再经过节点3，将3再放入数组，此时数组中的元素又到了k，我们再将它保存。相信后面的过程不用我多说了，这其实就是一个对树的深度优先遍历。
在实际的代码中，我们没必要真的去建树。好了，talk is cheap，直接来看代码吧
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result; //保存最后的结果
vector<int> v; //存放每一种组合
dfs(1, n, k, v, result);
return result;
}
/*
* begin 需要遍历的起始位置，比如说根节点下就是1，节点1下的起始位置就是2
* end 遍历的终止位置，由题目给出，也就是变量n
* k 每种组合的数字个数
* v 保存每一种组合
* result 保存最终的结果
*/
void dfs(int begin, int end, int k, vector<int> &v, vector<vector<int>> &result) {
if (k != 0) {
for (int i = begin; i <= end; i++) {
if (end - i + 1 < k) { //如果起始位置到终止位置数字的个数小于当前组合还需要的数字个数，
break; //直接跳出循环，这样可以减少没必要的迭代，以上图为例，根节点下的
} //节点4没有子节点，所以没必要对它进行遍历
v.push_back(i);
dfs(i + 1, end, k - 1, v, result); //下一层遍历的开始位置从i + 1开始，并将k减去1
v.pop_back(); //等到栈返回时，将最后一个元素弹出
}
} else {
result.push_back(v); //当元素个数到达k个时，我们将其保存
}
}
};
在实际问题中，循环和递归经常可以互相代替，比如说二叉树的遍历，你同样可以自己定义一个栈，然后用循环来进行遍历。虽然递归会带来性能上的损失，但是它所带来的程序可读性，对于这点性能损失是完全值得的。但也不要对递归滥用，比如说在计算斐波那契数列的时候，你可能会这么写：
Fib(int n)
{
if (n <= 1)
return 1;
else
return Fib(n-1) + Fib(n-2);
}
初看起来，这段程序对递归的使用好像很聪明。但实际情况是，这段程序的效率是相当低下的。分析很简单，因为它做了很多重复的计算。如果使用循环，就可以每次迭代时保存前两个数，这或许就是格言“计算任何事情不要超过一次”。
最后这里有一个关于递归和循环的比较：
递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就一定比递归高，递归和循环是两码事，递归带有栈操作，循环则不一定，两个概念不是一个层次，不同场景做不同的尝试。
2.1递归算法：
优点：代码简洁、清晰，并且容易验证正确性。（如果你真的理解了算法的话，否则你更晕）
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。
2.2循环算法：
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。
2.3递归算法和循环算法总结：
1. 一般递归调用可以处理的算法，也通过循环去解决常需要额外的低效处理。
2. 现在的编译器在优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。
3.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成递归往往是好的。（例如：求阶乘的递归实现与循环实现。）
网友评论