Differenza chiave: ricorsione vs 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 risolverlo. Il differenza fondamentale tra ricorsione e iterazione è che la ricorsione è un meccanismo per chiamare una funzione all'interno della stessa funzione mentre l'iterazione consiste nell'eseguire ripetutamente un insieme di istruzioni finché la condizione data è vera. La ricorsione e l'iterazione sono le principali tecniche per lo sviluppo di algoritmi e la creazione di applicazioni software.
CONTENUTI
1. Panoramica e differenza chiave
2. Che cos'è la ricorsione
3. Che cos'è l'iterazione
4. Somiglianze tra ricorsione e iterazione
5. Confronto affiancato - Ricorsione vs iterazione in forma tabulare
6. Riepilogo
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 utilizzando il programma per calcolare i fattoriali.
n! = n * (n-1) !, se n> 0
n! = 1, se n = 0;
Fare riferimento al codice seguente per calcolare il fattoriale di 3 (3! = 3 * 2 * 1).
intmain () {
valore int = fattoriale (3);
printf ("Il fattoriale è% d / n", valore);
return 0;
}
intfactorial (intn) {
if (n == 0) {
ritorno 1;
}
altro {
restituisce n * fattoriale (n-1);
}
}
Quando si chiama factorial (3), quella funzione chiamerà factorial (2). Quando si chiama fattoriale (2), quella funzione chiamerà fattoriale (1). Allora fattoriale (1) chiamerà fattoriale (0). fattoriale (0) restituirà 1. Nel programma precedente, n == 0 condizione nel "blocco if" è la condizione di base. Secondo Allo stesso modo, la funzione fattoriale viene chiamata ancora e ancora.
Le funzioni ricorsive sono correlate con lo 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 dato 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: ricorsione
Nel programma precedente, quando si chiama factorial (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 stack frame possono rallentare la velocità. Allo stesso modo nella ricorsione, una funzione chiama se stessa. La complessità temporale per una funzione ricorsiva viene rilevata 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 fino a quando la condizione data è vera. L'iterazione può essere ottenuta utilizzando "for loop", "do-while loop" o "while loop". La sintassi del "ciclo for" è la seguente.
for (inizializzazione; condizione; modifica) {
// dichiarazioni;
}
Figura 02: "diagramma di flusso per loop"
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, vengono eseguite le istruzioni all'interno delle parentesi graffe. Queste 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 loop. Quindi la condizione viene controllata di nuovo. Se la condizione è vera, verranno eseguite le istruzioni all'interno delle parentesi graffe. In questo modo il "ciclo for" itera.
In "while loop", le istruzioni all'interno del ciclo vengono eseguite finché la condizione non è vera.
while (condition) {
// dichiarazioni
}
Nel ciclo "do-while", la condizione viene verificata alla fine del ciclo. Quindi, il ciclo viene eseguito almeno una volta.
fare{
// dichiarazioni
} while (condizione)
Il programma per trovare il fattoriale di 3 (3!) Usando l'iterazione ("ciclo for") è il seguente.
int main () {
intn = 3, fattoriale = 1;
inti;
for (i = 1; i <= n; i ++) {
fattoriale = fattoriale * i;
}
printf ("Il fattoriale è% d / n", fattoriale);
return 0;
}
Quali sono le somiglianze tra ricorsione e iterazione?
- Entrambe sono tecniche per risolvere un problema.
- Il compito può essere risolto sia in ricorsione che in iterazione.
Qual è la differenza tra ricorsione e iterazione?
Articolo diff. Al centro prima della tabella
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 fino a quando la condizione data è vera. |
| Complessità spaziale | |
| La complessità dello spazio dei programmi ricorsivi è maggiore delle iterazioni. | La complessità dello spazio è inferiore nelle iterazioni. |
| Velocità | |
| L'esecuzione della ricorsione è lenta. | Normalmente, l'iterazione è più veloce della ricorsione. |
| Condizione | |
| Se non esiste una condizione di terminazione, può esserci una ricorsione infinita. | Se la condizione non diventa mai falsa, sarà un'iterazione infinita. |
| Pila | |
| 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: ricorsione 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 l'iterazione per eseguire ripetutamente un insieme di istruzioni fino a quando la condizione data è vera. Se un problema può essere risolto in forma ricorsiva, può essere risolto anche utilizzando iterazioni.
Scarica la versione PDF di Ricorsione vs Iterazione
È possibile scaricare la versione PDF di questo articolo e utilizzarla per scopi offline come da nota di citazione. Si prega di scaricare la versione PDF qui Differenza tra ricorsione e iterazione
