Are any JavaScript engines tail call (TCO) optimized?

JavascriptFunctional ProgrammingTail Recursion

Javascript Problem Overview

I have a tail recursive pathfinding algorithm that I've implemented in JavaScript and would like to know if any (all?) browsers would possibly get stack overflow exceptions.

Javascript Solutions

Solution 1 - Javascript

The ECMAScript 4 specification was originally going to add support for TCO, but it was dropped:

No more tail calls in JavaScript?

As far as I know, no widely-available implementations of JavaScript currently do automatic TCO. This may be of use to you, though:

Tail Call Optimization

Essentially, using the accumulator pattern accomplish the same effect.

Solution 2 - Javascript

No joy for the moment, but thankfully proper tail calls are slated for Harmony (ECMAScript version 6) http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls

Solution 3 - Javascript

Pretty much every browser you encounter will barf on "too much recursion". Here's an entry in the V8 bug tracker that will probably be interesting reading.

If it's simple self-recursion, it's probably worth the effort to use explicit iteration rather than hoping for tail-call elimination.

Solution 4 - Javascript

Tail call optimization will be supported In ECMAScript 6 strict mode in the future. Check http://www.2ality.com/2015/06/tail-call-optimization.html for details.

Check http://kangax.github.io/compat-table/es6/ for current engine support.

At the moment (18-07-2019) the following engines support tail call optimization:

  • Safari >= 10
  • iOS >= 10
  • Kinoma XS6
  • Duktape 2.3

support if "experimental JavaScript features"-flag is turned on:

  • Node 6.5
  • Chrome 54 / Opera 41 Current version of the compat table does not list it anymore

Solution 5 - Javascript

Tail call optimization is now available in LispyScript which compiles to JavaScript. You can read more about it here.

Solution 6 - Javascript

Currently no JavaScript implementations recognise tail recursion. Changes are being made in ECMAScript 6, and as others have said, there is an open ticket on V8.

Here you can see V8's generated assembler for a tail recursion function:

Example of how V8 compiles recursion

Compare that to how Clang has compiled the same function in C

Example of C compiler tail recursion

V8 retains the recursive call, whereas the C compiler has recognised the tail recursion and changed it into a loop.

Categories
Recommended Javascript Solutions
Recommended Functional Programming Solutions
Recommended Tail Recursion Solutions

Previous Solution:

MySQL get row position in ORDER BY

SqlMysqlAnalytic Functions

Next Solution:

What is the best way to remove the first element from an array?

JavaArrays

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionclofreshView Question on Stackoverflow
Solution 1 - JavascriptTim SylvesterView Answer on Stackoverflow
Solution 2 - JavascriptMr SpeakerView Answer on Stackoverflow
Solution 3 - JavascriptHank GayView Answer on Stackoverflow
Solution 4 - JavascriptSimon ZyxView Answer on Stackoverflow
Solution 5 - JavascriptSantoshView Answer on Stackoverflow
Solution 6 - JavascriptmcfedrView Answer on Stackoverflow