使用递归Javascript计算数组的总和

Question

希望通过递归sum()来解决这个问题。现在，代码可以运行，但我应该多次调用sum()，并且不应该改变输入数组。

var sum = function(array) {
    if(array.length === 0){
        return 0;
    }
    function add(array, i){
        console.log(array[i]);
        if(i === array.length-1){
            return array[i];
        }
        return array[i] + add(array, i+1);
    }
    return add(array, 0);
};
sum([1, 2, 3, 4, 5, 6]) //21

- Wendy

---

我相信你（们）正在寻找的是 function sum(array) { return array.length ? array[0] + sum(array.slice(1)) : 0; }。 - Bergi

@Bergi 这是一个可能的答案，但我不认为一个好的答案应该复制数组的任何部分。 - Alnitak

@Alnitak 为什么？这不是由 OP 规定的要求。这是一个相当基本的问题，旨在帮助 OP 理解递归。寻求最有效的解决方案会忽略重点 - 在这种情况下，紧凑和清晰应该是更好的目标。 - Akshat Mahajan

@Alnitak：我认为这比给sum添加一个额外的可选参数更好（更纯粹）:-) - Bergi

Answer 1

一个符合您所有要求的一行代码：

var sum = function(array) {
    return (array.length === 0) ? 0 : array[0] + sum(array.slice(1));
}

// or in ES6

var sum = (array) => (array.length === 0) ? 0 : array[0] + sum(array.slice(1));

// Test cases
sum([1,2,3]); // 6

var s = [1,2,3];
sum(s); // 6
sum(s); // 6

推理

• 在递归调用中，您需要将任务建模为对基本情况的缩减。在这种情况下，最简单的基本情况是空数组-此时，您的函数应返回零。
• 那么，缩减步骤应该是什么？嗯，你可以将数组的总和建模为将第一个元素与其余数组的sum相加的结果——在某些点上，这些连续的调用最终将导致对sum([])的调用，而您已经知道其答案。那正是上面的代码所做的。
• array.slice(1) 创建从第一个元素开始直到末尾的数组的浅拷贝，原始数组上永远不会发生变化。为了简洁起见，我使用三元表达式。

分解:

sum([1,2,3])
-> 1 + sum([2,3])
-> 1 + 2 + sum([3])
-> 1 + 2 + 3 + sum([])
-> 1 + 2 + 3 + 0
-> 6

- Akshat Mahajan

Answer 2

你已经朝着正确的方向迈进，但需要考虑到 sum 函数可能会有一个可选的第二个参数（默认为零），用于指定从哪个位置开始求和...

function sum(array, n) {
    n ||= 0;
    if (n === array.length) {
        return 0;
    } else {
        return array[n] + sum(array, n + 1);
    }
}

- Alnitak

---

“n ||= 0;”是什么意思？它是“n = n || 0”的缩写吗？ - kidwon

@kidwon 是的 - 或者使用 if (n === undefined) n = 0; - Alnitak

n ||= 0 是 ES6 吗？它非常有用。 - Wendy

这是关注点混杂。你的函数可重用性较低。sum 应该只做它所声称的事情，即将一些东西相加。如果你想跳过前 x 个元素，在将其传递给 sum 之前，只需对数组进行切片即可。 - user5536315

Answer 3

function sumNumbersRecursively(input){
    if (input.length == 0){
        return 0;
    } else{
       return input.shift() + sumNumbersRecursively(input);
    }
}

console.log(sumNumbersRecursively([2,3,4]))

- C Williams

---

这种方法与接受的答案相比有什么优势？我认为它有一个显著的缺点，即会破坏你想要求和的数组。 - Scott Sauyet

Answer 4

arr = [1,2,3,4]
sum = arr.reduce((acc, curr)=> acc+curr)

数组 = [1,2,3,4]
总和 = 数组.reduce((累加器, 当前值)=> 累加器+当前值)

- deepak_pal

---

这不使用递归，而这正是原帖中所要求的。 - Nellie Danielyan

Answer 5

你实际上不需要在你的求和函数中添加add函数，只需将函数内联并以0作为起点初始化，或者可选地检查i变量是否未定义并将其初始化为0！

var sum = function(array, i) {
    if(array.length === 0){
        return 0;
    }
  console.log(array[i]);
  if(i === array.length-1){
    return array[i];
  }
  return array[i] + sum(array, i+1);
};
console.log(sum([1, 2, 3, 4, 5, 6],0)) //21

- 42shadow42

Answer 6

你有两个解决方案：

• 你可以使用.reduce()方法
• 或者执行一个简单的尾递归

使用reduction：

function sum(a, b) {
  return a + b;
}

const array = [1, 2, 3, 4, 5, 6];

//In our reduce, we will apply our sum function, 
//and pass the result as the next value
const res = array.reduce(sum);

使用递归：

function sumRec(array, acc = 0, index) {
    //We will update our accumulator, and increment
  // the value of our current index
  return index === array.length
  ? acc
  : sumRec(array, acc += array[index], ++index);
}

console.log(sumRec(array, 0, 0));

个人而言，我认为第一种解决方案更加优雅。

- Paul Boutes

---

第一种解决方案确实很优雅，但它并不是 OP 被要求使用的递归。 - Alnitak

Answer 7

function sumArr(arr){
  if(arr.length>1){
    return arr.pop()+sumArr(arr);
  }else{
    return arr[0];
  }
}

- Hossein Rezaei

Answer 8

如果您需要多次调用sum，则使用二进制方法：将数组分成两半并对每个部分进行递归。当长度为1时，返回单个值。

这对您有用吗？恐怕我不记得JS语法中的数组切片，因此我的递归语句可能在细节上有误。

var sum = function(array) {
    if(array.length === 1){
        return array[0];
    }
    mid = array.length / 2
    return sum(array[0:mid-1]) + sum(array[mid:array.length-1])
};
sum([1, 2, 3, 4, 5, 6]) //21

- Prune

---

采用二进制方法并没有优势 - 递归调用和加法的数量仍然是O(n)。 - Alnitak

同时，使用数组切片意味着程序使用的内存比所需的要多得多。 - Alnitak

优点在于OP需要多次调用sum函数。这就是我使用二进制方法的唯一原因。否则，利用多线程才能发挥作用，而这只有在非常大的数组中才会产生效果。 - Prune