JavaScript之递归
递归基础
- 什么是递归？
在JavaScript程序中，函数直接或间接调用自己。通过某个条件判断跳出结构，得出结果。递归的本质就是一个循环。 - 引用之前在知乎看到的一个对递归的理解。
从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的是从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的是从前有座山。。。
或者
for(let i = 0; i < 1; i--) {
console.log(i);
}
这里可以看出是一个循环了吧，这是一个死循环，没有终止条件。
- 也可以看下面一个例子：
function fn() {
console.log(1);
fn(); // 递归，自己调用自己
}
fn() // 没有终止条件，这个递归就是一个死循环。
// 1
// 1
// 1
// ...
- 看到这应该是基本明白是什么意思了，那看一下下面的递减：
function cut(n) {
if(n === 0) return;
console.log(n);
cut(n - 1);
}
cut(5);
// 5
// 4
// 3
// 2
// 1
- 看出了什么，是不是多了一个判断条件？
if(n === 0) return;这是避免进入死循环，所以使用递归的时候，一定要加上临界条件(或者说是边界条件)，否则就会陷入死循环。
再比如让你求一个1-100的和，你是不是会这样写：
var sum = 0;
for(let i = 1; i <= 100; i++) {
sum += i;
}
console.log(sum) // 5050
那么使用递归呢，该如何去计算1-100的和？
用递归求1-100的和，即sum(100)，我们可以列出公式：
var result = sum(100);
var result = sum(99) + 100;
var result = sum(98) + 100;
var result = sum(97) + 100;
var result = sum(96) + 100;
...
然后我们是不是可以由以上的公式得出一下结果：
var result = sum(n-1) + n;
转成递归结构是不是
function sum(n) {
return sum(n-1) + n;
}
但是按我们上面所说，使用递归的时候，一定要加上临界条件，否则就会陷入死循环。
那在计算1-100的和的临界条件是什么呢？
我们可以这样算：
求100的时候转换为求99；
求99的时候转换为求98；
求98的时候转换为求97；
求97的时候转换为求96；
...
求2的时候转换为求1；
求1的时候转换为求？
所以，这里我们就得加上临界条件啦，即sum(1) = 1;
那么，递归函数是不是：
function sum(n) {
if(n === 1) return 1;
return sum(n-1) + n;
}
sum(100)
// 5050
记得还有一个arguments.callee方法，但是用的比较少了，可以这样
function sum(n) {
if(n === 1) {
return n;
}else {
return n + arguments.callee(n - 1);
}
}
sum(100)
// 5050
-
假设让你分别求奇数偶数的和是多少呢？
比如求奇数和
是不是可以举例子，如1、3、5、7、9、11、13、15、17、19...
第一项是1，第二项是3，第三项是5，
那是不是设fn(n)为第几项(第n项),即sum(n)为前n项之和？
那就可以得出公式：
fn(n) = fn(n-1) + 2;
sum(n) = fn(n) + sum(n - 1);
那么这样是不是可以猜出递归结构了？
function fn(n) {
return fn(n - 1) + 2;
}
function sum(n) {
return fn(n) + sum(n - 1);
}
到了这里，我们是不是忘记了很重要的一点，忘记加上临界条件了，那么他们的临界条件是什么呢？
我们知道，按上面举的例子1、3、5、7、9、11、13、15、17、19...
fn(0)是不是1 ?
fn(1)是不是3 ?
fn(2)是不是5 ?
...
那么最小的是不是fn(0) ?，在正整数中，最小的奇数是不是1，所以这个fn的临界条件就是fn(0) = 1;
既然fn(0)的值都是1了，那sum(0)是不是也是1，所以
临界条件
fn(0) = 1;
sum(0) = 1;
那么就可以得出
function fn(n) {
if(n === 0) return 1;
return fn(n - 1) + 2;
}
function sum(n) {
if(n === 0) return 1;
return fn(n) + sum(n-1);
}
// 计算100以内所有奇数和, 100以内奇数有50个
sum(49) // 0-49
// 2500
那么求偶数和是不是更简单了，只需要改变临界条件就行了。
比如，举个例子，2、4、6、8、10、12、14、16、18、20...
fn(0)是不是2？
fn(1)是不是4？
fn(2)是不是6？
fn(3)是不是8？
...
正整数中，最小的偶数是不是2？，所以fn(0)就是2，对应的sum(0)是不是也是2？
得出的临界条件是不是
fn(0) = 2;
sum(0) = 2;
那么递归函数是不是
function fn(n) {
if(n === 0) return 2;
return fn(n - 1) + 2;
}
function sum(n) {
if(n === 0) return 2;
return fn(n) + sum(n-1);
}
// 计算100以内所有偶数和, 100以内偶数也是50个
sum(49) // 0-49
// 2550
递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量 。递归在很多语言中都很常见，合理的使用，可以帮助我们解决很多问题。
