js尾调用优化的实现

尾调用是函数式编程的一个重要概念。本文介绍了它的含义和用法。

1.什么是尾号？

尾调用的概念很简单，可以用一句话说清楚，就是一个函数的最后一步是调用另一个函数。

函数f(x){ return g(x)；}在上面的代码中，函数f的最后一步是调用函数g，称为尾调用。

以下两种情况不是尾号。

//案例一函数f(x){让y=g(x)；返回y；}//case 2函数f(x){ return g(x)1；}在上面的代码中，第一种情况是调用函数g后还有其他操作，所以不是尾调用，即使语义完全一样。案例2也属于调用后的操作，即使是一行写的。

尾调用不一定出现在函数的尾部，只要是最后一个操作。

函数f(x){ if(x ^ 0){ return m(x)} return n(x)；}在上面的代码中，函数m和n都属于尾调用，因为它们是函数F的最后一次操作.

二、尾号调用优化

尾号呼叫之所以不同于其他呼叫，在于其特殊的呼叫位置。

我们知道，一个函数调用将在内存中形成一个“调用记录”，也称为“调用帧”，它存储诸如调用位置和内部变量等信息。如果在函数a内部调用函数b，会在a的调用记录上面形成一个b的调用记录，当b运行时，返回结果给a的调用记录会消失。如果函数B也调用函数C，会有一个C的调用记录栈，以此类推。所有调用记录形成一个“调用栈”。

由于尾调用是函数的最后一次操作，所以不需要保留外函数的调用记录，因为调用位置、内部变量等信息将不再使用，只要直接使用内函数的调用记录代替外函数的调用记录即可。

函数f() {让m=1；设n=2；返回g(m ^ n)；} f()；//相当于函数f(){ return g(3)；} f()；//相当于g(3)；在上面的代码中，如果函数g不是尾调用，函数f需要保存内部变量m和n的值，g的调用位置等信息。但是调用g之后，函数f就完成了，所以f()的调用记录可以完全删除，只保留g(3)的调用记录。

这叫做Tail调用优化’，即只保留内部函数的调用记录。如果所有函数都是尾调用，则可以实现每次执行只有一条调用记录，这将大大节省内存。这就是‘尾呼优化’的含义。

第三，尾部递归

函数调用本身称为递归。如果尾部调用自己，就叫做尾部递归。

递归非常消耗内存，因为需要同时保存数百条调用记录，所以很容易出现“堆栈溢出”错误。但是对于尾部递归，因为只有一个调用记录，所以“堆栈溢出”错误永远不会发生。

函数阶乘(n) { if (n===1)返回1；返回n *阶乘(n-1)；}阶乘(5) //120上面的代码是一个阶乘函数。要计算n的阶乘，最多需要保存n条调用记录，复杂度为O(n)。

如果重写为尾部递归，只保留一条调用记录，复杂度为O(1)。

函数阶乘(n，total) { if (n===1)返回total；返回阶乘(n - 1，n * total)；}阶乘(5，1)//120

可见‘尾调用优化’对递归运算意义重大，因此一些函数式编程语言已经将其写入语言规范。ES6也是如此，它首次明确规定所有ECMAScript实现都必须部署‘尾调用优化’。也就是说，在ES6中，只要使用尾部递归，就不会出现堆栈溢出，相对节省内存。

4.重写递归函数

要实现尾部递归，往往需要重写递归函数，以保证最后一步只调用自己。这样做的方法是将使用的所有内部变量重写到函数的参数中。例如，在上面的例子中，阶乘函数需要使用一个中间变量total，所以重写这个中间变量作为函数的参数。这样做的缺点是不直观，第一眼很难看到。为什么需要传入两个参数5和1来计算5的阶乘？

有两种方法可以解决这个问题。第一种方法是在尾部递归函数之外提供一个正规形式的函数。

函数tailFactorial(n，total) { if (n===1)返回total；返回tailFactorial(n - 1，n * total)；}function阶乘(n){ return tail阶乘(n，1)；}阶乘(5) //120上面的代码通过一个范式的阶乘函数调用尾部递归函数tailFactorial，这看起来正常多了。

函数式编程中有一个概念，叫做currying，意思是把多参数函数转换成单参数形式。这里也可以用真皮。

函数currying(fn，n){ return function(m){ return fn . call(this，m，n)；};}函数tailFactorial(n，total) { if (n===1)返回total；返回tailFactorial(n - 1，n * total)；}const阶乘=currying(tail阶乘，1)；阶乘(5) //120上面的代码将尾部递归函数tailFactorial更改为只接受一个参数的阶乘。

第二种方法简单得多，就是使用ES6函数的默认值。

函数阶乘(n，total=1) { if (n===1)返回total；返回阶乘(n - 1，n * total)；}阶乘(5) //120在上面的代码中，参数total的默认值为1，因此在调用时没有必要提供这个值。

综上所述，递归本质上是一种循环运算。纯函数式编程语言没有循环操作命令，所有的循环都是通过递归实现的，这就是为什么尾部递归对于这些语言来说极其重要。对于其他支持‘尾调用优化’的语言(如Lua、ES6)，只需要知道循环可以用递归代替，一旦使用递归，最好使用尾递归。

(【说明】本文摘自我写的《ECMAScript 6入门》)

动词（verb的缩写）严格模型

ES6的尾呼优化只在严格模式下开启，正常模式无效。

这是因为在正常模式下，函数内部有两个变量，可以跟踪函数的调用栈。

参数：调用时返回函数的参数。Func.caller:返回调用当前函数的函数。当尾部调用优化发生时，函数的调用栈会被重写，所以上面两个变量会失真。严格模式禁用这两个变量，因此尾部调用模式仅在严格模式下生效。

以上就是本文的全部内容。希望对大家的学习有帮助，支持我们。