JavaScript is just finally getting tail call optimization on es6. That means that in all current platforms, as of summer 2015, if a function calls itself too many times recursively it eventually causes an exception. This most often comes up in forward recursive algorithms which can be really fast, even with a lot of function calls.
In V8 there isn't any one number of recursions before you get "RangeError: Maximum call stack size exceeded", it depends on the code, the version and the platform. However it often seems to be in the 10-20k range.
// broken console.log( fib(13974) // throws RangeError ) function fib (n) { return calcFib(0, 1, n) } function calcFib (total, last, i) { if (i === 0) return total return calcFib(total+last, total, i-1) }
For this code on my machine 13974 is the straw that broke the camels back, 13973 executes just fine. And incredibly quickly. For some things this is a fine limit, for example the 10,000th Fibonacci number is already too large for JavaScript, and we get 'infinity`. But what could we do to use a recursive algorithm without hitting the stack limit?
One option is to use asynchronous recursion, setting each next iteration inside a timer, and passing a call back along to get (in this case log) the final total.
fib(3000000, console.log.bind(console)) function fib (n, cb) { return calcFib(0, 1, n, cb) } function calcFib (total, last, i, cb) { if (i === 0) return cb(total) setImmediate(function () { calcFib(total+last, total, i-1, cb) }) }
This is slower than the original, up from 100ms to 150ms for n = 13000. It takes a few seconds to do the full 3million. But it never blows out the stack due to depth, because each one is starting fresh.
There is another amazing side effect of this. It's not blocking. A long running synchronous process blocks the thread so no other events/timers can happen, but by breaking it up across the timers we avoid that. The rest of our process still functions as normal, executing any incoming events and timers in between each step of calcFib.