javascriptrecursiontail-recursion

Are functions in JavaScript tail-call optimized?


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?


Solution

  • Update: As of July 22, 2023 Safari is the only browser that supports tail call optimization.

    If the goal is to simply work around the stack limit, as other answers have shown, it is possible. All that is required is a lazy function and a trampoline.

    This is not the same as tail call optimization though the distinction will not matter for most practical purposes as it has the same asymptotic space and time complexity as TCO with a constant overhead that for most purposes will be negligible.

    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
    

    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 at the link below.

    Note: ES 5 does not optimize tail calls.

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