Recursion in Functional JavaScript

You may have come across references to recursive functions while programming in JavaScript. You may even have tried to construct (or deconstruct) a few yourself. But you probably haven’t seen a lot of examples of effective recursion in the wild. In fact, other than the exotic nature of this approach, you may not have considered when and where recursion is useful, or how dangerous it can be if used carelessly.

What is Recursion Good For?

Recursion is a technique for iterating over an operation by having a function call itself repeatedly until it arrives at a result. Most loops can be rewritten in a recursive style, and in some functional languages this approach to looping is the default.

However, while JavaScript’s functional coding style does support recursive functions, we need to be aware that most JavaScript compilers are not currently optimized to support them safely.

Recursion is best applied when you need to call the same function repeatedly with different parameters from within a loop. While it can be used in many situations, it is most effective for solving problems involving iterative branching, such as fractal math, sorting, or traversing the nodes of complex or non-linear data structures.

One reason that recursion is favored in functional programming languages is that it allows for the construction of code that doesn’t require setting and maintaining state with local variables. Recursive functions are also naturally easy to test because they are easy to write in a pure manner, with a specific and consistent return value for any given input, and no side effects on external variable states.

Looping

The classic example of a function where recursion can be applied is the factorial. This is a function that returns the value of multiplying a number again and again by each preceding integer, all the way down to one.

For example, the factorial of three is:

[code language="bash"]
3 × 2 × 1 = 6
[/code]

The factorial of six is:

[code language="bash"]
6 × 5 × 4 × 3 × 2 × 1 = 720
[/code]

You can see how quickly these results get big. You can also see that we’re repeating the same behavior over and over. We take the result of one multiplication operation and multiply it again by one less than the second value. Then we do that again and again until we reach one.

Continue reading %Recursion in Functional JavaScript%

by M. David Green via SitePoint