Are functions in JavaScript tail-call optimized?

Question

I have been trying to understand Tail call optimization in context of JavaScript and have written the below recursive and tail-recursive methods for factorial().

Recursive:

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

Tail-recursive:

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

  return fact(n, 1)
}

But I am not sure if the tail-recursive version of the function will be optimised by JavaScript compiler as it is done in other languages like Scala etc. Can someone help me out on this one?

Just say that `function factorial( n, res=1 ) { if (n – cibercitizen1 Jan 05 '22 at 11:36 — cibercitizen1, Jan 05 '22 at 11:36

score 87 · Accepted Answer · edited Jan 01 '20 at 16:34

87

Update: As of January 1, 2020 Safari is the only browser that supports tail call optimization.

The chromium team explicitly states that Tail Call Optimization is not under active development and can be tracked here.

The implementation for Firefox can be tracked here

Original Post

Yes, ES2015 offers tail call optimization in strict mode. Dr. Axel Rauschmayer lays it out beautifully at the link below so I shall not repeat his words here.

Note: ES 5 does not optimize tail calls.

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

edited Jan 01 '20 at 16:34

Freewalker

5,037
3
42
61

answered May 14 '16 at 08:42

sheeldotme

2,109
13
24

Important caveat: it can only be optimized in strict mode. – Barmar May 14 '16 at 09:32
21

Having tail call optimization in ES2015 is distinctly different from all or even most implementations which otherwise claim to be ES2015-compliant doing proper tail call optimization. The correct answer to the question of "Are functions in JavaScript tail-call optimized?" is "they are if the engine does, otherwise they aren't." See https://www.chromestatus.com/feature/5516876633341952. – May 14 '16 at 10:30
5

I'm pretty sure that browsers will also tail-call-optimise ES5 code when they implement it for ES6. It's just that the ES6 specification now explicitly requires it (and still, no engine has yet implemented it). – Bergi May 14 '16 at 10:56
1

The 'ECMAScript compatibility table' is a good resource to check the compatibility. https://kangax.github.io/compat-table/es6/ – Eldho NewAge May 24 '18 at 13:22

score 18 · Answer 2 · answered Jul 31 '17 at 16:15

18

In theory yes. As the other answer states.

In practice though, as of July 2017, No. Only Safari supports it.

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

answered Jul 31 '17 at 16:15

AK_

7,713
7
42
76

4

Correct - and since Chrome is not working on it at all, there appears to be an excellent probability that tail calls will never be usable in production code. https://www.chromestatus.com/feature/5516876633341952 – Freewalker Nov 09 '17 at 16:57

score 16 · Answer 3 · answered Jun 14 '20 at 18:46

As the other answers have said, not in practice. However, you can define a utility to help out.

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

As you can see, this allows you to write tail recursive functions with only a small difference in syntax, without running into a max call stack error.

I have no idea whether this is a good idea or not. But it definitely is TCO in javascript. Nice work! — tel, May 01 '21 at 08:40

subhashis · Answer 4 · 2021-05-06T17:47:38.887

1

Safari is the only browser that supports tail call optimization. ES2015 offers tail call optimization in strict mode

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


factorial(555)

Follow the LINK

edited May 06 '21 at 17:47

answered May 06 '21 at 15:46

subhashis

4,444
7
36
51

Are functions in JavaScript tail-call optimized?

4 Answers4

Linked