Un algoritmo ricorsivo è una funzione che richiama se stessa. Questa tecnica ha pregi e difetti. Uno dei pregi più evidenti è la semplificazione della codifica e l'eleganza della soluzione. Uno dei difetti è insito nei meccanismi di elaborazione delle CPU, che devono salvare tutti i dati, poiché sta per essere chiamata la stessa funzione, che sporcherebbe i registri di calcolo.

Facciamo un esempio pratico immaginando di avere una classe con tanti banchi su cui c'è un lucido con un solo pennarello di colore diverso. Sono sul primo banco e inizio a disegnare il mio lucido con il colore rosso. Ora mi serve il verde e mi sposto sul secondo banco. Disegno sul secondo lucido con il verde, poi mi serve il blu e mi sposto sul terzo. Ripeto l'operazione per venti colori.

Alla fine torno indietro con i 20 lucidi, li sovrappongo e ottengo il disegno con tutti i colori. Se avevo 1000 colori, non sarebbe stato possibile e, in effetti, è quello che succede ai programmi ricorsivi. Se le chiamate sono migliaia, forse una moderna CPU ce la può fare, ma se sono milioni, o peggio miliardi, finirà lo spazio in cui salvare i risultati intermedi.

Per evitare questo problema si usa l'iterazione, che non ha questi limiti. Una loop che esegue delle istruzioni migliaia di miliardi di volte è normale, un programma ricorsivo non ce la farebbe mai. In generale, tra l’altro, una funzione iterativa è sempre più veloce di una ricorsiva.

Vediamo le differenze di programmazione utilizzando un problema banale: calcolare la somma degli interi fino al generico numero "n".

Function iterativa(n)

r=1 && Questo sarà il risultato

for k=2 to n && Iteriamo "n" volte

r=r+k && Prima fa 1+2=3 poi 3+3=6 poi 6+4=10 ecc.

next

return r && Questo è il risultato

Questa funzione somma i numeri partendo da 1 in avanti.

Function ricorsiva(n)

if n <= 1

return 1

else

return n + ricorsiva(n-1)

endif

Questa funzione somma i numeri partendo da n e procedendo all'indietro.

Se scrivo "print iterativa(5)" oppure "print ricorsiva(5)" il risultato sarà 15 immediatamente, ma se scrivo

"print iterativa(1.000.000.000)" o "print ricorsiva(1.000.000.000)", nel primo caso avrò il risultato in un secondo, nel secondo caso avrò un errore, perché una CPU di solito non è in grado di chiamare se stessa così tante volte. Si dice che il programma va in "stack overflow" ed è uno dei metodi usati dagli hacker per prendere il controllo dei computer. Se il sistema operativo non interviene bloccando il programma, ovvio.