RICORSIONE E ITERAZIONE

Nei linguaggi di programmazione esistono due concetti molto importanti ed utili, ma che spesso vengono confusi: iterazione e ricorsione. L’iterazione può essere definita come l’esecuzione ripetuta di una o più righe di codice, fino a quando non si verifichi una determinata situazione. In C# e VB.NET ad esempio è possibile utilizzare gli oggetti For, For Each, Do, While ecc. per poter realizzare una iterazione. Una caratteristica importante, inoltre, è che le righe di codice che formano il loop dell’iterazione, sono tutte nella stessa funzione.

Si parla invece di ritorsione quando una funzione richiama se stessa all’interno delle funzione stessa. Gli elementi fondamentali della ricorsione sono due: il passo ricorso, cioè il comando che richiama la funzione stessa, e il passo base, cioè il comando che comporta l’uscita dal loop. Ad ogni chiamata si genera un nuovo stack frame. Il vantaggio di utilizzare una struttura ricorsivi piuttosto che una iterazione, è che il codice risulta essere più compatto e semplice da leggere, ma solitamente la ricorsione occupa più memoria dell’equivalente iterazione; inoltre, utilizzando una ritorsione, può accadere di incappare in uno stack overflow, cioè lo stack eccede la memoria a sua disposizione.

Vediamo ora un esempio molto comune per confrontare i due oggetti: la funzione naive per il calcolo del fattoriale:

// ITERAZIONE

Function Fattoriale_Iterativo (N As Integer) As Integer
  Dim Prodotto As Integer = 1
  For i As Integer = 2 To N
    Prodotto *= i
  Next
  Return Prodotto
End Function


// RICORSIONE

Function Fattoriale_Ricorsivo (N as Integer) As Integer
  'Base Case
  If N = 1 Then Return 1
  'Recursive Case
  Return N * Fattoriale_Ricorsivo(N-1)
End Function