Recursion - Sum Nested Array

Question

I'm trying to sum a nested array [1,2,[3,4],[],[5]] without using loops but I don't see what's wrong with what I have so far.

function sumItems(array) {
  let sum = 0;
  array.forEach((item) => {
    if (Array.isArray(item)) {
      sumItems(item);
    } else {
      sum += item;
    }
  });
  return sum;
}

Answer 1

try with

 function sumItems(array) {

  let sum = 0;
  array.forEach((item) => {
    if(Array.isArray(item)) {
     sum += sumItems(item);
    } else {
    sum += item;
    }
  })
  return sum;
}

Answer 2

recursion is a functional heritage

Recursion is a concept that comes from functional style. Mixing it with imperative style is a source of much pain and confusion for new programmers.

To design a recursive function, we identify the base and inductive case(s).

• base case - the list of items to sum is empty; ie, item is Empty. return 0
• inductive case 1 - the list of items is not empty; ie, there must be at least one item. if the item is a list, return its sum plus the sum of the rest of the items
• inductive case 2 - there is at least one item that is not an array. return this item plus the sum of the rest of the items

const Empty =
  Symbol ()

const sumDeep = ([ item = Empty, ...rest ] = []) =>
  item === Empty
    ? 0
    : Array.isArray (item)
      ? sumDeep (item) + sumDeep (rest)
      : item + sumDeep (rest)

console.log
  ( sumDeep ([ [ 1, 2 ], [ 3, 4 ], [ 5, [ 6, [] ] ] ]) // 21
  , sumDeep ([ 1, 2, 3, 4, 5, 6 ])                     // 21
  , sumDeep ([])                                       // 0
  , sumDeep ()                                         // 0
  )

As a result of this implementation, all pain and suffering are removed from the program. We do not concern ourselves with local state variables, variable reassignment, or side effects like forEach and not using the return value of a function call.

---

recursion caution

And a tail-recursive version which can be made stack-safe. Here, we add a parameter cont to represent our continuation which effectively allows us sequence the order of + operations without growing the stack – changes in bold

const identity = x =>
  x

const sumDeep = ([ item = Empty, ...rest ] = [], cont = identity) =>
  item === Empty
    ? cont (0)
    : Array.isArray (item)
      ? sumDeep (item, a =>
         sumDeep (rest, b =>
           cont (a + b)))
      : sumDeep (rest, a =>
          cont (item + a))

Usage is identitcal

console.log
  ( sumDeep ([ [ 1, 2 ], [ 3, 4 ], [ 5, [ 6, [] ] ] ]) // 21
  , sumDeep ([ 1, 2, 3, 4, 5, 6 ])                     // 21
  , sumDeep ([])                                       // 0
  , sumDeep ()                                         // 0
  )

performance enhancement

As @גלעד ברקן points out, array destructuring syntax used above (eg ...rest) create copies of the input array. As demonstrated in his/her answer, an index parameter can be used which will avoid creating copies. This variation shows how the index technique can also be used in a tail-recursive way

const identity = x =>
  x

const sumDeep = (items = [], i = 0, cont = identity) =>
  i >= items.length
    ? cont (0)
    : Array.isArray (items [i])
      ? sumDeep (items [i], 0, a =>
          sumDeep (items, i + 1, b =>
            cont (a + b)))
      : sumDeep (items, i + 1, a => 
          cont (items [i] + a))

console.log
  ( sumDeep ([ [ 1, 2 ], [ 3, 4 ], [ 5, [ 6, [] ] ] ]) // 21
  , sumDeep ([ 1, 2, 3, 4, 5, 6 ])                     // 21
  , sumDeep ([])                                       // 0
  , sumDeep ()                                         // 0
  )

Answer 3

Here's a version without using loops:

function f(arr, i){
  if (i == arr.length)
    return 0;
 
  if (Array.isArray(arr[i]))
    return f(arr[i], 0) + f(arr, i + 1);
   
  return arr[i] + f(arr, i + 1);
}

console.log(f([1,2,[3,4],[],[5]], 0));

Answer 4

You could define a callback for using with Array#reduce, which check if an item is an array and uses this function again for that array.

function add(s, v) {
    return Array.isArray(v)
        ? v.reduce(add, s)
        : s + v;
}

var array = [1, 2, [3, 4], [], [5]];

console.log(array.reduce(add, 0));

Answer 5

You may do as follows;

var sumNested = ([a,...as]) => (as.length && sumNested(as)) + (Array.isArray(a) ? sumNested(a) : a || 0);

console.log(sumNested([1,2,3,[4,[5,[6]]],7,[]]));

The function argument designation [a,…as] means that when the function is fed with a nested array like [1,2,3,[4,[5,[6]]],7,[]] then a is assigned to the head which is 1 and as is assigned to the tail of the initial array which is [2,3,[4,[5,[6]]],7,[]]. The rest should be easy to understand.

Answer 6

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

Answer 7

This is similar to some of the other solutions but might be easier for some to read:

 function Sum(arr) {
   if (!arr.length) return 0;
   if (Array.isArray(arr[0])) return Sum(arr[0]) + Sum(arr.slice(1));
   return arr[0] + Sum(arr.slice(1));
 }

 console.log(Sum([[1],2,[3,[4,[5,[6,[7,[8,9,10],11,[12]]]]]]])) // 78