Ricorsione e iterazione
Per capire la ricorsione, devi capire la ricorsione...
Iterazione nella programmazione:
una fasedi un processo ciclico di elaborazione dei dati.
Spesso gli algoritmi iterativi nella fase corrente (iterazione) utilizzano il risultato della stessa operazione o azione calcolata nelle fasi precedenti. Un esempio di tali calcoli è il calcolo delle relazioni di ricorrenza.
Un semplice esempio di valore ricorsivo è il fattoriale:
\(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
Il calcolo del valore ad ogni passo (iterazione) è
\(N=N \cdot i\) . Quando calcoliamo il valore di
\(N\), prendiamo il valore già memorizzato
\(N\).
Il fattoriale di un numero può anche essere descritto usando la
formula ricorrente:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casi} \end{equazione*}\)
Potresti notare che questa descrizione non è altro che una funzione ricorsiva.
Qui la prima riga (
\(n <= 1\)) è il caso base (condizione di terminazione della ricorsione) e la seconda riga è la transizione al passo successivo.
| Funzione fattoriale ricorsiva |
Algoritmo iterativo |
static int Factorial(int n){
se (n > 1)
return n * Fattoriale(n - 1);
altrimenti restituisce 1;
}
|
int x = 1;
for (int i = 2; i <= n; i++)
x = x * io;
Console.WriteLine("%d", x);
|
Dovrebbe essere chiaro che le chiamate di funzione comportano un sovraccarico aggiuntivo, quindi un calcolo fattoriale non ricorsivo sarà leggermente più veloce.
Conclusione: dove puoi scrivere un programma con un semplice algoritmo iterativo, senza ricorsione, allora devi scrivere senza ricorsione. Tuttavia, esiste un'ampia classe di problemi in cui il processo computazionale è implementato solo mediante ricorsione.
D'altra parte, gli algoritmi ricorsivi sono spesso più comprensibili.