Mastering JavaScript Functional Programming - Second Edition

Decrease and conquer – searching

The most usual case of recursion involves just a single, simple case. We have already seen some examples of this, such as the ubiquitous factorial calculation: to calculate the factorial of n, you previously needed to calculate the factorial of n-1. (See Chapter 1, Becoming Functional – Several Questions.) Let's turn now to a nonmathematical example.

To search for an element in an array, you would also use this decrease and conquer strategy. If the array is empty, then obviously the searched-for value isn't there; otherwise, the result is in the array if and only if it's the first element in it, or if it's in the rest of the array. The following code does just that:

const search = (arr, key) => { if (arr.length ...