尾调用优化
参考地址:http://es6.ruanyifeng.com/#docs/function
尾调用,就是说在函数的最后一步是调用另一个函数,例如
function a(value) {
return b(value)
}
上述,在函数a
的最后一步调用了函数b
,这种调用方式就是尾调用。
那么,尾调用优化是什么意思呢?
我们知道,函数调用会在内存形成一个“调用记录”,又称“调用帧”(call frame),保存调用位置和内部变量等信息。如果在函数A
的内部调用函数B
,那么在A
的调用帧上方,还会形成一个B
的调用帧。等到B
运行结束,将结果返回到A
,B
的调用帧才会消失。如果函数B
内部还调用函数C
,那就还有一个C
的调用帧,以此类推。所有的调用帧,就形成一个“调用栈”(call stack)。
尾调用由于是函数的最后一步操作,所以不需要保留外层函数的调用帧,因为调用位置、内部变量等信息都不会再用到了,只要直接用内层函数的调用帧,取代外层函数的调用帧就可以了。
当在函数的尾部调用自身时,就成为尾递归。
普通的递归函数吗,由于要保存非常多个调用帧,所以就很容易发生堆栈溢出的错误。但是对于尾递归,就不存在这种错误,因为其只存在一个调用帧。
例如阶乘函数
function factorial(n) {
if (n === 1) return 1
return n * factorial(n - 1)
}
计算n
的阶乘,所以就要保存n
个调用记录
但是,如果使用尾递归的调用方式
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5, 1) // 120
这样在函数整个执行过程中,只保留一个调用记录。
当然,这看起来并不是通俗易懂,计算一个阶乘,还需要另外再传入第二个参数1
,可以使用如下的改进方式
function tailFactorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
function factorial(n) {
return tailFactorial(n, 1)
}
factorial(5)
也可以使用柯里化的方式,意思是将多参数的函数转换为单参数的形式。
function currying(fn, n) {
return function (m) {
return fn.call(this, m, n);
};
}
function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total);
}
const factorial = currying(tailFactorial, 1);
factorial(5) // 120
或者使用es6默认值的方式
function factorial(n, total = 1) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5)
如果您觉得本文对您有用,欢迎捐赠或留言~
- 本博客所有文章除特别声明外,均可转载和分享,转载请注明出处!
- 本文地址:https://www.leevii.com/?p=761