技术 | 前端面试题(一):递归解析

阅读 4116
收藏 180
2017-02-14
原文链接:mp.weixin.qq.com

我和阿里巴巴的同事守雌将为大家带来一个系列专题:前端面试题解析,一周更新两篇,也许答案可能不是最优的,但是也可以给你提供解决问题的思路。面试题力求实战,期望对于找工作的你,温故而知新的你,能有所帮助。


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

题目:一个数组“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 cache 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('cache time : ',time4 - time3);

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

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

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

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

欢迎大家关注象尘说-编程之道“小密圈”,前端面试题解析,会在“小密圈”中讨论其他的优化方案。如果你还不知道“小密圈”有什么作用,可以点击菜单栏上“小密圈”来获取详情。

地址链接:https://wx.xiaomiquan.com/mweb/views/joingroup/join_group.html?group_id=5414881224&secret=ql23uqjlnm80lxm9od6llkqijltb5r3u&extra=3e73c043fd796c547b54675d60d9b7bc343c71590f108862080eb35eb863bb1c


更多精彩内容可关注我的个人微信公众号:搜索fed-talk或者扫描下列二维码,也欢迎您将它分享给自己的朋友。

评论