Les fonctions en JavaScript sont-elles optimisées pour le tail-call ?

Question

J'ai essayé de comprendre Tail call optimization dans le contexte de JavaScript et j'ai écrit les méthodes récursives et récursives-queues ci-dessous pour factorial() .

Récursif :

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

Queue-récursive :

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

  return fact(n, 1)
}

Mais je ne suis pas sûr que le tail-recursive de la fonction sera optimisée par le compilateur JavaScript, comme c'est le cas dans d'autres langages tels que Scala, etc. Quelqu'un peut-il m'aider sur ce point ?

Answer 1

Mise à jour : depuis le 1er janvier 2020, Safari est le seul navigateur qui prend en charge l'optimisation des appels de queue.

L'équipe Chrome déclare explicitement que l'optimisation des appels de queue n'est pas en cours de développement actif et qu'elle peut être suivie. aquí .

L'implémentation pour Firefox peut être suivie aquí

Poste original

Oui, ES2015 offre une optimisation des appels de queue en mode strict. Axel Rauschmayer l'a magnifiquement expliqué dans le lien ci-dessous, je ne vais donc pas répéter ses mots ici.

Remarque : l'ES 5 n'optimise pas les appels de queue.

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

Answer 2

Comme l'ont dit les autres réponses, pas en pratique. Cependant, vous pouvez définir un utilitaire pour vous aider.

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

Comme vous pouvez le constater, cela vous permet d'écrire des fonctions récursives de queue avec seulement une petite différence de syntaxe, sans vous heurter à une erreur de pile d'appel maximale.

Answer 3

En théorie, oui. Comme le dit l'autre réponse.

En pratique cependant, depuis juillet 2017, non. Seul Safari le prend en charge.

Compatibilité Javascript ES6 (ES2015) : https://kangax.github.io/compat-table/es6/

Answer 4

Safari est le seul navigateur qui prend en charge l'optimisation des appels de queue. ES2015 offre l'optimisation des appels de queue en mode strict.

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

factorial(555)

Suivez les LIEN