JavaScript尾部调用中的函数是否经过优化

Are functions in JavaScript tail-call optimized?

本文关键字：是否 经过 优化 函数 尾部 调用 JavaScript      更新时间：2023-09-26

我一直在努力理解JavaScript上下文中的Tail call optimization，并为factorial()编写了以下递归和尾部递归方法。

递归：

function factorial (n) {
  if (n < 2) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}

尾部递归：

function factorial (n) {
  function fact(n, acc) {
    if (n < 2) {
      return acc;
    } else {
      return fact(n-1, n * acc);
    }
  }
  return fact(n, 1)
}

但我不确定tail-recursive版本的函数是否会像在Scala等其他语言中一样，通过JavaScript编译器进行优化。有人能帮我解决这个问题吗？

更新：截至2023年7月22日，Safari是唯一支持尾部调用优化的浏览器

如果目标是简单地绕过堆栈限制，就像其他答案所显示的那样，这是可能的。所需要的只是一个懒惰的功能和一个蹦床这与尾部调用优化不同

const trampoline = (x) => {
    while (typeof x == 'function') x = x()
    return x;
}
const lazy = (f) => (...args) => () => f(...args)
function factorial (n) {
  const f = lazy((a, n) => n == 0 ? a : f(n * a, n - 1));
  return trampoline(f(1, n));
}
console.log(factorial(30000)); // Infinity

chromium团队明确表示，Tail Call Optimization没有在积极开发中，可以在这里进行跟踪。

Firefox的实现可以在这里跟踪

原始帖子

是的，ES2015在严格模式下提供尾呼优化。Axel Rauschmayer博士在下面的链接中完美地阐述了这一点，所以我不在这里重复他的话。

注意：ES 5不会优化尾部调用。

http://www.2ality.com/2015/06/tail-call-optimization.html

正如其他答案所说，不是在实践中。但是，您可以定义一个实用程序来提供帮助。

class Tco {
  constructor(func) {
    this.func = func;
  }
  execute() {
    let value = this;
    while (value instanceof Tco)
      value = value.func();
    return value;
  }
}
const tco = (f) => new Tco(f);

function factorial (n) {
  const fact = (n, acc) => tco(() => {
    if (n < 2) {
      return acc;
    } else {
      return fact(n-1, n * acc);
    }
  });
  return fact(n, 1).execute();
}
console.log(factorial(2000000)); // Infinity

正如您所看到的，这允许您编写语法上只有很小差异的尾部递归函数，而不会遇到最大调用堆栈错误。

理论上是的。正如另一个答案所说。

然而，在实践中，截至2017年7月，没有。只有Safari支持它。

Javascript ES6（ES2015）兼容性：https://kangax.github.io/compat-table/es6/

Safari是唯一支持尾部调用优化的浏览器。ES2015在严格模式中提供尾呼优化

    function factorial(n, returnVal= 1) {
      'use strict';
       if (n <= 1) return returnVal;
        return factorial(n - 1, n * returnVal);
}

factorial(555)

按照链接

截至2023年6月，大多数发动机仍然看不到对TCO的支持。

那些想要实现尾部递归算法并对其进行优化的人，可以使用一个实用程序来实现，例如https://stackoverflow.com/a/62376811/7379821

我实现了一个与npm包类似的东西：

https://www.npmjs.com/package/@xtao org/tailrec.js

它的好处是，您可以正常地调用尾部递归函数——您只需在正文中标记尾部调用，如下所示：

import tailrec from "@xtao-org/tailrec.js"
function factorial(n) {
  const fact = tailrec((n, acc) => {
    if (n < 2) {
      return acc;
    } else {
      return fact.tail(n-1, n * acc);
    }
  })
  return fact(n, 1)
}

我希望这能让某人的生活更轻松。享受

相关文章：