技术 | 前端面试题（一）：递归解析

递归基本上是一个必考的算法题，它是实现程序计算过程中描述过程的基础模式之一，可见这是极其重要的。前端考察这个的原因，多数是在于看看面试者对于一些基础算法的了解程度，以及思考程度。

题目：一个数组“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 = {}; 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 {  result.push(temp);
	    }
	}
    }
} var date1 = new Date(); var time1 = date1.getTime(); var r = []; fillArrayII(meta,r); var date2 = new Date(); var time2 = date2.getTime(); console.log('no *** time : ',time2 - time1); var date3 = new Date(); var time3 = date3.getTime(); var f = []; fillArrayII(meta,f); var date4 = new Date(); var time4 = date4.getTime(); console.log('*** time : ',time4 - time3);

大家可以看一下优化的结果：

无缓存的420ms，而缓存过的393ms，足足提升了27ms，虽然这个空间不大，但是如果当递归足够深时，可以节省大量的时间。不过缓存，需要对数据结构有一定的设计，这是一个前提。

那么除了缓存之外，最常用的优化方式应该算尾递归了，通俗易懂的说，尾递归就是把计算结果放到调用者函数的尾部，顶部的返回值越简单越好，而尾巴的返回可能是越来越复杂的计算。

这里只是一个“抛砖引玉”，一般正常情况下递归都可以用迭代来代替。如果你在写完递归之后，再写一个迭代的代替方案，并加以说明，我想你应该会受到青睐。

技术 | 前端面试题（一）：递归解析

全站热榜