之前分享过递归,其中有一个优化就是尾调用。
先明确尾调用的概念:
尾调用(Tail Call)是函数式编程的一个重要概念,就是指某个函数的最后一步是return调用另一个函数。
function fn() {
return gn()
}
下面几种不是尾调用:
function fn() {
return gn() + 10//调用之后又赋值
}
function fn() {
gn()//没有return,或者说是return了undefined
}
function fn() {
var gnn = gn();
return gnn//调用后还有操作
}
注意,是最后一步操作,不是放在最末尾,下面也算尾调用:
function fn(a) {
if(a > 10){
return gn(10)
}else{
return gn(20)
}
return gn()
}
之前分享过调用栈,如果不是尾调用,那么会生成一个调用栈,直到栈顶的执行完毕,才会释放之前形成的调用栈的内存。尾调用因为是最后一步操作,所以不需要保留之前的栈,也就不需要保存之前的内存,就是递归里面计算阶乘那两个函数。
注意,并不是所有的函数都能尾调用优化,要看你这个函数需不需要使用某些上个函数的变量或者什么的。
尾调用优化其实很大一部分就是递归函数在使用,因为递归函数调用的时候非常耗费内存,可能需要保存成百上千调用栈,很容易内存溢出。如果是尾递归就只有一个调用栈,能把复杂度O(n)的变成O(1)。
至于怎么改写递归变成可以使用尾调用就比较复杂了,需要根据不同函数去修改。比如阮一峰大神的例子:
function sum(x, y) {
if (y > 0) {
return sum(x + 1, y - 1);
} else {
return x;
}
}
sum(1, 100000)
改成:
function sum(x, y) {
if (y > 0) {
return sum.bind(null, x + 1, y - 1);
} else {
return x;
}
}
然后使用蹦床函数:
function trampoline(f) {
while (f && f instanceof Function) {
f = f();
}
return f;
}
执行:
trampoline(sum(1, 100000))
你会发现,很多递归函数都能改成类似的,然后使用蹦床函数实现尾调用优化。
而ES6对尾调用有什么优化?就是函数默认值,在一些场景下,比如阶乘的递归,采用默认值实现尾递归优化。
(完)