Why does recursion return an empty array with this javascript algorithm?

Question

Question

Let us consider this example (array written in general format):

ls = [0, 1, 3, 6, 10]

The corresponding sums are (put together in a list):

[20, 20, 19, 16, 10, 0]

The function parts_sums (or its variants in other languages) will take as parameter a list ls and return a list of the sums of its parts as defined above.

Other Examples

ls = [1, 2, 3, 4, 5, 6] 
parts_sums(ls) -> [21, 20, 18, 15, 11, 6, 0]

ls = [744125, 935, 407, 454, 430, 90, 144, 6710213, 889, 810, 2579358]
parts_sums(ls) -> [10037855, 9293730, 9292795, 9292388, 9291934, 9291504, 9291414, 9291270, 2581057, 2580168, 2579358, 0]

My Attempt

function partsSums(ls) {
    let newArr = [];

    if(ls.length == 0){
      return newArr;
    }

    let summedNum = ls.reduce((total, item)=>{
       let totalledNum = total + item;
       return totalledNum;
    })
    newArr.push(summedNum);

    let [a, ...rest] = ls;
    ls = rest;

    return partsSums(ls)
    
}

console.log(partsSums([0,1,3,6,10]))

The current algorithm returns an empty array. Why is this, and what can I do to fix it?

Have you tried to add logs to understand what's going on? A little hint: `newArr` is never used again or returned.. (except when `partsSums` finally gets called with an empty array) — Kaddath, Aug 07 '20 at 11:53
Step through `partsSums([0])`. What happens in the two calls for `partsSums()` and what is its return value? — Andreas, Aug 07 '20 at 11:54

score 1 · Accepted Answer · answered Aug 07 '20 at 11:56

1

You're returning an empty array when you reach your end condition (ls.length == 0), because you always create a new array. You should probably have the array as part of the input arguments of your function "partsSum".

answered Aug 07 '20 at 11:56

Mick

837
8
23

1

I am going to accept this answer, as it was what I needed to solve the problem. But if anyone wants to see the fix, then I will post it below. – AndrewNeedsHelp Aug 07 '20 at 12:02

score 1 · Answer 2 · answered Aug 07 '20 at 12:02

1

function partsSums(ls, newArr = []) {
    

    if(ls.length == 0){
      newArr.push(0);
      return newArr;
    } 

    let summedNum = ls.reduce((total, item)=>{
       let totalledNum = total + item;
       return totalledNum;
    })
    
    newArr.push(summedNum);

    let [a, ...rest] = ls;
    ls = rest;

    return partsSums(ls, newArr)
    
}

console.log(partsSums([0,1,3,6,10]))

answered Aug 07 '20 at 12:02

AndrewNeedsHelp

385
4
15

2

`let [a, ...rest] = ls; ls = rest; return partsSums(ls, newArr);` -> `return partsSums(ls.slice(1), newArr)` – Andreas Aug 07 '20 at 12:09

score 1 · Answer 3 · answered Aug 07 '20 at 12:06

With let [a, ...rest] = ls; you are stripping the first element from the array and returning it. So when you hit the check ls.length==0 at entry into the function you return an empty array and recursion stops.

You need to track the sums as well and return the array containing those from the function. The following approach works:

function partsSums(ls, itemSums) {
    if(ls.length == 0){
      return itemSums;
    }
    
    let summedNum = ls.reduce((total, item)=>{
       let totalledNum = total + item;
       return totalledNum;
    });

    let [a, ...rest] = ls;
    ls = rest;

    return partsSums(ls, [...itemSums, summedNum])
}

console.log(partsSums([0,1,3,6,10], []))

3limin4t0r · Answer 4 · 2020-08-07T13:10:04.860

The reason the current solution returns an empty array is because you create a new newArr every iteration. When using recursion you should either pass the results on the the next recursion call or combine the result of the recursion call with something in the current method.

Without changing much of your code the following changes fix most of your problem:

// move newArr from an inner variable to a parameter
function partsSums(ls, newArr = []) {
    if(ls.length == 0){
      return newArr;
    }

    let summedNum = ls.reduce((total, item)=>{
       let totalledNum = total + item;
       return totalledNum;
    })
    newArr.push(summedNum);

    let [a, ...rest] = ls;
    ls = rest;

    // pass the current result to next recurring call
    return partsSums(ls, newArr)
}

console.log(partsSums([0,1,3,6,10]))

This does not entirely solve your issue since you are still missing the 0 value in the result.

Your current version also sums the contents of ls multiple times, each iteration one less than the one before. Say I provided an ls of length 10. You first iteration would go through all 10 elements and sum them (using reduce), the second iteration would go through 9 elements and sum them, etc. Resulting in 10 + 9 + 8 + ... = 55 iterations.

Instead of summing al resulting elements get the result of those elements first. Then use the first element in the result, since that contains the newest sum.

Here are 2 examples:

// "normal" recursion
function partsSumsA(ls) {
    if (ls.length == 0) return Array.of(0);
    
    const [nr, ...nrs] = ls;
    const sums = partsSumsA(nrs);
    
    return [nr + sums[0], ...sums];
}

// tail-recursion
function partsSumsB(ls, sums = Array.of(0)) {
  if (ls.length == 0) return sums;
  
  // const [...nrs, nr] = ls;
  const nrs = ls.slice(0, -1);
  const nr  = ls[ls.length - 1];
  
  return partsSumsB(nrs, [nr + sums[0], ...sums]);
}

console.log(...partsSumsA([0,1,3,6,10]));
console.log(...partsSumsB([0,1,3,6,10]));

For additional info about tail-recursion see: What is tail recursion?

Why does recursion return an empty array with this javascript algorithm?

4 Answers4