CODEWITHSUNDEEP
javascript
user479947
user479947

Reputation:

Simple tail-call optimization for recursive, while-loop style functions

I have a simple function:

const stackOverflow = (n = 0) =>
  n === 10000 ? 'cool' : stackOverflow(n + 1)

https://jsfiddle.net/dsso9pg6/

When I run this, I hit a "Maximum call stack size exceeded" error. I've read that these sorts of recursive functions can be written differently to avoid this issue in the call stack (something to do with "tail-call optimization"...), but I don't quite see where the issue lies.

How would I keep this same recursive function structure while avoiding the error?

Edit: Or is this already tail-call optimized? (I was seeing the error in Node.js 8.6 and Chrome 61, but Safari 11 doesn't complain and returns "Cool.")

Upvotes: 1

Views: 370

Answers (1)

Dat Pham
Dat Pham

Reputation: 1865

You got it right, the while-loop in procedural programming can be replaced by recursion in functional programming paradigm. Hence, a technique called "tail-call optimization" is invented in some functional programming languages (Haskell for example) to deal with long call stacks in these scenarios.

The maximum call stack in javascript also depends on the runtime environment: for example, it's 30000 in my browser but could this could vary. So your code works fine in my browser and not throw an error. But the idea is that there is an upper limit and tail-call optimization could eliminate that.

However, tail-call optimization is a feature supported on language engine level and works in the background rather than a feature that we can use. And unfortunately, javascript is not truly an FP language so it does not support this feature yet. Hopefully, when ES6 is finalized we can have this cool feature and use functional programming to its full extent.

Edit: You can check whether your runtime environment support TCO here (look like Safari already supported it)

https://kangax.github.io/compat-table/es6/

Upvotes: 1

Related Questions