回到课程

对数字求和到给定值

重要程度: 5

编写一个函数 sumTo(n) 计算 1 + 2 + ... + n 的和。

举个例子:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

用三种方式实现:

  1. 使用循环。
  2. 使用递归,对 n > 1 执行 sumTo(n) = n + sumTo(n-1)
  3. 使用等差数列求和公式.

结果示例:

function sumTo(n) { /*... 你的代码 ... */ }

alert( sumTo(100) ); // 5050

P.S. 哪种解决方式最快?哪种最慢?为什么?

P.P.S. 我们可以使用递归来计算 sumTo(100000) 吗?

使用循环的解法:

function sumTo(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

使用递归的解法:

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

alert( sumTo(100) );

使用公式 sumTo(n) = n*(n+1)/2 的解法:

function sumTo(n) {
  return n * (n + 1) / 2;
}

alert( sumTo(100) );

P.S. 当然是公式解法最快。对任何数字 n,只需要进行 3 次运算,数学大法好!

循环的速度次之。在循环或递归方法里,我们对相同的数字求和,但是递归涉及嵌套调用和执行堆栈管理,这会消耗资源,所以它更慢一些。

P.P.S. JS 标准描述了一个「尾递归」优化:如果递归调用是函数的最后一步(比如上面的 sumTo),那么外部的函数就不再需要恢复执行,我们也就不再需要记录它的执行上下文了。这样的话 sumTo(100000) 是可以求解的。但是如果你的 JavaScript 引擎不支持这个优化,就会报错:超出最大栈深度,因为一般堆栈的大小是有限制的。