Differenza chiave: ricorsione e iterazione
La ricorsione e l'iterazione possono essere utilizzate per risolvere problemi di programmazione. L'approccio per risolvere il problema utilizzando la ricorsione o l'iterazione dipende dal modo in cui si risolve il problema. Il differenza fondamentale tra ricorsione e iterazione è quello la ricorsione è un meccanismo per chiamare una funzione all'interno della stessa funzione mentre l'iterazione consiste nell'esecuzione ripetuta di un insieme di istruzioni finché la condizione data non è vera. La ricorsione e l'iterazione sono le principali tecniche per lo sviluppo di algoritmi e la creazione di applicazioni software.
Cos'è la ricorsione?
Quando una funzione chiama se stessa all'interno della funzione, è nota come ricorsione. Esistono due tipi di ricorsione. Sono ricorsione finita e ricorsione infinita. La ricorsione finita ha una condizione di terminazione. La ricorsione infinita non ha una condizione di terminazione.
La ricorsione può essere spiegata usando il programma per calcolare i fattoriali.
n!=n(n-1)!, se n>0
n!=1, se n=0;
Fai riferimento al codice seguente per calcolare il fattoriale di 3(3!=321).
intmain() {
int valore=fattoriale (3);
printf("Fattoriale è %d\n", valore);
ritorno 0;
}
intfactorial (intn) {
se(n==0) {
ritorno 1;
}
altro {
restituisce n fattoriale(n-1);
}
}
Quando si chiama fattoriale (3), quella funzione chiamerà fattoriale (2). Quando si chiama fattoriale (2), quella funzione chiamerà fattoriale (1). Quindi fattoriale (1) chiamerà fattoriale (0). fattoriale (0) restituirà 1. Nel programma sopra, la condizione n==0 nel "blocco se" è la condizione di base. Secondo Allo stesso modo, la funzione fattoriale viene chiamata ancora e ancora.
Le funzioni ricorsive sono correlate allo stack. In C, il programma principale può avere molte funzioni. Quindi, main() è la funzione chiamante e la funzione chiamata dal programma principale è la funzione chiamata. Quando la funzione viene chiamata, il controllo viene assegnato alla funzione chiamata. Al termine dell'esecuzione della funzione, il controllo viene restituito a main. Quindi il programma principale continua. Quindi, crea un record di attivazione o uno stack frame per continuare l'esecuzione.
Figura 01: Ricorsività
Nel programma sopra, quando si chiama fattoriale (3) da main, crea un record di attivazione nello stack di chiamate. Quindi, lo stack frame fattoriale (2) viene creato in cima allo stack e così via. Il record di attivazione conserva le informazioni sulle variabili locali, ecc. Ogni volta che viene chiamata la funzione, viene creato un nuovo insieme di variabili locali in cima allo stack. Questi frame stack possono rallentare la velocità. Allo stesso modo nella ricorsione, una funzione chiama se stessa. La complessità temporale per una funzione ricorsiva si trova dal numero di volte in cui la funzione viene chiamata. La complessità temporale per una chiamata di funzione è O(1). Per n numero di chiamate ricorsive, la complessità temporale è O(n).
Cos'è l'iterazione?
L'iterazione è un blocco di istruzioni che si ripete ancora e ancora finché la condizione data non è vera. L'iterazione può essere ottenuta utilizzando "for loop", "do-while loop" o "while loop". La sintassi "for loop" è la seguente.
for (inizializzazione; condizione; modifica) {
// dichiarazioni;
}
Figura 02: "per diagramma di flusso del circuito"
Il passaggio di inizializzazione viene eseguito per primo. Questo passaggio consiste nel dichiarare e inizializzare le variabili di controllo del ciclo. Se la condizione è vera, le istruzioni all'interno delle parentesi graffe vengono eseguite. Tali istruzioni vengono eseguite finché la condizione non è vera. Se la condizione è falsa, il controllo passa all'istruzione successiva dopo il "ciclo for". Dopo aver eseguito le istruzioni all'interno del ciclo, il controllo passa alla sezione di modifica. Serve per aggiornare la variabile di controllo del ciclo. Quindi la condizione viene nuovamente verificata. Se la condizione è vera, verranno eseguite le istruzioni racchiuse tra parentesi graffe. In questo modo il ciclo "for" scorre.
In "while loop", le istruzioni all'interno del ciclo vengono eseguite finché la condizione non è vera.
mentre (condizione){
//dichiarazioni
}
Nel ciclo "do-while", la condizione viene verificata alla fine del ciclo. Quindi, il ciclo viene eseguito almeno una volta.
fai{
//dichiarazioni
} while(condizione)
Il programma per trovare il fattoriale di 3 (3!) usando l'iterazione ("for loop") è il seguente.
int main(){
intn=3, fattoriale=1;
inti;
for(i=1; i<=n; i++){
fattoriale=fattorialei;
}
printf("Fattoriale è %d\n", fattoriale);
ritorno 0;
}
Quali sono le somiglianze tra ricorsione e iterazione?
- Entrambe sono tecniche per risolvere un problema.
- Il compito può essere risolto in ricorsione o iterazione.
Qual è la differenza tra ricorsione e iterazione?
Ricorsione vs Iterazione |
|
| La ricorsione è un metodo per chiamare una funzione all'interno della stessa funzione. | L'iterazione è un blocco di istruzioni che si ripete finché la condizione data non è vera. |
| Complessità spaziale | |
| La complessità spaziale dei programmi ricorsivi è superiore alle iterazioni. | La complessità dello spazio è inferiore nelle iterazioni. |
| Velocità | |
| L'esecuzione della ricorsione è lenta. | Normalmente, l'iterazione è più veloce della ricorsione. |
| Condizione | |
| Se non vi è alcuna condizione di terminazione, può esserci una ricorsione infinita. | Se la condizione non diventa mai falsa, sarà un'iterazione infinita. |
| Impila | |
| Nella ricorsione, lo stack viene utilizzato per memorizzare le variabili locali quando viene chiamata la funzione. | In un'iterazione, lo stack non viene utilizzato. |
| Leggibilità del codice | |
| Un programma ricorsivo è più leggibile. | Il programma iterativo è più difficile da leggere di un programma ricorsivo. |
Riepilogo – Ricorsività vs Iterazione
Questo articolo ha discusso la differenza tra ricorsione e iterazione. Entrambi possono essere utilizzati per risolvere problemi di programmazione. La differenza tra ricorsione e iterazione è che la ricorsione è un meccanismo per chiamare una funzione all'interno della stessa funzione e iterarla per eseguire ripetutamente un insieme di istruzioni finché la condizione data non è vera. Se un problema può essere risolto in forma ricorsiva, può anche essere risolto usando le iterazioni.
Scarica la versione PDF di ricorsione e iterazione
Puoi scaricare la versione PDF di questo articolo e usarla per scopi offline come da nota di citazione. Si prega di scaricare la versione PDF qui Differenza tra ricorsione e iterazione
