javascript 递归
概念
在程序中函数直接或间接调用自己，然后跳出结构，返回结果
递归的步骤(技巧)
- 假设递归函数已经写好
- 寻找递推关系
- 将递推关系的结构转换为递归体
- 将临界条件加入到递归体中
示例
求 1+2+3+3+...n 的和。
二逼青年：
首数加位数 ，乘以个数除以 2
function sum(n) {
return ((1 + n) * n) / 2;
}
console.log(sum(100)); //5050
普通青年： 写个循环
function sum(n) {
let result = n;
while (n-- > 0) {
result += n;
}
return result;
}
console.log(sum(100)); //5050
文艺青年： 有规律的序数运算，所以用递归
/***
* 假设递归函数已经写好为sum,既sum(100),就是求1-100的和
* 寻找递推关系: 就是 n 与 n-1 ,或 n-2 之间的关系，sum(n) == sum(n-1) + n, 前面的数字（n-1）之和和sun(n-1)加上本身n
*/
function sum(n) {
return n == 1 ? 1 : sum(n - 1) + n; //n=1的时候跳出
}
console.log(sum(100)); //5050
求 1+3+5+7+9+...(2n-1)第 n 项的结果和前 n 项和
二逼青年：
用公式值为 n 的平方
function sum(n) {
return n * n;
}
console.log(sum(5)); //25 =1+3+5+7+9
普通青年： 写个循环
function sum(n) {
let result = 0;
while (2 * n - 1 >= 1) {
result += 2 * n - 1;
n -= 1;
}
return result;
}
console.log(sum(5)); //25
文艺青年： 有规律的序数运算，所以用递归
/***
* 假设递归函数已经写好为sum,既sum(100),就是求1-（2n-1）的和
* 寻找递推关系: 就是 n 与 2n-1 之间的关系，sum(n) == sum(n-1) + (2n-1)
*/
function sum(n) {
return n == 1 ? 1 : sum(n - 1) + (2 * n - 1); //n=1的时候跳出
}
console.log(sum(5)); //25
求 2+4+6+8+10+...2n 第 n 项的结果和前 n 项和
二逼青年：
用公式值为 n(n+1)
function sum(n) {
return n * (n + 1);
}
console.log(sum(5)); //30 =2+4+6+8+10
普通青年： 写个循环
function sum(n) {
let result = 0;
while (2 * n > 0) {
result += 2 * n;
n -= 1;
}
return result;
}
console.log(sum(5)); //30
文艺青年： 有规律的序数运算，所以用递归
/***
* 假设递归函数已经写好为sum,既sum(100),就是求1- 2n的和
* 寻找递推关系: 就是 n 与 2n 之间的关系，sum(n) == sum(n-1) + 2n
*/
function sum(n) {
return n == 0 ? 0 : sum(n - 1) + 2 * n; //n=0的时候跳出
}
console.log(sum(5)); //30
斐波拉契(Fibonacci)运算(兔子生兔子的故事)
一对兔子从出生后第 3 个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子对数为多少
产量分析：1， 1， 2， 3， 5， 8， 13， 21 ....n
第 n 个月的兔子总数 = 第 n-1 个月的兔子总数 + 第 n-2 个月的兔子总数
问题： 求任意月兔子的总数
二逼青年：
没公式，不会算，读书少，别骗我
普通青年： 循环大法好
var sum = function (n) {
var a1 = 1,
a2 = 1,
a3 = 0;
if (n <= 2) {
return 1;
}
for (var i = 0; i < n - 1; i++) {
a3 = a1 + a2;
a1 = a2;
a2 = a3;
}
return a3;
};
console.log(sum(5)); //8
文艺青年：看我的递归大法吧
有规律的序数运算，所以用递归
/***
* 假设递归函数已经写好为sum,既sum(10),就是第10个月兔子的总数
* 寻找递推关系: 倒数第3个数 = 倒数第二个数(n-1) + 倒数第一个数(n-2)
*/
function sum(n) {
return n <= 2 ? 1 : sum(n - 1) + sum(n - 2); //n<=1的时候跳出
}
console.log(sum(5)); //8
mul 函数
实现一个函数 mul，运算结果可以满足如下结果
1.mul(2)(3).valueOf() //6
2.mul(3)(4)(5)(6).valueOf() //360
二逼青年 & 普通青年
实现 mul(2)(3).valueOf() =>6
function mul(a) {
return function (b) {
let obj = {};
obj.valueOf = function () {
return a * b;
};
return obj;
};
}
console.log(mul(2)(3).valueOf()); //6
实现 mul(3)(4)(5)(6).valueOf() =>360
function mul(a) {
return function (b) {
return function (c) {
return function (d) {
let obj = {};
obj.valueOf = function () {
return a * b * c * d;
};
return obj;
};
};
};
}
console.log(mul(3)(4)(5)(6).valueOf()); //360
文艺青年：看你俩写的太 JB 累了。假如有无限级回调呢，比如 mul(3)(4)(5)(6)....(n).valueOf(), n 等于 100，你不累死啊。
二逼青年 & 普通青年：你就扯吧，有这样的需求吗？
文艺青年：呵呵，没有这样的需求，那就不抬杠了哈，用递归吧，更简单
function mul(x) {
const result = (y) => mul(x * y);
result.valueOf = () => x;
return result;
}
console.log(mul(2)(3).valueOf()); //6
console.log(mul(3)(4)(5)(6).valueOf()); //360
可以看到，递归写法简单优美，省去考虑很多边界条件的时间。当然，递归算法会保存很多的临时数据，类似于堆栈的过程，如果栈深太深，就会造成内存用尽，程序崩溃的现象。Java 为每个线程分配了栈大小，如果栈大小溢出，就会报错，这时候还是选择递推好一点。
上面的例子都是些简单的例子，还需许多例子比如 汉诺塔，细胞分裂，爬楼梯等经典例子。我读书少，没做更深的钻研...
关于递归中的的 arguments.callee
callee 是 arguments 对象的一个属性。它可以用于引用该函数的函数体内当前正在执行的函数。这在函数的名称是未知时很有用，例如在没有名称的函数表达式 (也称为“匿名函数”)内。
早期版本的 JavaScript 不允许使用命名函数表达式，出于这样的原因, 你不能创建一个递归函数表达式
function factorial(n) {
return !(n > 1) ? 1 : factorial(n - 1) * n;
}
[1, 2, 3, 4, 5].map(factorial);
但是
[1, 2, 3, 4, 5].map(function (n) {
return !(n > 1) ? 1 : /* what goes here? */ (n - 1) * n;
});
这个不行。为了解决这个问题， arguments.callee 添加进来了。然后你可以这么做
[1, 2, 3, 4, 5].map(function (n) {
return !(n > 1) ? 1 : arguments.callee(n - 1) * n;
});
然而，这实际上是一个非常糟糕的解决方案，因为这 (以及其它的 arguments, callee, 和 caller 问题) 使得在通常的情况（你可以通过调试一些个别例子去实现它，但即使最好的代码是最理想的，你也没必要去检查调试它）不可能实现内联和尾递归。另外一个主要原因是递归调用会获取到一个不同的 this 值，例如：
var global = this;
var sillyFunction = function (recursed) {
if (!recursed) {
return arguments.callee(true);
}
if (this !== global) {
//this居然不等于global
console.log("This is: " + this);
} else {
alconsole.logert("This is the global");
}
};
sillyFunction();
再例如这道题目：计算 1*2*3*4*5\*....n 的结果，就是阶乘函数
function factorial(num) {
if (num <= 1) {
return 1;
} else {
return num * factorial(num - 1);
}
}
定义阶乘函数一般都要用到递归算法；如上面的代码所示，在函数有名字，而且名字以后也不会变的情况下，这样定义没有问题。
但问题是这个函数的执行与函数名 factorial 紧紧耦合在了一起。为了消除这种紧密耦合的现象，可以像下面这样使用 arguments.callee
function factorial(num) {
if (num <= 1) {
return 1;
} else {
return num * arguments.callee(num - 1);
}
}
在这个重写后的 factorial()函数的函数体内，没有再引用函数名 factorial。这样，无论引用函数时使用的是什么名字，都可以保证正常完成递归调用, 如下代码：
function factorial(num) {
if (num <= 1) {
return 1;
} else {
return num * arguments.callee(num - 1);
}
}
var test = factorial;
console.log(test(5)); //120
factorial = function () {
return 0;
};
console.log(test(5)); // 120 如果没有使用arguments.callee，将返回0,因为factorial 在外部被重新定义了
在此，变量 trueFactorial 获得了 factorial 的值，实际上是在另一个位置上保存了一个函数的指针。然后，我们又将一个简单地返回 0 的函数赋值给 factorial 变量。如果像原来的 factorial() 那样不使用 arguments.callee，调用 trueFactorial()就会返回 0。可是，在解除了函数体内的代码与函数名的耦合状态之后，trueFactorial()仍然能够正常地计算阶乘；至于factorial()，它现在只是一个返回 0 的函数。
现在已经不推荐使用 arguments.callee()；
原因：访问 arguments 是个很昂贵的操作，因为它是个很大的对象，每次递归调用时都需要重新创建。影响现代浏览器的性能，还会影响闭包。
那不能用咋办呢？记得有到面试题是这样的，接受参数 n=5，不用 for 循环输出数组【1,2,3,4,5】
这是用递归的思路，配合 arguments.callee，代码如下
function print(n) {
var arr = [];
return (function () {
arr.unshift(n);
n--;
if (n > 0) {
arguments.callee();
}
return arr;
})();
}
print(5); // [1,2,3,4,5]
用 setTimeout 实现 setInterval
function say() {
//something
setTimeout(say, 200);
}
setTimeout(say, 200);
// or
function say() {
//something
setTimeout(arguments.callee, 200);
}
setTimeout(say, 200);
没有替代方案的 arguments.callee
下面的例子是没有可以替代arguments.callee 的方案的，因此弃用它时会产生一个 BUG (参看 bug 725398):
function createPerson(sIdentity) {
var oPerson = new Function("alert(arguments.callee.identity);");
oPerson.identity = sIdentity;
return oPerson;
}
var john = createPerson("John Smith");
john();
利用命名函数表达式也可以实现上述例子的同样效果
function createPerson(identity) {
function Person() {
console.log(Person.identity);
}
Person.identity = identity;
return Person;
}
var john = createPerson("John Smith");
john(); //John Smith
[完]
我，秦始皇，打钱！
