Loops, Array Methods, and Recursion

"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:

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.

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".

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:

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. 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:

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).

A for...of solution could look like:

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)

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

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:

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:

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,
• map,
• filter, and
• 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.

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 function for an arbitrary array of numbers:

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:

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:

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:

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):

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 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:

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):

// 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.

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 and (for even more extreme examples) Ramda. 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:

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:

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.

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.

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". 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).

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 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 and Ramda) 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:

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:

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

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.