Array Reduce Sum Using Recursion

Question

Given an array of length n, consolidate the sum created by adding index pairs until there's only a single index.

EXAMPLES:

[1, 2, 3, 4, 5] => 48

Explanation:

The next array would be [3, 5, 7, 9] because [1+2, 2+3, 3+4, 4+5]
The next array would be [8, 12, 16] because [3+5, 5+7, 7+9]
The next array would be [20, 28] because [8+12, 12+16]
The final answer would be [48] because [20+28] and there are not enough operands to add

This is the solution I came up with but I feel like there's a simpler way to achieve the same solution. I'm trying to understand recursion but I need some explanation on why when we call our stacks, we do it from the (n - 1) or from the (n + 1) to reach our base cases and how do we know which one to use? I don't understand why we're using those passing arguments when we are returning our helper function.

function reduceSum(input) {
  function simplify(input, index) {
    if (index === 1) {
      return input[0];
    }

    if (index === 0) {
      return 0;
    }

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

    return simplify(input, index - 1);
  }

  return simplify(input, input.length);
}


console.log(reduceSum([1, 2, 3, 4]) == 20)
console.log(reduceSum([5]) == 5)
console.log(reduceSum([]) == 0)
console.log(reduceSum([1, 3, 5]) == 12)
console.log(reduceSum([-5, 5]) == 0)
console.log(reduceSum([-5, 5, -5, 5]) == 0)
console.log(reduceSum([-5, 5, 5, -5]) == 20)

An advice would be to just run the last array [-5, 5, 5, -5] and then do a console.log(input) after the for loop to see what happens to input. For each recursive loop, the last index will be NaN, hence why the code is calling simplify(input, index - 1). Tbh, this solution is much shorter than I would had come up with. — Rickard Elimää
– Rickard Elimää, Commented Jan 15, 2023 at 20:21

Ben Stephens · Accepted Answer · 2023-01-15 21:57:02Z

2

I'm not sure the following is a genuinely simpler way to achieve the solution as it does basically the same thing (although it does not modify the original array), but perhaps there's something useful here:

function reduceSum(input) {
  if(input.length <= 1)
    return input[0] || 0;
  
  return reduceSum(
    input.reduce(
      (acc, val, i, { [i + 1]: next }) =>
        typeof next !== 'undefined' ? [ ...acc, val + next ] : acc,
      []
    )
  );
}


console.log(reduceSum([1, 2, 3, 4]) == 20)
console.log(reduceSum([5]) == 5)
console.log(reduceSum([]) == 0)
console.log(reduceSum([1, 3, 5]) == 12)
console.log(reduceSum([-5, 5]) == 0)
console.log(reduceSum([-5, 5, -5, 5]) == 0)
console.log(reduceSum([-5, 5, 5, -5]) == 20)

The next variable is populated using object destructuring on the array argument passed to the reduce callback function. It will be undefined when the reduce method processes the last element of the array, this last element gets skipped; this means that each time we run reduceSum the array gets shorter by one element (as per your original).

edited Jan 15, 2023 at 21:57

answered Jan 15, 2023 at 21:23

Ben Stephens

3,3711 gold badge7 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

vanowm Over a year ago

You can more than double the speed of your method by not using spread, destructuring and using i to detect last item: (acc, val, i, next) => (i < next.length - 1 && (acc[i] = val + next[++i]), acc)

Sharon Kaufman Over a year ago

This is very useful to have to perform the task in-place. Thank you for sharing this with me!

Ben Stephens Over a year ago

Thank you @vanowm, that's some food for thought.

vanowm · Accepted Answer · 2023-01-15 22:30:24Z

Each loop updates values in the array. And with each loop the index needs to be reduced, otherwise it will be infinite loop. Just add console.log("" + input) right after the for loop and you'll see how input progresses with each call of simplify() function.

There are a few optimizations can be done to your code:

you don't need simplify() at all, simply check if index variable is undefined:

function reduceSum(input, index) {
  if (index === undefined)
    index = input.length;

  if (index === 1) {
    return input[0];
  }

  if (index === 0) {
    return 0;
  }

  for (let i = 0; i < input.length; i++) {
    input[i] += input[i + 1];
  }
  console.log("input:  " + input);
  return reduceSum(input, index - 1);
}

console.log("result:", reduceSum([1, 2, 3, 4, 5]) == 48)
console.log("result:", reduceSum([1, 2, 3, 4]) == 20)
console.log("result:", reduceSum([5]) == 5)
console.log("result:", reduceSum([]) == 0)
console.log("result:", reduceSum([1, 3, 5]) == 12)
console.log("result:", reduceSum([-5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, -5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, 5, -5]) == 20)

You can also optimize a little by only looping through 0 to index - 1 instead of entire array:

function reduceSum(input, index) {
  if (index === undefined)
    index = input.length;

  if (index === 1) {
    return input[0];
  }

  if (index === 0) {
    return 0;
  }

  for (let i = 0; i < index - 1; i++) {
    input[i] += input[i + 1];
  }
  console.log("input: " + input);
  return reduceSum(input, index - 1);
}

console.log("result:", reduceSum([1, 2, 3, 4, 5]) == 48)
console.log("result:", reduceSum([1, 2, 3, 4]) == 20)
console.log("result:", reduceSum([5]) == 5)
console.log("result:", reduceSum([]) == 0)
console.log("result:", reduceSum([1, 3, 5]) == 12)
console.log("result:", reduceSum([-5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, -5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, 5, -5]) == 20)

Further you can optimize the code by adding default value to the index variable and moving conditions to the end the function, this way it won't need an extra call of the function to get final result:

function reduceSum(input, index = input.length - 1) {
  for (let i = 0; i < index; i++) {
    input[i] += input[i + 1];
  }
  console.log("input: " + input);
  if (index > 1)
    return reduceSum(input, --index);

  //return final result or 0 if array is empty
  return input[0] || 0;
}

console.log("result:", reduceSum([1, 2, 3, 4, 5]) == 48)
console.log("result:", reduceSum([1, 2, 3, 4]) == 20)
console.log("result:", reduceSum([5]) == 5)
console.log("result:", reduceSum([]) == 0)
console.log("result:", reduceSum([1, 3, 5]) == 12)
console.log("result:", reduceSum([-5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, -5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, 5, -5]) == 20)

Finally, you can get rid of index all together, by removing last item from the input array instead, this method is slower than the above though:

function reduceSum(input) {
  for (let i = 0; i < input.length - 1; i++) {
    input[i] += input[i + 1];
  }
  console.log("input: " + input);
  if (input.length > 1)
  {
    //remove last item by reducing length of the array
    input.length--;
    return reduceSum(input);
  }
  //return final result or 0 if array is empty
  return input[0] || 0;
}

console.log("result:", reduceSum([1, 2, 3, 4, 5]) == 48)
console.log("result:", reduceSum([1, 2, 3, 4]) == 20)
console.log("result:", reduceSum([5]) == 5)
console.log("result:", reduceSum([]) == 0)
console.log("result:", reduceSum([1, 3, 5]) == 12)
console.log("result:", reduceSum([-5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, -5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, 5, -5]) == 20)

Ahhhh thank you so much for breaking that down so well for me! I think I finally understand it now. Great job!

PeterKA · Accepted Answer · 2023-01-16 10:46:38Z

0

You can use a for loop as follows:

function reduceSum(input) {
  if( input.length < 2 ) {
    return input[0] || 0;
  }
  const arr = [];
  for(let i = 0; i < input.length - 1; i++) {
    arr.push(input[i] + input[i+1]);
  }
  return reduceSum( arr );
}


console.log(reduceSum([1, 2, 3, 4]) == 20)
console.log(reduceSum([5]) == 5)
console.log(reduceSum([]) == 0)
console.log(reduceSum([1, 3, 5]) == 12)
console.log(reduceSum([-5, 5]) == 0)
console.log(reduceSum([-5, 5, -5, 5]) == 0)
console.log(reduceSum([-5, 5, 5, -5]) == 20)

answered Jan 16, 2023 at 10:46

PeterKA

24.7k5 gold badges28 silver badges52 bronze badges

Collectives™ on Stack Overflow

Array Reduce Sum Using Recursion

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related