121

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?

Improve this question
1
  • Just say that `function factorial( n, res=1 ) { if (n Commented Jan 5, 2022 at 11:36

5 Answers 5

Reset to default
118

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

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

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 chromestatus.com/feature/5516876633341952.
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).
The 'ECMAScript compatibility table' is a good resource to check the compatibility. kangax.github.io/compat-table/es6
The thing that annoys me the most about browsers not implementing TCO is that reading the source code of the popular frameworks, most of them could benefit enormously from TCO performance-wise if they could rely on it being available. Every virtual DOM implementation tends to be written in continuation passing style, and currently has to use a trampoline.
"This is not the same as tail call optimization" - hmm... in what sense? Is this just a semantic point - i.e. do you simply mean by this that since you're implementing the optimization yourself rather than it being built into the language, it's not properly called "tail call optimization" because that's the name of a language feature? Or is it a substantive point - i.e. do you mean to say that there's an actual behaviour difference between this workaround and true tail call optimization implemented in the language? If there's a substantive difference, what is it? I can't see it...
|
29

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.

Improve this answer

2 Comments

I have no idea whether this is a good idea or not. But it definitely is TCO in javascript. Nice work!
This is not TCO, see my updated answer for a similar work around without classes.
19

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/

Improve this answer

1 Comment

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. chromestatus.com/feature/5516876633341952
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

Improve this answer

Comments

0

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!

Improve this answer

2 Comments

See also this answer.
This is not TCO, see my updated answer for a similar work around without having to write your recursive function any differently.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.