torna alle lezioni

Sommare tutti i numeri fino a quello dato

importanza: 5

Scrivete una funzione sumTo(n) che calcola la somma dei numeri 1 + 2 + ... + n.

Ad esempio:

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

Scrivete 3 diverse varianti della soluzione:

  1. Utilizzando un ciclo for.
  2. Utilizzando la ricorsione, poiché sumTo(n) = n + sumTo(n-1) per n > 1.
  3. Utilizzate la formula della progressione aritmetica.

Un esempio:

function sumTo(n) { /*... your code ... */ }

alert( sumTo(100) ); // 5050

P.S. Quale soluzione risulta essere la più rapida? La più lenta? Perché?

P.P.S. Possiamo utilizzare la ricorsione per calcolare sumTo(100000)?

La soluzione che utilizza il ciclo:

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

alert( sumTo(100) );

La soluzione ricorsiva:

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

alert( sumTo(100) );

La soluzione che sfrutta la formula: sumTo(n) = n*(n+1)/2:

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

alert( sumTo(100) );

P.S. Naturalmente, la formula risulta essere la soluzione più rapida. Arriva al risultato con solamente 3 operazioni, qualsiasi sia n. La matematica serve!

La soluzione che utilizza il ciclo è la seconda in termini di velocità. Sia nella soluzione ricorsiva che in quella iterativa sommiamo gli stessi numeri. La ricorsione però coinvolge un gran numero di chiamate annidate e richiede una gestione dei contesti d’esecuzione. Richiede molte più risorse, questo la rende più lenta.

P.P.S. Lo standard descrive un ottimizzazione: se la chiamata ricorsiva è l’ultima cosa che avviene nella funzione (come in sumTo), allora la funzione esterna non ha alcuna necessita di riprende l’esecuzione e non c’è quindi bisogno di memorizzare il contesto d’esecuzione In questo particolare caso sumTo(100000) viene risolta. Ma se il motore JavaScript non lo supporta, ci sarà un errore: “maximum stack size exceeded”, che indica il raggiungimento del massimo numero di esecuzioni annidate.