Javascript的函数递归
递归是什么？
想个标题已经让我很纠结了，究竟是函数递归还是递归函数？
看了下MDN的说明是：** 函数可以被递归，就是说函数可以调用其本身。**
那递归就是函数的里面再调用自己，从而形成一个循环。
还是在实战才会学得更快，来战吧。
用递归计算阶乘:
function factorial(n){
return (n * factorial(n - 1));
}
这里就是函数里，调用了自己不停的互乘。当运行factorial(5)就不停计算 5*4*3*2...的计算下去，但问题是这没有尽头呀！直到栈溢出抛出 Uncaught RangeError: Maximum call stack size exceeded(…) 也不会有返回值。
这种无尽的递归称为死递归，它和死循环一样恐怖。
所有循环的程序都会有一个退出条件，对于每一个递归的程序，也都会有一个退出条件，加入退出条件后，函数就成了这样：
function factorial(n){
if ((n == 0) || (n == 1))
return 1;
else
return (n * factorial(n - 1));
}
factorial(5); // 120
使用递归的时候要注意出口,不return出口会造成死循环。
看到这里，你可能会想说递归不就是循环吗？这种for都可以简单实现啦。
没错，递归就是一个循环，自身的一个循环。
循环的时间复杂度和空间复杂度都优于用递归实现。
递归是方法调用本身,总是要进出堆栈内存,容易导致内存溢出,并且运行慢,循环是直接在内存中执行,速度快。
递归的优越性在于条理清晰，可读性强，比较适宜于问题本身是递归性质的、用循环难于解决的问题。在二者都不难的情况下，一般都是优先选用循环来解决问题的。
写一个99乘法表
这一个简单的实战例子，相信刚开始学javascript时，老师都给你布置这道作业，直接用两个for就可以轻松实现:
可以直接复杂代码，放到控制台就可以运行
for(var i=1; i<=9; i++){
for(var j=1; j<=i; j++){
document.writeln(j+" x "+i+"="+i*j);
if (j==i) {
document.writeln("<br>");
}
}
}
效果如下：
99sfb.jpg
让我跟据递归简单的实现一个：
var ss = function(x){
if(x>0 && x<=9){
for(var i=1;i<=x;i++){
document.writeln(i+"x"+x+"="+x*i);
if(i==x){
document.write("<br>");
}
}
ss(++x)
}
}
ss(1)//从1开始;改成9，函数里就要改成减了，实现出来就倒过来了
效果一模一样(哈哈，其实我是用了同一张图...)：
99sfb.jpg
上面函数还是有用到for呀，下面我们用纯的：
var jj = function(x,y){
if(x==1&&y==1){
document.writeln(x+"x"+y+"="+x*y);
return false;//注意这个return出口，不然会死循环
}
if(y==1){
document.writeln(x+"x"+y+"="+x*y);
document.writeln("<br>");
x--;
y=x;
}else{
document.writeln(x+"x"+y+"="+x*y);
--y;
}
jj(x,y);
}
jj(9,9)
这个也可以实现效果，只是真的是倒过来了(哈哈....)
99fsb2.jpg
** 在知乎看到有个大神，用递归实现 javascript 中常用的 forEach map filter 函数。
作者：韦捷 访问地址：https://www.zhihu.com/question/54359554/answer/139040476 **
下面让我把实现方法搬运过来装装逼：
先编写两个辅助函数：
// 得到 array 的第一个元素
// head([1,2,3,4,5])
// => 1
var head = function (array) {
return array[0]
}
// 得到 array 除第一个元素外的其他元素
// tail([1,2,3,4,5])
// => [2,3,4,5]
var tail = function (array) {
return array.slice(1, array.length)
}
forEach 时会遍历作为第一个参数的数组，并且逐个将数组中的成员作为参数传给 fn 函数执行。
var forEach = function (array, fn) {
if (array.length > 0) {
fn(head(array))//传进的函数调用数组的第一个值
forEach(tail(array), fn)//重新调用剩下的数组
}
}
forEach([1,2,3], function (x) { console.log(x) })
// => 1
// => 2
// => 3
map 时会遍历作为第一个参数的数组，并且逐个将数组中的成员作为参数传给 fn 函数执行，然后将 fn 的返回值逐个装入新数组，最后返回新数组。
var map = function (array, fn) {
if (array.length > 0) {
return [fn(head(array))].concat(map(tail(array), fn))//实现每个值+1后合并
} else {
return []
}
}
map([1,2,3], function (x) { return x+1 })
// => [2,3,4]
filter 时会遍历作为第一个参数的数组，并且逐个将数组中的成员作为参数传给 fn 函数执行，如果 fn 的返回值是 true 则将当前参数装入新数组，否则忽略当前参数，最后返回新数组。
var filter = function (array, fn) {
if (array.length > 0) {
if (fn(head(array)) === true) {
return [head(array)].concat(filter(tail(array), fn))//实现每个>2的值合并
} else {
return [].concat(filter(tail(array), fn))
}
} else {
return []
}
}
filter([1,2,3,4,5], function (x) { return x>2 })
// => [3,4,5]
JSON中最常用到
用到了递归函数，用来调用json的子节点，把所有json中的子节点中包含某个数的object，都push到一个数组中，然后对其进行绑定。
var arr=[];
function getData(data){
if(data.itemId=="4323"){
arr.push(item_data);
}
if(data.Childs){
if(data.Childs.length>0){
getChilds(data.Childs)
}
}
}
function getChilds(data){
for(var i=0;i<data.length;i++){
getData(data[i]);
}
}
更深入的应用还有二叉树的遍历等...
** 参考资料 **
