sum of an array using recursion Javascript
21,523
Solution 1
A one-liner that meets all your requirements:
var sum = function(array) {
return (array.length === 0) ? 0 : array[0] + sum(array.slice(1));
}
// or in ES6
var sum = (array) => (array.length === 0) ? 0 : array[0] + sum(array.slice(1));
// Test cases
sum([1,2,3]); // 6
var s = [1,2,3];
sum(s); // 6
sum(s); // 6
Reasoning
- In a recursive call, you need to model your task as reduction to a base case. The simplest base case in this case is the empty array - at that point, your function should return zero.
- What should the reduction step be? Well you can model a sum of an array as the result of adding the first element to the
sum
of the remainder of the array - at some point, these successive calls will eventually result in a call tosum([])
, the answer to which you already know. That is exactly what the code above does. -
array.slice(1)
creates a shallow copy of the array starting from the first element onwards, and no mutation ever occurs on the original array. For conciseness, I have used a ternary expression.
Breakdown:
sum([1,2,3])
-> 1 + sum([2,3])
-> 1 + 2 + sum([3])
-> 1 + 2 + 3 + sum([])
-> 1 + 2 + 3 + 0
-> 6
Solution 2
You're on the right track, but consider that sum could take an optional second argument (that defaults to zero) that indicates the position to start summing from...
function sum(array, n) {
n ||= 0;
if (n === array.length) {
return 0;
} else {
return array[n] + sum(array, n + 1);
}
}
Author by
Wendy
Updated on August 19, 2020Comments
-
Wendy over 3 years
Looking for a way to solve this problem by recursing
sum()
. Right now, the code works, but I am supposed to callsum()
more than once, and it should not mutate the input array.var sum = function(array) { if(array.length === 0){ return 0; } function add(array, i){ console.log(array[i]); if(i === array.length-1){ return array[i]; } return array[i] + add(array, i+1); } return add(array, 0); }; sum([1, 2, 3, 4, 5, 6]) //21
-
Alnitak almost 8 yearsthere is no advantage to a binary approach - the number of recursive calls and additions is still
O(n)
. -
Alnitak almost 8 yearsalso taking array slices means that the program uses a lot more memory than required
-
Alnitak almost 8 yearsthe first solution is indeed elegant, but it's not the recursion that the OP has been asked for.
-
kidwon almost 8 yearsWhat is
n ||= 0;
doing? Is it short forn = n || 0
? -
Alnitak almost 8 years@kidwon yes - alternatively use
if (n === undefined) n = 0;
-
Prune almost 8 yearsThe advantage is that OP has a requirement to call sum more than once. That's the only reason I used the binary approach. Otherwise, taking advantage would require multi-threading, which would only bear fruit with very large arrays.
-
Wendy almost 8 yearsLove this! Clean and simple. Thank you so much!
-
Wendy almost 8 yearsis
n || = 0
ES6? It's so useful -
Iven Marquardt almost 8 yearsThis is mixing of concerns. Your function is less reusable.
sum
should just do what it claims to do, namely adding something up. If you want to skip the first x elements, just slice the array before passing it tosum
. -
Nellie Danielyan about 5 yearsThis doesn't use recursion which the OP has asked for
-
Scott Sauyet over 3 yearsWhat advantage does that have over the accepted answer? I see a significant disadvantage in that it destroys the array you're trying to sum.