Functional JavaScript

Chapter 6. Recursion

This chapter is a transitional chapter meant to smooth the way from thinking about functions to thinking about a deeper understanding of a functional style, including when to break from it and why doing so is sometimes a good idea. Specifically, this chapter covers recursion, or functions calling themselves directly or through other functions.

Self-Absorbed Functions (Functions That Call Themselves)

Historically, recursion and functional programming were viewed as related, or at least they were often taught together. Throughout this chapter, I’ll explain how they’re related, but for now, I can say that an understanding of recursion is important to functional programming for three reasons:

• Recursive solutions involve the use of a single abstraction applied to subsets of a common problem.

• Recursion can hide mutable state.

• Recursion is one way to implement laziness and infinitely large structures.

If you think about the essential nature of a function, myLength, that takes an array and returns its length (i.e., number of elements), then you might land on the following description:^[65]

1. Start with a size of zero.

2. Loop through the array, adding one to the size for each entry.

3. If you get to the end, then the size is the length.

This is a correct description of myLength, but it doesn’t involve recursive thinking. Instead, a recursive description would be as follows:

1. An array’s length is zero if it’s empty.

2. Add one to the result of myLength with the remainder of the array.

I can directly ...