CODEWITHSUNDEEP
javascriptrecursiontail-recursion
Aditya Singh
Aditya Singh

Reputation: 16650

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?

Upvotes: 118

Views: 52460

Answers (5)

sheeldotme
sheeldotme

Reputation: 2503

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

Upvotes: 112

Darius J Chuck
Darius J Chuck

Reputation: 64

As of June 2023, there is still no support for TCO in sight in most engines.

Those who would like to implement tail-recursive algorithms and have them optimized, can do that with a utility, such as the one demonstrated by https://stackoverflow.com/a/62376811/7379821

I implemented a similar thing as an npm package:

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

The nice thing about it is that you can call your tail-recursive function normally -- you just mark the tail calls in the body, like so:

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

I hope it makes life easier for someone. Enjoy!

Upvotes: 0

subhashis
subhashis

Reputation: 4878

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

Upvotes: 1

tjjfvi
tjjfvi

Reputation: 409

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.

Upvotes: 29

AK_
AK_

Reputation: 8099

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/

Upvotes: 19

Related Questions