Learning Recursion in JavaScript Part 2 - Sum an Array of Numbers 3 Ways

March 31, 2019

Ah, recursion, one of those intimidating programming topics that make many developers’ heads spin 🤯 . These types of problems can be difficult to conceptualize, especially when you’re under pressure during an interview. I know I’ve felt that before! Well, that’s why I am writing this blog post series on recursion, to help you and me learn it better. As I’ve spent more time learning about it, I’ve come to find it a fascinating topic and appreciate how elegantly you can use it to solve certain types of problems.

Here are the other posts in this series if you haven’t checked those out yet:

  1. The Obligatory Factorial Function
  2. Sum an Array of Numbers 3 Ways
  3. Flattening Arrays
  4. Palindromes

In the last post, The Obligatory Factorial Function, we learned that code implemented with loops can also be written with recursion. For this second post in this series on recursion, let’s look at an interview problem I was given once. The problem was, “Write a function that sums an array of numbers”.

My first implementation was using a standard for loop:

function sum(array) {
  let sum = 0;

  for (let i = 0; i < array.length; i++) {
    sum += array[i];
  }

  return sum;
}

sum([1, 2, 3, 4, 5]); // 15

Right after, I was asked, “Can you think of another way to sum an array of numbers without a loop?”. I solved it using Array.prototype.reduce:

function sum(array) {
  return array.reduce((sum, num) => sum + num, 0);
}

sum([1, 2, 3, 4, 5]); // 15

After this implementation, I was asked, “Can you think of one more way to sum an array of numbers without a loop or reduce?”. At the time, recursion hadn’t occurred to me. After 30 seconds of silence of me trying to think of another way, the interviewer said, “Are you familiar with recursion?”. I was, thankfully, and solved it with recursion:

function sum(array) {
  if (array.length === 0) {
    return 0;
  } else {
    return array[0] + sum(array.slice(1));
  }
}

sum([1, 2, 3, 4, 5]); // 15

In this implementation, the recursion happens in the else block, where the sum function calls itself. Each time sum is called, its argument is an array that leaves off the first element (index 0) via the splice() method on arrays. Thus, the array passed to sum continually gets smaller and smaller until it hits the base case where the array is empty and 0 is returned.

If we were to expand this call stack out, it would look like this:

sum([1, 2, 3, 4, 5]) = 1 + sum([2, 3, 4, 5])
sum([1, 2, 3, 4, 5]) = 1 + (2 + sum([3, 4, 5]))
sum([1, 2, 3, 4, 5]) = 1 + (2 + (3 + sum([4, 5])))
sum([1, 2, 3, 4, 5]) = 1 + (2 + (3 + (4 + sum([5]))))
sum([1, 2, 3, 4, 5]) = 1 + (2 + (3 + (4 + (5 + sum([])))))
sum([1, 2, 3, 4, 5]) = 1 + (2 + (3 + (4 + (5 + 0))))

We can also implement this without the slice() method and instead use destructuring and rest parameters:

function sum(array) {
  if (array.length === 0) {
    return 0;
  } else {
    let [head, ...tail] = array;
    return head + sum(tail);
  }
}

sum([1, 2, 3, 4, 5]); // 15

Conclusion

So there you have it, 3 ways to sum an array of numbers. I think most would agree that the simplest solution is using Array.prototype.reduce, but nevertheless this is another good exercise to illustrate how loops can implemented with recursion. Stay tuned for the next post in my series on recursion, as we’ll continue to look at more examples and facets of recursion.

Disclaimer: Any viewpoints and opinions expressed in this article are those of David Tang and do not reflect those of my employer or any of my colleagues.