4.4　递归

递归函数是指调用自身的函数，在前文的深拷贝函数中我们就用到了递归函数，让我们来回忆一下，示例如下。

上例中的函数deepCopy就是递归函数。

递归函数必须有可以终止递归调用的语句，否则会导致内存溢出，以一个计算阶乘的函数为例，如果没有终止递归的条件，这个函数将无休止地运行下去，会导致内存溢出，而“聪明”的浏览器则会抛出栈溢出的错误，示例如下。

为以上函数添加终止递归的条件，示例如下。

我们也可以通过arguments.callee调用函数自身，但arguments.callee性能不佳，因此，在严格模式下arguments.callee是无法使用的，示例如下。

在讲尾递归之前，先了解一下函数调用堆栈的问题，这里需要引入一个概念——栈帧。

有如下一段代码：

函数调用时会创建一个帧，帧中包含的参数和局部变量等信息形成一个栈帧。当运行的程序从当前函数A调用另外一个函数B时，就会为函数B建立一个新的栈帧，这个栈帧会被压入函数A的栈帧。当函数B返回时，其栈帧会从函数A的栈帧中弹出，此时进入函数A的栈帧，如果函数A也返回，那么栈就空了。

再来谈递归，递归的性能并不好，因为在递归终止前，JavaScript引擎会为每一次递归分配一块内存以存储栈帧，随着递归的深入，这个栈帧也越来越庞大，也就导致递归占用的内存越来越多，当传入factorial的数值增加到一定程度时，例如10 000（不同浏览器的内存限制不同）,浏览器就会因为耗尽内存而抛出栈溢出的错误。

尾调用是指在函数执行的最后一步调用另外一个函数并返回，因为函数返回后，其栈帧也会被弹出，因此其占用的内存也得以释放，示例如下。

      function foo(){
          return bar()
      }

而在递归中进行尾调用就称为“尾递归”，尾递归会在执行时被优化成循环形式执行，这种方式被称为TCO（Tail Call Optimisation，尾调用优化），示例如下。

遗憾的是，大多数JavaScript引擎（V8引擎曾短暂支持过TCO，但于2017年7月从TurboFan的源码中移除了支持TCO的代码，Safari已经支持）并没有实现尾递归的优化，所以上述代码依旧会抛出栈溢出的错误。

练习

• 使用递归。