Вернуться к уроку

Вычислить сумму чисел до данного

важность: 5

Напишите функцию sumTo(n), которая для данного n вычисляет сумму чисел от 1 до 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. Через рекурсию, т.к. sumTo(n) = n + sumTo(n-1) для n > 1.
  3. С использованием формулы для суммы арифметической прогрессии.

Пример работы вашей функции:

function sumTo(n) { /*... ваш код ... */ }

alert( sumTo(100) ); // 5050

Какой вариант решения самый быстрый? Самый медленный? Почему?

Можно ли при помощи рекурсии посчитать sumTo(100000)? Если нет, то почему?

Решение с использованием цикла:

function sumTo(n) {
  var sum = 0;
  for (var 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, а цикл и рекурсия требуют как минимум n операций сложения.

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

Рекурсия в данном случае работает медленнее всех.

P.P.S. Существует ограничение глубины вложенных вызовов, поэтому рекурсивный вызов sumTo(100000) выдаст ошибку.