如果递归步骤是 block 中的最后一个表达式 (IIUC),JavaScript 只会将其优化为非递归循环。这是否意味着右侧的递归调用将被优化,而左侧的递归调用将不会在下面进行优化?
function fibonacci(n) {
if(n < 2) return n;
return fibonacci(n-1) + fibonacci(n-2);
}
最佳答案
Does that mean that the right-hand recursive call will be optimised and the left-hand recursive call will NOT in the following?
我不这么认为。只有当您直接返回其他函数返回的内容时,TCO 才有可能。由于您的函数在返回结果之前会处理这两个结果,因此这两个调用都不能进行尾部优化。
底层解释
在基于堆栈的机器方面,这样的代码:
function fun1()
return fun2(42)
function fun2(arg)
return arg + 1
翻译成这个
fun1:
push 42
call fun2
result = pop
push result
exit
fun2:
arg = pop
arg = arg + 1
push arg
exit
TCO可以去掉call-pop-push,直接跳转到fun2
:
fun1:
push 42
goto fun2
exit
但是,像您这样的代码段将是这样的:
fun1:
push n - 1
call fun2
result1 = pop
push n - 2
call fun2
result2 = pop
result3 = result1 + result2
push result3
exit
这里不能用跳转代替调用,因为我们需要回到fun1去执行加法。
Disclaimer: this is a rather theoretical explanation, I have no idea how modern JS compilers actually implement TCO. They are quite smart, so perhaps there's a way to optimize stuff like this as well.
关于javascript - JavaScript 中的尾递归优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44758371/