递归那点事（下）

nys013 基础面试

# 前言

上篇我们说道了一些用到递归的一些面试题，也讲了递归使用命名式函数的完善。

不过，面试题终究是面试题，而递归在实际开发中，根据情况谨慎使用。（本人参与的项目中，用到递归次数的场景，就是封装表格组件时，对嵌套数据的处理上用的多）

下篇，我们来讲讲递归的优缺点，再引申一下事件循环机制。

这里提一下事件循环机制，以帮助理解递归。

js是单线程的，这个是由其用途决定的，这是js的核心，不会改变。

但是单线程就意味着，所有任务需要排队，前一个任务结束，才会执行后一个任务。如果前一个任务耗时很长，后一个任务就不得不一直等着。

所以为了完善这一点，就有了同步任务和异步任务。

下图很好的诠释了事件循环机制，大致过程为：js从上向下读代码，主线程形成堆和栈，栈中代码执行时会调用各种外部API，将各类事件加入任务队列。在栈中的同步任务执行完后，就会从任务队列中取出这些异步任务执行。

所以我们在使用递归时，函数不断调用，栈中任务不断增加，调用的函数因没有执行完仍在栈中没有释放，只有我们满足条件不再递归调用函数时，函数从栈顶向栈底一个个执行完毕释放掉。

每次函数调用都要在栈中分配空间，每次函数调用向栈压入也需要一定时间，可见递归是对时间和空间的消耗比较大的。

还有栈的容量是有限的，若是我们递归层次太多，函数执行嵌套过深，还没有能等到函数执行完毕释放，栈就满了，就会形成栈溢出。

这里有一道面试题值得看看，以下代码迭代太深会造成stack溢出, 改写成不会出错的代码

var queue = ...... //这是一个很大很大的数组
var nextItem = function(){
  var item = queue.pop();
  if(item){
    nextItem();
  }
}

若是理解了事件循环机制，我们就能理解以下这个改错方案了

var nextItem = function(){
  var item = queue.pop();
  if(item) {
    setTimeout(function(){
      nextItem()
    },0)
  }
}

即，使用了延时定时器，将本在同步任务的函数调用，变到了异步任务——

如此循环，像是递归，但是却非递归，我们会确保栈空后才去执行任务队列函数，这样就不会造成栈溢出了。