How to compute the sum of a list of numbers in JavaScript, recursively?

As you'll agree, computing the sum of an array of numbers is no difficult feat. Just iterate over the array, add each element to an aggregate variable (often named as total or sum), and then return the aggregate in the end. Super super simple, right?

But there is some spice that could be sprinkled on top of this basic task to make it worthy of being asked in an interview setting. Did I mention that such a question has actually been asked in a JavaScript interview as stated by a candidate on Glassdoor? Anyways, let's open up the spice cabinet...

Recursive sum

And the spice is recursion. Are you scared of recursion? Well, it's a fact that many people are so.

Computing the sum of an array of numbers via iteration (typically using a for loop) is pretty straightforward. A slightly more involved task is to do so using recursion.

If you can easily solve this problem, it clearly demonstrates your problem-solving ability and your understanding of recursion. And that's precisely what the interviewer is interested in knowing when testing you with such a question (building upon a previous, often easier, question).

So the idea is to create a function sumRecursive() that takes in an array and returns back its sum, computed via recursion.

Think about it for a while, try implementing it on your own, and then we'll walk through the solution to this problem together in the next section.

The solution

Solving a problem via recursion boils down to essentially two things:

• A recursive case which is a smaller version of the original problem.
• A base case which is a scenario where we can answer rightaway without having to resort to a recursion.

The recursive case is where we ramify the original problem into a smaller problem, similar in nature. This ramification means that with each subproblem, we get closer and closer to a direct answer instead of another recursion.

Speaking of which, when our subproblem becomes so small that it could be solved rightaway with a direct answer, we have our base case.

For the recursive sum problem we're solving at the moment, the recursive case is to take the first element of the given array and add it to the sum of the subarray starting at index 1 and going all the way to the end.

Visually, something like this, for the array [10, 2, 5]:

For computing the recursive sum of [10, 2, 5], we add 10 to the recursive sum of [2, 5]. Clearly, computing the sum of the subarray with one less element is a smaller problem, similar in nature to the original problem.

So that's the recursive case.

The base cases are also pretty easy to enumerate:

• When we have an empty array, the sum is 0.
• When we have an array with just one element, the sum is that very element.

Altogether, we get to the following code:

function sumRecursive(nums) {
   if (! nums.length) {
      return 0;
   }
   if (nums.length === 1) {
      return nums[0];
   }
   return nums[0] + sumRecursive(nums.slice(1));
}

Notice how, in order to recursively invoke sumRecursive() with a smaller array, we leverage the array slice() method, slicing from index 1 to the very end.

It's now time to test this function on a couple of arrays and see whether our intuition hits correctly or not:

sumRecursive([10, 2, 5]); // 17
sumRecursive([10]); // 10
sumRecursive([]); // 0
sumRecursive([0.5, 1, 1]); // 2.5
sumRecursive([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); // 55

Perfect! It indeed hits correctly!

More spice

Wait a second... There is another spice that could be further added to this simple problem and that is to prevent making a copy of the array during the recursion.

Currently, before invoking sumRecursive() in the recursive case, we call nums.slice(1) in order to make a copy of the array from its second element to the very end. This is clearly inefficient.

How can you prevent it? What can you do to provide the function with a subarray but not actually make a copy? Think about a different way of modeling the subarray. As they say It's all about perspective.