Javascript的函数递归

作者: CH563 | 来源:发表于2017-03-07 17:01 被阅读143次

    递归是什么?

    想个标题已经让我很纠结了,究竟是函数递归还是递归函数?

    看了下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]);
        }
    }
    

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

    ** 参考资料 **

    相关文章

      网友评论

      本文标题:Javascript的函数递归

      本文链接:https://www.haomeiwen.com/subject/augmgttx.html