递归那些事

果然还是想递归能让脑子转起来

上一次写递归还是很久以前在学校写扫雷的时候用到的，因为需要遍历地图，当时自己写的时候用队列写的广度优先搜索（BFS），因为相对于比较费脑的递归，用队列好想的多了，但碍于指导老师的要求还是又用递归写了一遍。再往前的话，就是acm的时候做题用到的了，但也很少，能用循环解决的干嘛要用递归呢（其实更重要的原因是当时对递归真的不是很理解，看别人的代码都不一定能看懂，别说自己写了）。恩，再往前应该就没有了。

好了，来看今天的问题吧

“所有的递归都能用循环实现。”这句话不是我说的，网上赞同的很多，反对的也不少。但就目前我遇到的情况，都能把递归转换成循环，换句话说吧，“我用过的循环基本都能转换成递归”，因为我都是优先用循环，做完之后闲着没事再去琢磨用递归实现。来分析下怎么写一个递归首先，递归要有结束条件，不然就是死循环其次，你想让他循环干甚么最后，返回值应该是什么不看最后一点的话，跟写循环一样，其实真的差不多，下面通过几个问题来理解一下

递归求阶乘先看看用循环怎么做吧求n的阶乘，循环n次，累乘就好了
```
var n = 5;
var sum = 1;
for(var i = n; i > 0; i--){
 sum *= i
}
alert(n+"的阶乘是："+sum);
```
下面是递归首先，求n的阶乘的话，自然是从n一直乘到1，所以结束条件是n>1，其次，当前数乘上他前面一个数的阶乘就是当前数的阶乘最后，每次的返回值都是当前数乘上前一个数的阶乘，当当前数为1的时候，返回值就是1 最后的结果就是这样，想！一定要动脑子想！
```
function deal(n){
 if(n > 1){
     return n * deal(n - 1);
 }
 return 1;
}
```
递归求斐波那契数（第一位和第二位为1，往后的都为前两位的和，1 1 2 3 5 8 13 21 34….）首先，已知第一位和第二位都是1，所以当n为1和2的时候我们都返回1就行了，故结束条件是n>2 其次，公式是：当前项的值为其前两项的和，那就是：f(n) = f(n-1) + f(n-2) 最后，n为1和2的时候我们都返回1，否则返回f(n-1) + f(n-2)

function f(n){
	if(n > 2){
		return f(n-1) + f(n-2);
	} else {
		return 1;
	}
}

递归求组合数（C（M，N）是从M个物品中任选N个的方法，详情点这里）求组合数的公式：C(m, n) = C(m-1, n) + C(m-1, n-1) 这里的m是在公式里下面那个比较大的数，n是比较小的数。当时我自己写完测试的时候给弄反了，怎么弄结果都不对，最后看了下公式，原来是n和m弄反了。直接上代码了，思路跟之前的一样。唯一要注意的就是结束条件，当n的值为0，或者是n等于m的时候，组合数的值为1
```
function deal(m, n){
 if(m && m < n){
     return deal(m-1, n) + deal(m-1, n-1);
 } else {
     return 1;
 }
}
```

果然还是想递归能让脑子转起来

好了，来看今天的问题吧

CATALOG

FEATURED TAGS

FRIENDS