luke.dewitt

$ cd ~/talks/recursion-and-javascript

2017-01-31REDspace Tech Share

Recursion & JavaScript: WTF⁠

Why deep recursion blows the stack in JavaScript, the setTimeout trick that gets around it, and where tail call optimization actually stood.

$ open slides

  1. WTF
  2. I LOVE RECURSION
  3. AS LONG AS THERE’S BEEN JAVASCRIPT, THERE HAVE BEEN ISSUES WITH RECURSION… ▸… of course, that hasn’t been JavaScripts only problem as long as it has been around…
  4. WHY? ▸JavaScript is not tail call optimized
  5. WHAT? ▸Tail Call Optimized
  6. TAIL CALL OPTIMIZATION ▸JavaScript recursive functions need to keep track of where they were called from each time, so they can resume at the correct point ▸Recursive functions stack up on each other ▸The stack builds up and eventually you run out of memory
  7. UNTIL THIS…
  8. UNTIL THIS…
  9. WHAT? ▸calling the function recursively from within a timeout will clear the stack ▸… or at least that’s how he explained it.
  10. SO…
  11. TURNS OUT… ▸Tail call optimization is part of the standard for ES6, yet has not been implemented by most platforms… ▸iOS10 supports it ▸#appleFTW ▸Node > 6.5 supports it ▸Only when running in “harmony” mode ▸run node using the ‘—harmony’ flag ▸full table here: https://kangax.github.io/compat-table/es6/
  12. SO…
  13. THANK YOU! HERE’S A FUN GIF
1 / 13
download pdf ↓

$ cat notes.md

An internal tech share at REDspace. I love recursion. JavaScript, historically, has not loved it back.

Why it breaks

JavaScript wasn’t tail call optimized. Every recursive call has to remember where it was called from so it can resume there, so the calls stack up on each other until you run out of memory.

Until this…

Then I found a setTimeout(..., 0) in our code with the comment “prevents stack blowout with recursion.” Calling the function again from inside a timeout starts it on a fresh stack, so the old one never builds up. Or at least, that’s how it was explained to me.

Turns out…

Tail call optimization is part of the ES6 standard, but most platforms hadn’t implemented it yet:

  • iOS 10 supported it. #appleFTW
  • Node 6.5+ supported it, but only behind the --harmony flag.
  • The full picture: the ES6 compatibility table.
visitor@whatadewitt: ~