94

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.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
clofresh
  • 1,345
  • 1
  • 9
  • 11
  • 2
    Is it actually a recursive algorithm, or an iterative algorithm implemented with recursion? My understanding is that TCO can only help with the latter. – nmichaels Sep 07 '10 at 16:32
  • 1
    I just want to add that TCO is not `only` an optimization. Supporting it should be part of the language specification, not the compiler/interpreter since code written against one interpreter/compiler with TCO would probably not work on an interpreter/compiler without TCO. – Hoffmann May 04 '14 at 18:34
  • 1
    You can see current support and watch it evolve across engines in Kangax's ES6 compatibility table here: http://kangax.github.io/compat-table/es6/#proper_tail_calls_(tail_call_optimisation) – Roy Tinker Dec 16 '14 at 20:22
  • nmichaels: TCO (Tail Call Optimization) is about *any* tail call, not just recursive tail calls. – Maëlan Apr 06 '21 at 16:40

6 Answers6

48

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

No more tail calls in JavaScript?

As of 2010, no widely-available implementations of JavaScript currently do automatic TCO.

See comments for more recent updates.

Tim Sylvester
  • 22,897
  • 2
  • 80
  • 94
  • 1
    Just an FYI, Rhino has automatic TCO along with Continuations in "interpreted" mode (opt = -1) http://wiki.apache.org/cocoon/RhinoWithContinuations – Mark Porter Oct 01 '12 at 15:27
  • 5
    (sorry for trolling) ECMAScript 6 has included TCO, termed Proper Tail Calls in the specification. – frosty Jan 20 '13 at 06:13
  • @sclv: What's the trampoline reference? – bukzor Jan 29 '13 at 08:28
  • 41
    The accumulator pattern doesn't accomplish the same effect as TCO. It merely transforms recursive algorithms into tail-recursive form. This is a prerequisite for TCO to be possible, but it is not a substitute for it. You'll still blow the stack in a language that doesn't optimise tail-calls. – Marcelo Cantos Jun 17 '13 at 05:45
  • "no widely-available implementations of JS currently do automatic TCO" this is incorrect as of Node 6.2.0, if you pass the right flag – Janus Troelsen Jun 23 '16 at 09:24
  • Tail Call Optimization is supported from ES6 – Elzohary Feb 05 '22 at 15:32
  • Second link seems outdated. – borisdiakur May 01 '23 at 17:40
26

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

Mr Speaker
  • 3,047
  • 24
  • 17
  • 1
    @MarkWilbur The question was specifically about _browsers_, not all existing implementations of ECMAScript. – Useless Code Mar 26 '14 at 04:38
  • 1
    @UselessCode Nope, this question is about "Javascript engines" so... not just browsers – B T Jul 06 '14 at 22:14
  • 1
    @BT There are indeed many non-browser JS environments, and the title does use the more generic "Javascript engines" but the body of the question specifies "...would like to know if any (all?) **browsers** would possibly get stack overflow exceptions." – Useless Code Jul 07 '14 at 11:25
  • I have to counter "but the title says...". I think because he mentions both, the question is about both. But you're right if you're saying it doesn't make the answer obsolete. – B T Jul 07 '14 at 18:04
  • 4
    @MarkWilbur As far as I am aware node using the same version of v8 as chrome - which currently doesn't support do TCO I had a gist with the JS, and the optimised assembler that current V8 produces - https://gist.github.com/mcfedr/832e3553964a014621d5 – mcfedr Nov 07 '14 at 21:02
  • @MarkWilbur A simple test shows that an infinitely recursive function in Node v0.12.7 gets `RangeError: Maximum call stack size exceeded`. Try `node -e 'function x() { x() }; x()'`. – Brian McCutchon Sep 15 '15 at 05:29
13

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
Simon Zyx
  • 6,503
  • 1
  • 25
  • 37
12

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.

Hank Gay
  • 70,339
  • 36
  • 160
  • 222
  • The bug has finally been accepted. It is under the epic: "Feature Request Harmony". Hopefully that means that they plan to add it to ES6 support in V8. – Txangel May 19 '14 at 12:07
  • You can vote for TCO support in Internet Explorer here: https://wpdev.uservoice.com/forums/257854-internet-explorer-platform/suggestions/6850816-es6-tail-call-optimization – Roy Tinker Dec 16 '14 at 20:25
3

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

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Santosh
  • 1,928
  • 2
  • 15
  • 13
2

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.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
mcfedr
  • 7,845
  • 3
  • 31
  • 27