递归解析

递归解析

题目：一个数组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;
    if (!count) {
      return [];
    }
    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 {
          resultMap[temp] = temp
          result.push(temp);
        }
      }
    }
  }

  var date1 = new Date();
  var time1 = date1.getTime();
  var r = [];
  fillArrayII(meta, r);
  console.log(r);
  var date2 = new Date();
  var time2 = date2.getTime();
  console.log('no cache time : ', time2 - time1);
  var date3 = new Date();
  var time3 = date3.getTime();
  var f = [];
  fillArrayII(meta, f);
  console.log(f)
  var date4 = new Date();
  var time4 = date4.getTime();
  console.log('cache time : ', time4 - time3);