【转】尾调用优化

尾调用&＃xff08;Tail Call&＃xff09;是函数式编程的一个重要概念&＃xff0c;本文介绍它的含义和用法。

一、什么是尾调用&＃xff1f;

尾调用的概念非常简单&＃xff0c;一句话就能说清楚&＃xff0c;就是指某个函数的最后一步是调用另一个函数。

function f(x){return g(x);
}


上面代码中&＃xff0c;函数f的最后一步是调用函数g&＃xff0c;这就叫尾调用。

以下两种情况&＃xff0c;都不属于尾调用。

// 情况一
function f(x){let y &＃61; g(x);return y;
}// 情况二
function f(x){return g(x) &＃43; 1;
}


上面代码中&＃xff0c;情况一是调用函数g之后&＃xff0c;还有别的操作&＃xff0c;所以不属于尾调用&＃xff0c;即使语义完全一样。情况二也属于调用后还有操作&＃xff0c;即使写在一行内。

尾调用不一定出现在函数尾部&＃xff0c;只要是最后一步操作即可。

function f(x) {if (x > 0) {return m(x)}return n(x);
}


上面代码中&＃xff0c;函数m和n都属于尾调用&＃xff0c;因为它们都是函数f的最后一步操作。

二、尾调用优化

尾调用之所以与其他调用不同&＃xff0c;就在于它的特殊的调用位置。

我们知道&＃xff0c;函数调用会在内存形成一个"调用记录"&＃xff0c;又称"调用帧"&＃xff08;call frame&＃xff09;&＃xff0c;保存调用位置和内部变量等信息。如果在函数A的内部调用函数B&＃xff0c;那么在A的调用记录上方&＃xff0c;还会形成一个B的调用记录。等到B运行结束&＃xff0c;将结果返回到A&＃xff0c;B的调用记录才会消失。如果函数B内部还调用函数C&＃xff0c;那就还有一个C的调用记录栈&＃xff0c;以此类推。所有的调用记录&＃xff0c;就形成一个"调用栈"&＃xff08;call stack&＃xff09;。

尾调用由于是函数的最后一步操作&＃xff0c;所以不需要保留外层函数的调用记录&＃xff0c;因为调用位置、内部变量等信息都不会再用到了&＃xff0c;只要直接用内层函数的调用记录&＃xff0c;取代外层函数的调用记录就可以了。

function f() {let m &＃61; 1;let n &＃61; 2;return g(m &＃43; n);
}
f();// 等同于
function f() {return g(3);
}
f();// 等同于
g(3);


上面代码中&＃xff0c;如果函数g不是尾调用&＃xff0c;函数f就需要保存内部变量m和n的值、g的调用位置等信息。但由于调用g之后&＃xff0c;函数f就结束了&＃xff0c;所以执行到最后一步&＃xff0c;完全可以删除 f() 的调用记录&＃xff0c;只保留 g(3) 的调用记录。

这就叫做"尾调用优化"&＃xff08;Tail call optimization&＃xff09;&＃xff0c;即只保留内层函数的调用记录。如果所有函数都是尾调用&＃xff0c;那么完全可以做到每次执行时&＃xff0c;调用记录只有一项&＃xff0c;这将大大节省内存。这就是"尾调用优化"的意义。

三、尾递归

函数调用自身&＃xff0c;称为递归。如果尾调用自身&＃xff0c;就称为尾递归。

递归非常耗费内存&＃xff0c;因为需要同时保存成千上百个调用记录&＃xff0c;很容易发生"栈溢出"错误&＃xff08;stack overflow&＃xff09;。但对于尾递归来说&＃xff0c;由于只存在一个调用记录&＃xff0c;所以永远不会发生"栈溢出"错误。

function factorial(n) {if (n &＃61;&＃61;&＃61; 1) return 1;return n * factorial(n - 1);
}factorial(5) // 120


上面代码是一个阶乘函数&＃xff0c;计算n的阶乘&＃xff0c;最多需要保存n个调用记录&＃xff0c;复杂度 O(n) 。

如果改写成尾递归&＃xff0c;只保留一个调用记录&＃xff0c;复杂度 O(1) 。

function factorial(n, total) {if (n &＃61;&＃61;&＃61; 1) return total;return factorial(n - 1, n * total);
}factorial(5, 1) // 120


由此可见&＃xff0c;"尾调用优化"对递归操作意义重大&＃xff0c;所以一些函数式编程语言将其写入了语言规格。ES6也是如此&＃xff0c;第一次明确规定&＃xff0c;所有 ECMAScript 的实现&＃xff0c;都必须部署"尾调用优化"。这就是说&＃xff0c;在 ES6 中&＃xff0c;只要使用尾递归&＃xff0c;就不会发生栈溢出&＃xff0c;相对节省内存。

四、递归函数的改写

尾递归的实现&＃xff0c;往往需要改写递归函数&＃xff0c;确保最后一步只调用自身。做到这一点的方法&＃xff0c;就是把所有用到的内部变量改写成函数的参数。比如上面的例子&＃xff0c;阶乘函数 factorial 需要用到一个中间变量 total &＃xff0c;那就把这个中间变量改写成函数的参数。这样做的缺点就是不太直观&＃xff0c;第一眼很难看出来&＃xff0c;为什么计算5的阶乘&＃xff0c;需要传入两个参数5和1&＃xff1f;

两个方法可以解决这个问题。方法一是在尾递归函数之外&＃xff0c;再提供一个正常形式的函数。

function tailFactorial(n, total) {if (n &＃61;&＃61;&＃61; 1) return total;return tailFactorial(n - 1, n * total);
}function factorial(n) {return tailFactorial(n, 1);
}factorial(5) // 120


上面代码通过一个正常形式的阶乘函数 factorial &＃xff0c;调用尾递归函数 tailFactorial &＃xff0c;看起来就正常多了。

函数式编程有一个概念&＃xff0c;叫做柯里化&＃xff08;currying&＃xff09;&＃xff0c;意思是将多参数的函数转换成单参数的形式。这里也可以使用柯里化。

function currying(fn, n) {return function (m) {return fn.call(this, m, n);};
}function tailFactorial(n, total) {if (n &＃61;&＃61;&＃61; 1) return total;return tailFactorial(n - 1, n * total);
}const factorial &＃61; currying(tailFactorial, 1);factorial(5) // 120


上面代码通过柯里化&＃xff0c;将尾递归函数 tailFactorial 变为只接受1个参数的 factorial 。

第二种方法就简单多了&＃xff0c;就是采用ES6的函数默认值。

function factorial(n, total &＃61; 1) {if (n &＃61;&＃61;&＃61; 1) return total;return factorial(n - 1, n * total);
}factorial(5) // 120


上面代码中&＃xff0c;参数 total 有默认值1&＃xff0c;所以调用时不用提供这个值。

总结一下&＃xff0c;递归本质上是一种循环操作。纯粹的函数式编程语言没有循环操作命令&＃xff0c;所有的循环都用递归实现&＃xff0c;这就是为什么尾递归对这些语言极其重要。对于其他支持"尾调用优化"的语言&＃xff08;比如Lua&＃xff0c;ES6&＃xff09;&＃xff0c;只需要知道循环可以用递归代替&＃xff0c;而一旦使用递归&＃xff0c;就最好使用尾递归。

&＃xff08;[说明] 本文摘自我写的《ECMAScript 6入门》&＃xff09;

五、严格模式

ES6的尾调用优化只在严格模式下开启&＃xff0c;正常模式是无效的。

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

• arguments&＃xff1a;返回调用时函数的参数。
• func.caller&＃xff1a;返回调用当前函数的那个函数。

尾调用优化发生时&＃xff0c;函数的调用栈会改写&＃xff0c;因此上面两个变量就会失真。严格模式禁用这两个变量&＃xff0c;所以尾调用模式仅在严格模式下生效。

六、参考链接

• 尾调用&＃xff0c;from 维基百科
• Tail Calls, Default Arguments, and Excessive Recycling in ES-6, by raganwald
• Proper Tail Calls, from programming in Lua

&＃xff08;完&＃xff09;

文档信息

• 版权声明&＃xff1a;自由转载-非商用-非衍生-保持署名&＃xff08;创意共享3.0许可证&＃xff09;
• 发表日期&＃xff1a; 2015年4月10日
• 更多内容&＃xff1a; 档案 » Javascript
• 文集&＃xff1a;《前方的路》&＃xff0c;《未来世界的幸存者》