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

Question

我一直在尝试在 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

版本是否会被 JavaScript 编译器优化，就像 Scala 等其他语言一样。有人可以帮我解决这个问题吗？

Answer 1

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

如果目标只是解决堆栈限制，正如其他答案所示，这是可能的。 所需要的只是一个惰性函数和一个蹦床。

这与尾部调用优化不同，尽管对于大多数实际用途而言，这种区别并不重要，因为它具有与 TCO 相同的渐近空间和时间复杂度，且开销恒定，对于大多数用途来说可以忽略不计。

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 团队明确表示尾部调用优化并未在积极开发中，可以在此处进行跟踪。

可以在 here

跟踪 Firefox 的实现

原帖

是的，ES2015提供了严格模式下的尾部调用优化。 Axel Rauschmayer 博士在下面的链接中列出了它。

注意：ES 5 没有优化尾部调用。

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

Answer 2

正如其他答案所说，但实际上并非如此。但是，您可以定义一个实用程序来提供帮助。

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

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

Answer 3

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

但实际上，截至 2017 年 7 月，还没有。只有 Safari 支持。

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

Answer 4

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

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


factorial(555)

按照链接

Answer 5

截至 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)
}

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