DEV Community

Codeguage
Codeguage

Posted on

JavaScript Interview Question: Compute the Sum of a List of Numbers, Recursively

Table of contents


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 to this basic task which can make it worthy of being asked in an interview setting.

Did I mention that such a question has 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 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, your understanding of recursion, and how to reduce a problem to a similar sub-problem.

And that's precisely what the interviewer is interested in knowing when testing you with such a question (that builds 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 that is 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]:

Visualization of sumRecursive([10, 2, 5])
Visualization of sumRecursive([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.

💡 Notice: Speaking precisely, we can also just have the empty array as the single base case instead of having two base cases.

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));
}
Enter fullscreen mode Exit fullscreen mode

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:

Output:

>> 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
Enter fullscreen mode Exit fullscreen mode

Perfect!

So how was this blend of spice?


More spice

Wait a second...

There is one other spice that could be further added to this simple problem and that is tied to keeping from slicing the array for the sake of recursion.

Notice that when we recursively invoke sumRecursive(), we call nums.slice(1). This part makes a copy of the array from its second element to the very end. This copying makes for an inefficient implementation.

We can actually alleviate this if we slightly modify the way we model the subarray.

As they say "It's all about perspective."

If you're interested in seeing what this modification is (because well, this could be a question in your next interview) and want to solve this improvised problem, head over to the JavaScript Functions — Efficient Recursive Sum exercise.


Top comments (0)