Recursion: prefix sums

Question

I'm solving a CodeWars kata.

Link to the Kata

This is my code:

function partsSums(arr) {
    let bigSum = [];
    if (arr.length == 0) {
        bigSum.push(0);
    }

    while (arr.length >= 1) {
        let sum = arr.reduce((acc, ele) => acc + ele);
        bigSum.push(sum);
        partsSums(arr.shift());
    }

    return bigSum;
}

The correct answer should be: [20, 20, 19, 16, 10, 0]

My function returns: [ 20, 20, 19, 16, 10 ]

Please point out where I'm wrong or my misunderstanding. Thank you!

Answer 1

You could reduce from the right side and add the value the the value at index zero.

function partsSums(arr) {
    return arr.reduceRight((r, value) => [r[0] + value, ...r], [0]);
}

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

A speedy version

function partsSums(ls) {
    let l = ls.length,
        result = [];

    result[l] = 0;

    while (l--) result[l] = result[l + 1] + ls[l];

    return result;
}

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

Answer 2

The problem is that when your array reaches length 0 in the loop, you're not actually appending anything to bigSum. You can do that by explicitly adding it following your loop.

function partsSums(arr) {
    let bigSum = [];

    while (arr.length >= 1) {
        let sum = arr.reduce((acc, ele) => acc + ele);
        bigSum.push(sum);
        partsSums(arr.shift());
    }
    
    bigSum.push(0);

    return bigSum;
}
console.log(partsSums([0, 1, 3, 6, 10]));