递归

什么是递归？？？？？？？

递归，就是在运行的过程中调用自己

构成递归需具备的条件。

1.子问题须与原始问题为同样的事，且更为简单。

2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

递归关系就是实体自己和自己建立关系。

我们在两面相对的镜子之间放一根正在燃烧的蜡烛，我们会从其中一面镜子里看到一根蜡烛，

蜡烛后面又有一面镜子，镜子里面又有一根蜡烛……这也是递归的表现。

递归的解析

一个数组“var meta = [1,2,[3,4,[5]],6,[7,[8,9,[10,11,[12]]]]];”，通过递归的方式依次取出这个数组中的数据。

• 最简单的方式是设定一个函数，传入这个数组，然后判断其中的值是否为数组。

• 如果为数组，那么继续调用当前的函数，将这个值传入。

• 如果不为数组，那么就将值return出来，或者push到某个新数组里。

  function fillArray(array,result){  
      var count = array.length;
      var i = 0; 
      for(;i<count;++i){	
          var temp = array[i];
          if(Array.isArray(temp)){
              fillArray(temp,result);
  	} else {		
              result.push(array[i]);
  	}
    }
  }
  var result = [];
  fillArray(meta,result);
  console.log('递归处理的结果：',result);

  • 如果一个结果已经确定，在第二次调用时是否可以从内存里直接读，而不需要再缓存？

  • 设计好一个简单的Key/Value缓存

  • 在循环时，增加一个条件判断，如果缓存中存在，那么直接从缓存读取结果

        var resultMap={}

     var meta = [1,2,[3,4,[5]],6,[7,[8,9,[10,11,[12]]]]]

    function fillArrayII(array,result){

        var count = array.length;

        var i = 0;

        for(;i<count;++i){

            var temp = array[i];

            var g = resultMap[temp];

            if(g){

                result.push(g);

        } else {

                if (Array.isArray(temp)){

                    fillArrayII(temp,result);

            } else {

                    result.push(temp);

            }

        }

        }

    }

    var result = [];

    fillArrayII(meta,result);

    console.log('递归处理的结果：',result);