Loops, Array Methods, and Recursion
Tags: javascript, functional
Published: 2021-11-18 23:22:01

"Loops" are an extremely powerful abstraction in computing and `for` loops are often the entry point for most programmers into the topic. This level of abstraction is very primitive and can lead to writing quite inelegant, indirect, and often error prone code. There are several other versions of the loop as well as more specialized approaches to tackling the same category of problems. 

We'll start with the explanation of what a loop, as an abstraction, offers programmers. Then we'll discuss how "looping" manifests in Javascript. Finally we'll discuss how we can tackle the same problems with functional-programming strategies: array-methods/functions and recursion.

## What is "Looping"?

If we imagine our computer as a machine executing our code, a series of "operations", we immediately see the benefits of a machine reliably and reproducably performing mechanical work. For example, we can think of the summation of 1,000,000 figures from an accounting record. If we consider how we would describe this process doing it by hand, we may say something like:

``` 
- for summing a list of 1,000,000 things, 
    - we have a starting value of 0, 
    - take the items one at a time, 
    - each step add the taken item to our starting value, then use that as our next starting value
    - start with the first item in the list
    - stop when there are no more items in the list
    - finally, examine the updated starting value (the "sum")
```

From this description, we can distill the basic concepts of looping: 
    
- a notion of a "set" which we want to perform a repeated operation upon,
- an initial state,
- how we are going to traverse the set,
- an operation defined that we want to perform repeatedly,
- a starting condition,
- an ending condition, and
- a final operation

Not coincidentally, I described the pattern for what is generally considered the most primative type of loop: the `for` loop. So let's start with an examination of this loop as our launching point.

## Types of Loops

### For Loops

A `for` loop, at least conceptually, is the building block of most other loops. It satisfies all the qualities of looping described above. In Javascript, it has the form:

```javascript
for(<starting_condition>; <ending_condition>; <how_to_progress_after_each_step>;) {
    <work_to_do_at_each_step>
}
```

While this annotation doesn't directly map to the above described qualities of looping, actual implementations make it more apparent that it does in fact correspond. Let us consider summing a list of 1 million numbers, stored in an array.

```javascript
function forSum(array_of_numbers, sum = 0) {
  for(let i = 0; i < array_of_numbers.length; i++) {
      sum += array_of_numbers[i]
  }
  return sum
}
```

Here it is more apparent that each quality of a loop is addressed. Our set (`array_of_numbers`), operation to perform repeatedly (`+=`), initial state (`sum = 0`), starting condition (`let i = 0` or "start with the starting index of the array"), ending condition (`i < array_of_numbers.length` or "until the index is one less than the length of the array"), and a final operation (`return`).

> Another important quality of "looping" is the ability to stop midway through the process and to skip certain steps. These concepts are embodied in Javascript with the keywords `break` and `continue`.
>  
> With `break` we can abort the remaining steps, essentially overriding the ending condition. This is often referred to as `short-circuiting`. The purpose of this is to both improve efficiency--by not requiring the procedure to run a bunch of extra times--and to avoid the need for including "by-pass" code (code which essentially does nothing just to reach the completed state).
>
> `Continue` allows for an immediate jump to the end of the block of code contained within the loop. This too allows for avoiding certain types of "useless" code.
>
> Take this contrived example of summing the natural numbers from 1 to some unknown number, discarding all numbers that are multiples of 2 or 3, stopping once the sum reaches a certain target. We want to return the sum that exceeds the supplied target as well as the list of numbers that make up that sum. We don't know how many numbers that will take, so we will make our ending condition "while our current number is less than Infinity".
>
> ```javascript
> function takeNonMultiplesOfTwoOrThreeUntilSumIs(target) {
>   let sum = 0
>   let nums = []
>   for(let i = 1; i < Infinity; i++) {
>       if (i % 2 == 0 || i % 3 == 0) continue;
>       if (sum >= target) break;
>       sum += i
>       nums.push(i)
>   }
>   return [sum, nums]
> }
> ```
>
> This can be accomplished in other manners, but the inclusion of these keywords can often avoid extra code.

Using the `for` loops as an initial point of reference, we can consider variations that fix one or more of the above "knobs" and give us more particularlized behaviour. This is done for convenience and it should be noted that each of the other loops can be implemented with a `for` loop. 

### While Loops

A `while` loop appears a lot more streamlined, but its obvious applications are fairly specific. A `while` loop reduces the number of parameters from three (starting condition, ending condition, traversal instruction) down to 1 (ending condition). It disguises the other two parameters: the ending condition is established by monitoring a value outside the loop definition, and the traversal logic is (often) contained within the loop's block:

```javascript
function whileSum(arrayOfNumbers, sum = 0) {
  while (arrayOfNumbers.length) {
    let num = arrayOfNumbers.pop();
    sum += num;
  }
  return sum;
}
``` 

While certain circumstances benefit from this format, it does require special care not to create an "infinite loop". This is because there are a limited set of Javascript values which are [falsey](https://developer.mozilla.org/en-US/docs/Glossary/Falsy). Because the end condition *cannot* be set in terms of a parameter of the loop, it is easy to make a mistake here.

As with the `for` loop, `break` can be used to short-circuit the entire loop and `continue` can be used to short-circuit the current iteration.

### Do-While Loops

Very similar to a while loop, the `do-while` loop runs its execution block (the `do` block) *before* checking the `while`/end condition. The syntax includes a `do` block followed by a `while` statement: 

```javascript
function doWhileSum(arrayOfNumbers, sum = 0) {
  do {
    console.log(`Number of items left to sum: ${arrayOfNumbers.length}`);
    if (!arrayOfNumbers.length) {
      console.log("No items to sum");
      break;
    } else {
      let num = arrayOfNumbers.pop();
      sum += num;
    }
  } while (arrayOfNumbers.length);
  return sum
}
```

### For-Of Loops

A relatively recent addition to Javascript is the `for...of` loop, which iterates over all of the **values** in an iterable object (objects or arrays alike) ([MDN docs here](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Loops_and_iteration#for...of_statement)). 

A `for...of` solution could look like:

```javascript 
function forOfSum(arrayOfNumbers, sum = 0) {
  for(let num of arrayOfNumbers) {
    sum += num
  }
  return sum
}
```

### For-In Loops

There is also a `for...in` loop which iterates over **keys** and includes some you may not expect.  

> The for...in statement iterates over all enumerable properties of an object that are keyed by strings (ignoring ones keyed by Symbols), including inherited enumerable properties.
> 
> ...
> 
> Given that for...in is built for iterating object properties, not recommended for use with arrays, and options like Array.prototype.forEach() and for...of exist, what might be the use of for...in at all?
>
> It may be most practically used for debugging purposes, being an easy way to check the properties of an object (by outputting to the console or otherwise). Although arrays are often more practical for storing data, in situations where a key-value pair is preferred for working with data (with properties acting as the "key"), there may be instances where you want to check if any of those keys hold a particular value.
>
>  ([Source - MDN docs](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Loops_and_iteration#for...in_statement))

A contrived example would be to filter out values in an array that are at indices that are divisible by 2 or 3:

```javascript 
function forInSum(arrayOfNumbers, sum = 0) {
  for(let index in arrayOfNumbers) {
    if (index % 2 == 0 || index % 3 == 0) continue;
    sum += arrayOfNumbers[index]
  }
  return sum
}
```

> Note that in a `for-in` loop, we are working with keys of an object (or indices of an array in this simple example). In order to work with the values, we need to take the additional step of reading the value with the given object-key of the current iteration of the loop.

### Loops: Final Thoughts

Loops work on sets of data, be it an array, an object, strings, or one of the more exotic new objects. Definitionally, a set can be of any size including a single item or an empty set. An example of a loop operating on an empty set is as follows:

```javascript
while(true) {
  console.log(Date.now())
}
```

The loop is not tied to the data that it works upon, it merely describes an algorithm for repeatedly computing. While operating on sets in this way feels very flexible, it can be very error prone to consistently reimplement common patterns of object access. Therefore, it is very useful to consider using well established access patterns that exist, as we will consider next.

## From Loops to Array Methods/Functions

When introducing the concept of a loop, we described that a loop works on a "set". In Javascript, this translates to mean an `iterable object` which includes most commonly objects, arrays, and strings.

If we focus our thinking to arrays for a moment, we can consider another class of solutions as an alternative to loops. 

> Before concluding that limiting our discussion to arrays is a significant limitation, consider that objects, strings, and other objects each have methods which will convert the object to an array (ex. `Object.values`, `String.prototype.split`, etc).

When  traversing an array, we can often use array methods to complete those tasks more explicitly than a loop will permit. Loops are relatively low level operations that require us to implement much of the logic ourselves. Many array methods define a clear intent for common operations and they can be chained together using the "dot" syntax. For example:

```javascript
someArray
  .filter(...omittedFilterFunction)
  .map(...omittedMapFunction)
  .forEach(...omittedForEachFunction)
```

If you are performing some "side-effect" with each value in an array, there is `forEach`. If you are transforming each value, there is `map`. If you are conditionally rejecting values, there is `filter`. If you are "accumulating" values, there is `reduce`. 

> Accumulation can take many forms, but basically it means that you are starting with some value (commonly call the `accumulator`) and then using each element in the array to update the accumulator. You can find the documentation for these methods on the MDN site:
> 
> - [forEach](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach), 
> - [map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map), 
> - [filter](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/filter), and 
> - [reduce](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce).

There are several other built in array methods to consider, but these are the most common ones to consider. Additionally, their relationship to one another should provide insight into the "declarative" advantage over loops. 

### Reduce

`Array.prototype.reduce` is the `for` loop of array methods. It is the least declarative type of array iteration method and can be used to implement every other built-in array iteration method. In short, `reduce` iterates over an entire array, allowing for custom logic for copying and/or transforming of the original array's items into a new array (also known as the "accumulator").

The `reduce` method takes a callback which is called once for each value in the array and an initial value for your `accumulator`. This callback's signature is `(accumulator, currentValue, currentIndex, originalArray) => accumulator` (provide only as many parameters as you require, generally `(accumulator, currentValue)`. 

> If you're unfamiliar with this pattern of "variable" function arguments, I have written an article on [function arity in Javascript](https://dev.to/justin_m_morgan/a-deeper-dive-into-function-arity-with-a-focus-on-javascript-ae).

The value from `accumulator` is then passed as the first argument on the next iteration. It is easy to accidentally not return a value from your callback, especially when using an array function.

For example, if we want to implement a [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) function for an arbitrary array of numbers: 

```javascript
const arrayToBeFizzBuzzed = 
  Array(100)
    .fill(Infinity) // Array must have assigned value to map
    .map((_, i) => i + 1) 

const isFactorOf = (factor) => (testNumber) => !(num % factor)

const FizzBuzzReduce = (numbers, startingAccumulator = []) =>
  numbers.reduce((accumulator, num) => {
    if (isFactorOf(15)(num)) return [...accumulator, "FizzBuzz"];
    if (isFactorOf(3)(num)) return [...accumulator, "Fizz"];
    if (isFactorOf(5)(num)) return [...accumulator, "Buzz"];
    return [...accumulator, num];
  }, startingAccumulator);
```

Or if instead we wanted to filter out those values:

```javascript
const FizzBuzzFilterReduce = (numbers, startingAccumulator = []) =>
  numbers.reduce((accumulator, num) => {
    isFactorOf(15)(num) || isFactorOf(3)(num) || isFactorOf(5)(num) 
    ? accumulator
    : [...accumulator, num];
  }, startingAccumulator);
```

The basic idea here is that we are traversing the array and conditionally transforming the items in it (in the first case) and conditionally appending it to the accumulator (in the second case). Whether the item is transformed or not, a new copy of the accumulator is returned from the callback function to be used for the next iteration (with the next item in the array).

Rewriting our summation above using `reduce` would look like this:

```javascript
function reduceSum(arrayOfNumbers) {
  return arrayOfNumbers.reduce((acc, num) => acc += num, 0)
}
```

### Map

`Map` particularizes `reduce` by handling the copying of the transformed value into the accumulator in a default manner. Whatever value is returned from the transformation function is appended to the accumulator. So the above example could be rewritten as:

```javascript
const FizzBuzzMap = (numbers) => 
  numbers.map(num => {
    if (isFactorOf(15)(num)) return "FizzBuzz";
    if (isFactorOf(3)(num)) return "Fizz";
    if (isFactorOf(5)(num)) return "Buzz";
    return num;
  })
```

You can therefore think of `map` as the following particularization of `reduce` (written as a plain function, not a prototype method):

```javascript
const map = (array, transformer) => {
  return array.reduce((accumulator, currentValue) => {
    return [...accumulator, transformer(currentValue)]
  }, [])
}
```
### Filter

`Filter` particularizes `reduce` by handling the conditional copying of the item into the accumulator in a default manner. Unlike `map`, the value being iterated over is left unchanged in the resulting array. Rather, the [truthiness](https://developer.mozilla.org/en-US/docs/Glossary/Truthy) of the value determines whether the value is copied to the accumulator or rejected (and the accumulator being passed on unchanged). So the above example could be rewritten as:

```javascript
const FizzBuzzFilter = (numbers) => 
  numbers.filter(num => {
    return isFactorOf(15)(num) || isFactorOf(3)(num) || isFactorOf(5)(num) 
  })
```

You can therefore think of `filter` as the following particularization of `reduce` (written as a plain function, not a prototype method):

```javascript
// A predicate function must have a unary function signature
// and should be interpretted as returning a truthy or falsy value
// ex. const isOdd = num => num % 2
const filter = (array, predicateFn) => {
  return array.reduce((accumulator, currentValue) => {
    return predicateFn(currentValue)
    ? [...accumulator, currentValue]
    : accumulator
  }, [])
}
```

### forEach

`Array.prototype.forEach` is an array method which iterates over each element in an array but returns `undefined`. It is useful for performing side-effects on items in an array. It therefore cannot be chained onto by other array methods. It is most similar to `map`, though the return value of the callback function is not useful.

```javascript
const FizzBuzzLogger = (numbers) => 
  numbers.forEach(num => {
    if (isFactorOf(15)(num)) return console.log("FizzBuzz");
    if (isFactorOf(3)(num)) return console.log("Fizz");
    if (isFactorOf(5)(num)) return console.log("Buzz");
    return console.log(num);
  })
```

### And Beyond!

From this starting point, we can survey array methods that are further particularizations. The [MDN Docs] list several very useful ones (`.every`, `.some`, `.reverse`), some more infrequently used by my experience (`.lastIndexOf`). 

If this approach interests you, you can dive even deeper by surveying the various array functions available in popular utility libraries suchs [Lodash](https://lodash.com) and (for even more extreme examples) [Ramda](https://ramdajs.com). These libraries include composable functions (not array prototype methods) that are extremely useful once you get familiar with them. 

One such function that I am sad is not a prototype method is `zip`. `Zip` takes two or more arrays and combines them into new items, one element from each array and halting at the point of the shortest array. For example:

```javascript
const arr1 = ["a", "b", "c"]
const arr2 = [1, 2, 3, 4]
const arr3 = [10, 20, 30, 40, 50]
_.zip(arr1, arr2, arr3)
// [["a", 1, 10], ["b", 2, 20], ["c", 3, 30]]
```

> The above uses the version of zip from Lodash (which allows more than two arrays to be zipped together--Ramda is limited to two arrays).

These sorts of specialized array methods can be implemented using `reduce` but it requires a non-trivial amount of work (not to mention edge cases that need to be considered). It is therefore wise to turn to a well tested utility library if you wish to code in this style.

## Recursion

Another approach to replacing loops is to use `recursion` (the repeated call of the same function by itself). The approach is requires knowing that your function can call itself from within its own definition. This could happen infinitely if you don't provide a stopping condition (similar to the stopping condition of a loop). 

As an example, we could code our `FizzBuzz` function as follows:

```javascript
function recurFB(nums, acc = []) {
  let [num, ...rest] = nums
  
  if (!nums.length) return accumulator 
  if (isFactorOf(15)(num)) return recFB(rest, [...acc, "FizzBuzz"])
  if (isFactorOf(3)(num)) return recFB(rest, [...acc, "Fizz"])
  if (isFactorOf(5)(num)) return recFB(rest, [...acc, "Buzz"])
  return recFB(rest, [...acc, num])
}
```

Unfortunatly, recursion has some limitations in Javascript. Chiefly, the current implementation in all major browsers and Node versions do not do what is known as `tail-call optimization`. 

When a function executes, it creates an execution context which establishes an alotment of memory for variables within the execution block of the function. Each call of a function creates such an execution scope, and so recursive function calls create a new execution context for each recursive call. As you may imagine, the more recursive calls, the more memory alotted. And at a certain point, this [can lead to the runtime crashing](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Too_much_recursion).

The problem is that a function which calls itself in its body doesn't "finish" at that point and so its allocated system resources are not released. You may think to yourself "that's silly, the work is done". If you refer to the example implementation of a recursive `FizzBuzz`, you will see that there really isn't any work left *except* to recursively call itself. This is not always true but in this example I have defined the function in a way that is `tail-call optimized`. This means that all of the work of the function is completed *but for* a final call to execution of the function. 

You can imagine that *in theory*, if the runtime could detect this, it could execute the recursive call in a separate context (not nested within the parent function) and release the resources allocated to the parent caller. This is known as `tail-call optimization` and many languages do this. [Node even implemented it for a few versions but then removed it.](https://javascript.plainenglish.io/tail-calls-in-javascript-will-there-be-a-comeback-63ac3a0523a5)

So is there a workaround? Yes, but arguably it makes the whole exercise look a lot more like a loop. One solution I've hear referred to as a [recursive "trampoline"](https://blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3/). That is, the recursive call isn't truly a recursive call but rather a plain function call whereby the parent simply orchestrates the accumulation of each *successive* calls to the quasi-recursive function. Let's consider our above example.

First, we have to implement a `trampoline` utility function. This function is general enough that it can be used for all recursive functions that follow the trampline-pattern. The recursive function must then be modified slightly, returning an anonymous function which will, upon execution, call the next iteration with the appropriate arguments (stored in the anonymous function's closure scope).

```javascript 
const trampoline = fn => (...args) => {
  let result = fn(...args)
  while (typeof result === 'function') {
    result = result()
  }
  return result
}

function recurFB(nums, acc = []) {
  let [num, ...rest] = nums
  
  if (!nums.length) return accumulator 
  if (isFactorOf(15)(num)) return () => recFB(rest, [...acc, "FizzBuzz"])
  if (isFactorOf(3)(num)) return () => recFB(rest, [...acc, "Fizz"])
  if (isFactorOf(5)(num)) return () => recFB(rest, [...acc, "Buzz"])
  return () => recFB(rest, [...acc, num])
}

// Notice that each iteration returns a function expression 
// rather than immediately executing 
```

Here we return a function from each pseudo-recursive call. In the `trampoline` function, we test whether the return value is a function and if so, execute it in a new context (freeing the resources from the prior call to be garbage collected). Finally we return the non-function value at the terminal case of our recursion.

> But what if your "final" value is a function itself, just not the same function? 🧐

While recursion can be useful and elegant in many cases, it needs to be noted that this limitation exists in Javacript. Many times the context will not practically conflict with this limit but if your solution needs to be general then it is probably wise to prepare your function to avoid this limitation (either by using a loop or expressing your recursion as a trampoline-style function).

## Conclusion

Loops and the array methods/functions described above both tackle the same category of problems. But is one interchangable for the other? Can we simply prefer one approach and disregard the other? In short, loops are the abstraction over even lower-level computing operations that we don't contend with in Javascript. And loops are the building blocks in which the array-functions are constructed. Knowing these array-functions gives us access to convenience and "cleaner code" when it is appropriate, while loops give us flexibility and optimization when it is required. 

One such occassion where we cannot simply choose an array method is when our "set" is indeterminate. For example, above we provided an example where we looped from 1 to Infinity in order to sum values to a certain target. Because you cannot create an array from 1 to Infinity, a loop would be a simple solution to this problem while an array method would not. 

> While an array from 1 to Infinity is not possible, it should be noted that the problem as stated doesn't strictly require a computation across values from 1 to Infinity, but rather from 1 to an indeterminate end value. A [generator function](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators) which iterates by one is an available tool that could be used to accomplish this challenge but requiring more language features not discussed in this article.

It is sometimes pointed out that one characteristic of Javascript loops excels over (built-in) array-methods: performance. While this may prove to be a true problem in your usage case, it is important that you verify that this is the source of your issue through measurement before hastily optimizing for this stated-purpose. The tradeoff is "noisier" code which is more difficult to maintain and less pleasant to work with. 

If performance turns out to be a true problem, you can also count on the fact that the utility libraries which provide these functions (such as [Lodash](https://lodash.com) and [Ramda](https://ramdajs.com)) avoid such criticism. These libraries implement their functions as abstractions over loops with performance optimizations in mind.

Another apparent shortcoming of these array functions is the inability or inflexibility of short-ciruiting (as is available with the `break` and `continue` keywords in a loop). It is true that this is not available in the built in array-methods, such as `map`, `filter`, and `reduce`. The consequence of this is that these methods will traverse the entire array, and we may need to add "bypass" code in order to get the intended behaviour. 

For example, say that we want to accumulate a list of names in an array of people, but want to stop if the number of results exceeds some value. Two possible options:

```javascript 
const findSomeWithName = (people, name, limit) => 
  people
    .findAll(person => person.name == name)
    .slice(0, limit)

const findSomeWithName2 = (people, name, limit) => 
  people.reduce((acc, person) => {
    if (acc.length >= limit) return acc
    if (person.name == name) return [...acc, person]
    return acc
  }, [])

```

In both cases, we traverse the entire array, even if we reach our "end condition" very early. 

This criticism has a performance aspect and a readability/maintainability aspect. While the performance aspect is something to measure and is discussed above, the second concern isn't easily avoidable using the built in array-methods. 

Luckily, by adopting one of the mentioned utility libraries, this too is mostly a non-issue. As has been discussed in other parts of this article, these array-functions are abstractions that can take many forms. These common access patterns result in very particularized array-functions. For example, in `Ramda` there are `reduceWhile`, `takeWhile`, `dropWhile` variants that allow for tailored logic that halts upon a given condition. 

Rewriting the above could look like: 

```javascript
const hasName = (name) => (acc, person) =>
  person.name == name ? [...acc, person] : acc;
const lessThanLimit = (limit) => (accumulator) => accumulator.length < limit;
const findSomeWithName = (people, name, limit) => 
  reduceWhile(lessThanLimit(limit), hasName(name), [], people)
;
```

> If the style of this code looks like Greek to you, you may be interested in my article on [Point-Free Style Programming](https://dev.to/justin_m_morgan/point-free-style-in-javascript-43o9)

Abstractions for other types of short-circuiting behaviours can be implemented, derived from combinations of other functions, or will perhaps be included in these popular libraries. Whether you want to go down that path is a matter of preference. Just recognize that this "short-circuiting" behaviour is not an inherent limitation of using array-methods. 

Similarly, recursion can tackle the same category of problems as loops and array-functions but (at least in Javascript) suffer from memory-limitations that can crash your program and still require implementing logic manually (unlike using a utility library, such as Lodash or Ramda).

By becoming comfortable in all three approaches to working with collections, Javascript allows you to have a hybrid approach to any given problem that fits your (or your team's) preferred style of coding.