DEV Community

Discussion on: How to Get In the Recursive Mindset

View post
Collapse
 
peerreynders profile image
peerreynders • • Edited

Whenever somebody post an article about recursion with JavaScript they tend to stop with a body-recursive solution.

Given that JavaScript runtimes don't tend to support tail call optimization (more generally last call optimization to support mutual recursion) there may seem to be little value in going through the extra step of transforming to a tail-recursive solution.

What's the equivalent of a tail-recursive solution in JavaScript?

A loop.

In my judgement ad hoc loops can get pretty messy. One way to clean things up is to force the solution through the

ad hoc loop -> body-recursion -> tail-recursion -> clean loop

transformation (for an an example of the last part see my comment here).

The other thing — you close with this code

function factorial(n) {
  if (n <= 1) {
    return 1
  }
  return n * factorial(n - 1)
}
Enter fullscreen mode Exit fullscreen mode

There's nothing wrong with it.

Compare this with my starting point:

function factorial(n) {
  return n > 1 ? n * factorial(n - 1) : 1;
}
Enter fullscreen mode Exit fullscreen mode

I'm going to guess that you find your version much easier to read.

I would call your version "statement-based" while my version is "expression-based".

In my experience concepts like recursion (the mindset if you will) come much easier when you start moving to a more expression-based style of thinking:

  • functions, just like expressions, produce a value (even if it is just undefined). Statements do not.

Becoming more aware of the tension between statements and expressions (or functions) makes it possible to adopt a more value-oriented approach where appropriate (I'd classify recursion as a value-oriented technique).