Differenza tra ricorsione e iterazione in informatica

Ricorsione

La ricorsione (in inglese Recursion) è un metodo per risolvere un problema in cui la soluzione dipende da soluzioni a istanze più piccole dello stesso problema. L’approccio può essere applicato a molti tipi di problemi. La ricorsione viene utilizzata in una varietà di discipline che vanno dalla linguistica alla logica. L’applicazione più comune della ricorsione è in matematica e informatica, dove una funzione che viene definita viene applicata all’interno della propria definizione.

Iterazione

L’iterazione (in inglese Iteration ) è la ripetizione di un processo per generare una sequenza di risultati. La sequenza si avvicinerà a un punto finale o a un valore finale. Ogni ripetizione del processo è una singola iterazione e il risultato di ogni iterazione è quindi il punto di partenza dell’iterazione successiva.

Differenza tra ricorsione e iterazione

BASE DI CONFRONTO	RICURSIONE	ITERAZIONE
Descrizione	La ricorsione coinvolge una funzione ricorsiva che chiama se stessa ripetutamente fino a quando non viene raggiunta una condizione di base (funzione che è parzialmente definita da se stessa).	L’iterazione implica l’uso di cicli attraverso i quali un insieme di istruzioni viene eseguito ripetutamente finché la condizione non è falsa (ripetizioni di un processo basate su cicli).
Dimensione del codice	La ricorsione mantiene il codice breve e semplice.	L’approccio iterativo rende il codice più lungo.
Cosa comporta	Nella funzione ricorsiva, viene specificata solo la condizione di terminazione (caso base).	L’iterazione include l’inizializzazione, la condizione e l’esecuzione dell’istruzione all’interno del ciclo e l’aggiornamento (incrementi e decrementi) della variabile di controllo.
Overhead	Le funzioni ricorsive comportano un sovraccarico estensivo poiché ogni funzione chiama lo stato corrente, i parametri, ecc. Devono essere spinti e estratti dallo stack.	L’overhead è assente nell’iterazione.
Struttura	La ricorsione utilizza la struttura di selezione.	L’iterazione utilizza la struttura della ripetizione.
Risoluzione	La ricorsione termina quando viene riconosciuto un caso base.	L’iterazione termina quando la condizione di continuazione del ciclo fallisce.
Velocità	A causa dell’overhead del mantenimento dello stack, la ricorsione è relativamente più lenta dell’iterazione.	L’iterazione non implica l’uso dello stack; quindi è relativamente più veloce della ricorsione.
Condizione infinita	La ricorsione infinita si verifica se il passaggio di ricorsione non riduce il problema in un modo che converge su una condizione (caso base).	Un ciclo infinito si verifica con l’iterazione se il test della condizione del ciclo non diventa mai falso.
Effetto sul tempo di funzionamento del processore	La ricorsione aumenta il tempo di funzionamento del processore.	L’iterazione riduce il tempo di funzionamento del processore.
Utilizzo della memoria	La ricorsione utilizza l’area dello stack per memorizzare lo stato corrente della funzione a causa del quale l’utilizzo della memoria è relativamente elevato.	L’iterazione utilizza l’area di memoria permanente solo per le variabili coinvolte nel suo blocco di codice e quindi l’utilizzo della memoria è relativamente inferiore.
Complessità temporale	Complessità temporale molto elevata (generalmente esponenziale).	Complessità temporale relativamente inferiore (generalmente polinomio-logaritmica).
Effetto sulla CPU	La ricorsione infinita può mandare in crash la CPU.	Il looping infinito utilizza ripetutamente i cicli della CPU.
Applicazione	Fattoriale, serie di Fibonacci ecc.	Trovare la media di una serie di dati, creare una tabella di moltiplicazione ecc.