назад до уроку

Сума всіх чисел до даного

важливість: 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

Зробити 3 варіанти рішення:

  1. Використання циклу.
  2. Використання рекурсії, у випадку sumTo(n) = n + sumTo(n-1) для 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. Звичайно, формула є найшвидшим рішенням. Вона використовує лише 3 операції для будь-якого числа n. Математика допомагає!

Варіант з циклом є другим з точки зору швидкості. Як і у випадку рекурсії, в циклі ми сумуємо ті ж числа. Але рекурсія передбачає вкладені виклики та управління стеком. Це також займає ресурси, тому це повільніше.

P.P.S. Деякі рушії підтримують оптимізацію “хвостового виклику” (tail call): якщо рекурсивний виклик є останнім в функції (як у випадку з sumTo), то зовнішня функція не повинна відновлювати виконання, отже рушію не потрібно запам’ятовувати контекст виконання. Це зменшує використання пам’яті, тому підрахунок sumTo(100000) стає можливим. Але якщо рушій JavaScript не підтримує оптимізацію хвостового виклику (більшість з них не підтримує), то виникне помилка: максимальний розмір стека перевищиться, оскільки зазвичай є обмеження на загальний розмір стека.