![](http://gadget-info.com/img/difference-between/118/difference-between-recursion.jpg)
Grafico comparativo
Base per il confronto | ricorsione | Iterazione |
---|---|---|
Di base | L'affermazione in un corpo di funzioni chiama la funzione stessa. | Consente di eseguire ripetutamente l'insieme di istruzioni. |
Formato | In funzione ricorsiva, viene specificata solo la condizione di terminazione (caso base). | La iterazione include l'inizializzazione, la condizione, l'esecuzione dell'istruzione all'interno del ciclo e l'aggiornamento (incrementi e decrementi) della variabile di controllo. |
fine | Un'istruzione condizionale è inclusa nel corpo della funzione per forzare la funzione a ritornare senza che venga eseguita la chiamata di ricorsione. | L'istruzione di iterazione viene ripetutamente eseguita fino a quando viene raggiunta una determinata condizione. |
Condizione | Se la funzione non converge in una condizione chiamata (caso base), conduce alla ricorsione infinita. | Se la condizione di controllo nella dichiarazione di iterazione non diventa mai falsa, porta a un'infinita iterazione. |
Ripetizione infinita | La ricorsione infinita può mandare in crash il sistema. | Il ciclo infinito utilizza ripetutamente i cicli della CPU. |
Applicato | La ricorsione è sempre applicata alle funzioni. | L'iterazione viene applicata alle istruzioni di iterazione o ai "loop". |
Pila | Lo stack viene utilizzato per memorizzare l'insieme di nuove variabili locali e parametri ogni volta che viene chiamata la funzione. | Non utilizza lo stack. |
in alto | La ricorsione possiede il sovraccarico delle chiamate a funzioni ripetute. | Nessun sovraccarico di chiamate a funzioni ripetute. |
Velocità | Lento in esecuzione. | Veloce in esecuzione. |
Dimensione del codice | La ricorsione riduce la dimensione del codice. | L'iterazione rende il codice più lungo. |
Definizione di ricorsione
C ++ consente a una funzione di chiamarsi all'interno del suo codice. Ciò significa che la definizione della funzione possiede una chiamata di funzione a se stessa. A volte è anche chiamato " definizione circolare ". L'insieme di variabili locali e parametri utilizzati dalla funzione vengono creati di nuovo ogni volta che la funzione chiama se stesso e vengono memorizzati nella parte superiore dello stack. Ma, ogni volta che una funzione si chiama, non crea una nuova copia di quella funzione. La funzione ricorsiva non riduce in modo significativo la dimensione del codice e non migliora nemmeno l'utilizzo della memoria, ma lo fa rispetto all'iterazione.
Per terminare la ricorsione, è necessario includere un'istruzione select nella definizione della funzione per forzare la funzione a ritornare senza dare una chiamata ricorsiva a se stessa. L'assenza dell'istruzione select nella definizione di una funzione ricorsiva consentirà alla funzione di ricorsività infinita una volta chiamata.
Cerchiamo di comprendere la ricorsione con una funzione che restituirà il fattoriale del numero.
int factorial (int num) {int answer; if (num == 1) {return 1; } else {answer = factorial (num-1) * num; // chiamata ricorsiva} return (risposta); }
Nel codice precedente, l'istruzione in un'altra parte mostra la ricorsione, poiché l'istruzione chiama la funzione factorial () in cui risiede.
Definizione di Iterazione
L'iterazione è un processo che esegue ripetutamente l'insieme di istruzioni finché la condizione nella dichiarazione di iterazione diventa falsa. L'istruzione di iterazione include l'inizializzazione, il confronto, l'esecuzione delle istruzioni all'interno dell'istruzione di iterazione e infine l'aggiornamento della variabile di controllo. Dopo che la variabile di controllo è stata aggiornata, viene confrontata di nuovo e il processo si ripete fino a quando la condizione nella dichiarazione di iterazione risulta falsa. Le istruzioni di iterazione sono "for" loop, "while" loop, "do-while" loop.
L'istruzione di iterazione non usa uno stack per memorizzare le variabili. Quindi, l'esecuzione dell'istruzione di iterazione è più veloce rispetto alla funzione ricorsiva. Anche la funzione di iterazione non ha il sovraccarico delle chiamate a funzioni ripetute che rendono la sua esecuzione più veloce della funzione ricorsiva. L'iterazione termina quando la condizione di controllo diventa falsa. L'assenza della condizione di controllo nell'istruzione di iterazione può causare un loop infinito o può causare un errore di compilazione.
Comprendiamo l'iterazione relativa all'esempio precedente.
int factorial (int num) {int answer = 1; // ha bisogno dell'inizializzazione perché potrebbe contenere un valore spazzatura prima della sua inizializzazione per (int t = 1; t> num; t ++) // iterazione {answer = answer * (t); ritorno (risposta); }}
Nel codice sopra, la funzione restituisce il fattoriale del numero usando l'istruzione di iterazione.
Differenze chiave tra ricorsione e iterazione
- La ricorsione è quando un metodo in un programma si chiama ripetutamente mentre, iterazione è quando una serie di istruzioni in un programma viene ripetutamente eseguita.
- Un metodo ricorsivo contiene un insieme di istruzioni, una chiamata di istruzioni e una condizione di terminazione mentre le istruzioni di iterazione contengono inizializzazione, incremento, condizione, insieme di istruzioni all'interno di un ciclo e una variabile di controllo.
- Un'istruzione condizionale decide la cessazione della ricorsione e il valore della variabile di controllo decide la conclusione dell'istruzione di iterazione.
- Se il metodo non porta alla condizione di terminazione entra in ricorsione infinita. D'altra parte, se la variabile di controllo non porta mai al valore di terminazione, l'istruzione di iterazione itera infinitamente.
- La ricorsione infinita può portare al crash del sistema mentre, l'iterazione infinita consuma i cicli della CPU.
- La ricorsione viene sempre applicata al metodo mentre, l'iterazione viene applicata all'insieme di istruzioni.
- Le variabili create durante la ricorsione vengono archiviate nello stack mentre, l'iterazione non richiede una pila.
- La ricorsione causa l'overhead della chiamata a funzioni ripetute mentre, l'iterazione non ha una funzione che chiama overhead.
- A causa della funzione chiamata overhead, l'esecuzione della ricorsione è più lenta mentre l'esecuzione dell'iterazione è più veloce.
- La ricorsione riduce la dimensione del codice mentre, le iterazioni prolungano il codice.
Conclusione:
La funzione ricorsiva è facile da scrivere, ma non si comporta bene rispetto all'iterazione, mentre l'iterazione è difficile da scrivere ma le loro prestazioni sono buone rispetto alla ricorsione.