Differenza tra ricorsione e iterazione
Share
Differenza chiave - Ricorsione vs Iteration
La ricorsione e l'iterazione possono essere utilizzate per risolvere problemi di programmazione. L'approccio alla risoluzione del problema mediante ricorsione o iterazione dipende dal modo in cui risolvere il problema. Il differenza fondamentale tra ricorsione e iterazione è quella la ricorsione è un meccanismo per chiamare una funzione all'interno della stessa funzione mentre l'iterazione deve eseguire ripetutamente un insieme di istruzioni fino a quando la condizione data è vera. La ricorsione e l'iterazione sono tecniche importanti per lo sviluppo di algoritmi e la creazione di applicazioni software.
CONTENUTO
1. Panoramica e differenza chiave
2. Cos'è la ricorsione
3. Cos'è l'iterazione
4. Somiglianze tra ricorsione e iterazione
5. Confronto affiancato - Ricorsione contro iterazione in forma tabulare
6. Sommario
Cos'è la ricorsione?
Quando una funzione si chiama all'interno della funzione, è conosciuta come ricorsione. Esistono due tipi di ricorsione. Sono una ricorsione finita e una ricorsione infinita. Ricorsione finita ha una condizione di chiusura. Ricorsione infinita non ha una condizione di chiusura.
La ricorsione può essere spiegata usando il programma per calcolare i fattoriali.
n! = n * (n-1) !, se n> 0
n! = 1, se n = 0;
Fare riferimento al codice qui sotto per calcolare il fattoriale di 3 (3! = 3 * 2 * 1).
intmain ()
int value = factorial (3);
printf ("Fattoriale è% d \ n", valore);
ritorno 0;
intfactorial (intn)
if (n == 0)
ritorno 1;
altro
return n * factorial (n-1);
Quando si chiama factorial (3), quella funzione chiamerà factorial (2). Quando si chiama fattoriale (2), quella funzione chiamerà fattoriale (1). Quindi fattoriale (1) chiamerà fattoriale (0). fattoriale (0) restituirà 1. Nel programma precedente, n == 0 condizione nel "se blocco" è la condizione di base. Secondo lo stesso, la funzione fattoriale è chiamata ancora e ancora.
Le funzioni ricorsive sono correlate allo stack. In C, il programma principale può avere molte funzioni. Quindi main () è la funzione di chiamata e la funzione chiamata dal programma principale è la funzione chiamata. Quando viene chiamata la funzione, 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: ricorsione
Nel programma sopra, quando 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 informazioni sulle variabili locali, ecc. Ogni volta che viene chiamata la funzione, viene creato un nuovo set di variabili locali in cima allo stack. Questi frame stack possono rallentare la velocità. Allo stesso modo in ricorsione, una funzione chiama se stessa. La complessità temporale per una funzione ricorsiva è individuata 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 usando "for loop", "do-while loop" o "while loop". La sintassi "for loop" è la seguente.
per (inizializzazione, condizione, modifica)
// dichiarazioni;
Figura 02: "per diagramma di flusso ad anello"
Il passo 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 affermazioni vengono eseguite fino a quando la condizione è 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. È per aggiornare la variabile di controllo del ciclo. Quindi la condizione viene ricontrollata. Se la condizione è vera, verranno eseguite le istruzioni all'interno delle parentesi graffe. In questo modo il ciclo "for" itera.
In "ciclo while", le istruzioni all'interno del ciclo vengono eseguite fino a quando la condizione è vera.
while (condizione)
// dichiarazioni
Nel ciclo "fai-da-te", 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 ("for loop") è il seguente.
int main ()
intn = 3, factorial = 1;
inti;
per (i = 1; i<=n ; i++)
fattoriale = fattoriale * i;
printf ("Fattoriale è% d \ n", fattoriale);
ritorno 0;
Quali sono le somiglianze tra ricorsione e iterazione?
- Entrambe sono tecniche per risolvere un problema.
- L'attività può essere risolta in ricorsione o iterazione.
Qual è la differenza tra ricorsione e iterazione?
Ricorsione contro 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à dello spazio | |
| 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 c'è una condizione di terminazione, può esserci una ricorsione infinita. | Se la condizione non diventa mai falsa, sarà un'infinita iterazione. |
| Pila | |
| In ricorsione, lo stack viene utilizzato per memorizzare le variabili locali quando viene chiamata la funzione. | In una iterazione, la pila non viene utilizzata. |
| Leggibilità del codice | |
| Un programma ricorsivo è più leggibile. | Il programma iterativo è più difficile da leggere rispetto a un programma ricorsivo. |
Riassunto - Ricorsione vs Iteration
Questo articolo ha discusso la differenza tra ricorsione e iterazione. Entrambi possono essere usati 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 utilizzando iterazioni.
Scarica la versione PDF di Recursion vs Iteration
È possibile scaricare la versione PDF di questo articolo e utilizzarlo per scopi offline come da nota di citazione. Si prega di scaricare la versione PDF qui Differenza tra ricorsione e iterazione
Riferimento:
1. Punto, esercitazioni. "Nozioni di base sulle ricorsive di strutture e algoritmi di dati.", Punto tutorial, 15 agosto 2017. Disponibile qui
2.nareshtechnologies. "Ricorsione in funzioni C | C Language Tutorial "YouTube, YouTube, 12 settembre 2016. Disponibile qui
3.yusuf shakeel. "Algoritmo di ricorsione | Fattoriale - guida passo passo "YouTube, YouTube, 14 ottobre 2013. Disponibile qui
Cortesia dell'immagine:
1.'CPT-Ricorsione-Codice fattoriale'By Pluke - Opera propria, (Dominio Pubblico) tramite Commons Wikimedia
2.'For-loop-diagram'By Nessun autore leggibile a macchina fornito - Opera propria ipotizzata. (CC BY-SA 2.5) attraverso Commons Wikimedia
