javascript - JavaScript 中的尾递归优化

Question

如果递归步骤是 block 中的最后一个表达式 (IIUC)，JavaScript 只会将其优化为非递归循环。这是否意味着右侧的递归调用将被优化，而左侧的递归调用将不会在下面进行优化？

function fibonacci(n) {
  if(n < 2) return n;
  return fibonacci(n-1) + fibonacci(n-2);
}

Answer 1

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.