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>");
       }
    }
}

效果如下：

让我跟据递归简单的实现一个：

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，函数里就要改成减了，实现出来就倒过来了

效果一模一样(哈哈，其实我是用了同一张图…)：

上面函数还是有用到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)

这个也可以实现效果，只是真的是倒过来了(哈哈….)

---

在知乎看到有个大神，用递归实现 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]);
    }
}

更深入的应用还有二叉树的遍历等…

参考资料

• https://www.zhihu.com/question/54359554/answer/139040476
• http://www.haorooms.com/post/js_dg_jsdihanshu