Почему рекурсия возвращает пустой массив с этим алгоритмом javascript?

Question

Вопрос

Рассмотрим этот пример (массив, записанный в общем формате):

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

Соответствующие суммы (объединены в список):

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

Функция parts_sums (или ее варианты на других языках) примет в качестве параметра список ls и вернет список сумм его частей, как определено выше.

Другие примеры

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]

Моя попытка

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]))

Текущий алгоритм возвращает пустой массив. Почему это так и что я могу сделать, чтобы это исправить?

Answer 1

Причина, по которой текущее решение возвращает пустой массив, состоит в том, что вы создаете новый newArr на каждой итерации. При использовании рекурсии вы должны либо передать результаты при следующем вызове рекурсии, либо объединить результат вызова рекурсии с чем-то в текущем методе.

Без изменения большей части вашего кода следующие изменения устраняют большую часть вашей проблемы :

// 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]))

Это не полностью решает вашу проблему, так как вам все еще не хватает значения 0 в результате.

Текущая версия также суммирует содержимое ls несколько раз, каждая итерация на одну меньше предыдущей. Скажем, я предоставил ls длины 10. Первая итерация будет go через все 10 элементов и суммировать их (используя reduce), вторая итерация будет go через 9 элементов и суммировать их, et c . Результат: 10 + 9 + 8 + ... = 55 итераций.

Вместо того, чтобы суммировать все результирующие элементы, сначала получите результат этих элементов. Затем используйте первый элемент результата, так как он содержит самую новую сумму.

Вот 2 примера:

// "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]));

Для получения дополнительной информации о хвостовой рекурсии см .: Что такое хвостовая рекурсия?

Answer 2

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]))

Answer 3

С let [a, ...rest] = ls; вы удаляете первый элемент из массива и возвращаете его. Поэтому, когда вы нажимаете проверку ls.length==0 при входе в функцию, вы возвращаете пустой массив, и рекурсия останавливается.

Вам также необходимо отслеживать суммы и возвращать массив, содержащий их из функции. Работает следующий подход:

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], []))

Answer 4

Вы возвращаете пустой массив по достижении конечного условия (ls.length == 0), потому что вы всегда создаете новый массив. Вероятно, у вас должен быть массив как часть входных аргументов вашей функции partsSum.