javascript - JavaScript 中的尾递归优化

标签 javascript recursion

如果递归步骤是 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/

相关文章:

javascript - 缩放div中的背景图像

javascript - jQuery 每个循环总是返回最后一个值

javascript - Bootstrap 日期选择器在选择日期后不会自动关闭

javascript - 复杂形状人物轮廓

java - 通过递归调用继续存储变量值

java - 为什么回溯无法生成所有可能的组合?

java - 递归Java RLE解压方法【stackoverflow错误】

javascript - 为什么我的 fiddle 行为不正确?

c++ - 在 C++11 中的编译时 (constexpr) 计算斐波那契数(递归方法)

c - 是 int foo() { return foo();递归函数?