递归尾调用优化
之前分享过递归，其中有一个优化就是尾调用。
先明确尾调用的概念：
尾调用（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对尾调用有什么优化？就是函数默认值，在一些场景下，比如阶乘的递归，采用默认值实现尾递归优化。
（完）
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读