Ricorsione
Con il termine ricorsione si intende l'applicazione di un processo ricorsivo per la risoluzione di un determinato problema.
Un processo ricorsivo, sostanzialmente, è uno schema di calcolo attraverso il quale il valore di una determinata funzione al passo n è calcolato tramite il valore della stessa funzione al passo n-1 e così via fino a raggiungere un caso terminale.
Un esempio di funzione ricorsiva è il fattoriale (n!), che può essere definito nel seguente modo:
Detto in modo "semplice", la ricorsione si ottiene quando una funzione richiama se stessa durante la sua esecuzione.
Come creare un algoritmo ricorsivo
Per creare un algoritmo ricorsivo occorre per prima cosa isolare o designare dei casi particolari di arresto, successivamente sviluppare la soluzione in modo da convergere verso tali condizioni.
L'analisi dei casi terminali è un passo fondamentale in quanto, in assenza di essi, non si potrebbe mai giungere ad una soluzione.
Una volta fatto ciò è possibile passare alla creazione di una funzione che esegua tale algoritmo.
Una funzione ricorsiva ha sempre una o più variabili di controllo, che, variando il loro valore ad ogni chiamata, dirigono la convergenza verso il caso di arresto.
Vantaggi e svantaggi
Uno dei più grandi vantaggi degli algoritmi ricorsivi si trova nel metodo di rappresentazione della soluzione.
Essa può infatti essere espressa con una scrittura molto simile a quella matematica.
Gli algoritmi ricorsivi inoltre risultano più puliti ed eleganti rispetto ad un equivalente iterativo, dunque anche più leggibili ed apprezzabili.
Il vero problema è dato dall'impatto che essi hanno sull'efficienza, per comprendere il perché, occorre esaminare il funzionamento di un algoritmo ricorsivo.
Funzionamento
Nel momento in cui viene chiamata una funzione viene allocata una porzione di memoria riservata ai parametri (argomenti della funzione) e alle eventuali variabili locali.
Questa porzione è deallocata solo nel momento in cui la funzione termina.
Nel momento in cui una funzione ricorsiva crea una nuova istanza di sé stessa la sua esecuzione viene messa in pausa, in attesa di ricevere un valore di ritorno.
Viene dunque allocata una nuova porzione di memoria per la nuova istanza, in cui vengono copiati i nuovi parametri attuali.
Solo nel momento in cui viene raggiunto un caso terminale viene restituito un valore di ritorno, a quel punto la memoria viene deallocata, partendo dalla porzione riservata all'ultima istanza e risalendo verso la prima.
Questo fenomeno viene detto "overhead".
E' facile dunque capire che un algoritmo ricorsivo non è adatto ad eseguire una grande quantità di calcoli, in quanto ciò porterebbe ad un grosso rallentamento (dovuto per lo più al tempo perso nelle chiamate) e all'allocamento di una grossa quantità di memoria.
Algoritmi ricorsivi ed iterativi
Un algoritmo ricorsivo può essere espresso in maniera più o meno semplice in modo iterativo.
In questo caso si ottiene un miglioramento delle prestazioni a discapito però, della semplicità e leggibilità del codice.
Lascio qui alcuni esempi di algoritmi ricorsivi ed iterativi ed i benchmark relativi al calcolo dell' n-simo termine della successione di fibonacci.
Fattoriale:
Successione di Fibonacci:
Pari o dispari
Con il termine ricorsione si intende l'applicazione di un processo ricorsivo per la risoluzione di un determinato problema.
Un processo ricorsivo, sostanzialmente, è uno schema di calcolo attraverso il quale il valore di una determinata funzione al passo n è calcolato tramite il valore della stessa funzione al passo n-1 e così via fino a raggiungere un caso terminale.
Un esempio di funzione ricorsiva è il fattoriale (n!), che può essere definito nel seguente modo:
Come creare un algoritmo ricorsivo
Per creare un algoritmo ricorsivo occorre per prima cosa isolare o designare dei casi particolari di arresto, successivamente sviluppare la soluzione in modo da convergere verso tali condizioni.
L'analisi dei casi terminali è un passo fondamentale in quanto, in assenza di essi, non si potrebbe mai giungere ad una soluzione.
Una volta fatto ciò è possibile passare alla creazione di una funzione che esegua tale algoritmo.
Una funzione ricorsiva ha sempre una o più variabili di controllo, che, variando il loro valore ad ogni chiamata, dirigono la convergenza verso il caso di arresto.
Vantaggi e svantaggi
Uno dei più grandi vantaggi degli algoritmi ricorsivi si trova nel metodo di rappresentazione della soluzione.
Essa può infatti essere espressa con una scrittura molto simile a quella matematica.
Gli algoritmi ricorsivi inoltre risultano più puliti ed eleganti rispetto ad un equivalente iterativo, dunque anche più leggibili ed apprezzabili.
Il vero problema è dato dall'impatto che essi hanno sull'efficienza, per comprendere il perché, occorre esaminare il funzionamento di un algoritmo ricorsivo.
Funzionamento
Nel momento in cui viene chiamata una funzione viene allocata una porzione di memoria riservata ai parametri (argomenti della funzione) e alle eventuali variabili locali.
Questa porzione è deallocata solo nel momento in cui la funzione termina.
Nel momento in cui una funzione ricorsiva crea una nuova istanza di sé stessa la sua esecuzione viene messa in pausa, in attesa di ricevere un valore di ritorno.
Viene dunque allocata una nuova porzione di memoria per la nuova istanza, in cui vengono copiati i nuovi parametri attuali.
Solo nel momento in cui viene raggiunto un caso terminale viene restituito un valore di ritorno, a quel punto la memoria viene deallocata, partendo dalla porzione riservata all'ultima istanza e risalendo verso la prima.
Questo fenomeno viene detto "overhead".
E' facile dunque capire che un algoritmo ricorsivo non è adatto ad eseguire una grande quantità di calcoli, in quanto ciò porterebbe ad un grosso rallentamento (dovuto per lo più al tempo perso nelle chiamate) e all'allocamento di una grossa quantità di memoria.
Algoritmi ricorsivi ed iterativi
Un algoritmo ricorsivo può essere espresso in maniera più o meno semplice in modo iterativo.
In questo caso si ottiene un miglioramento delle prestazioni a discapito però, della semplicità e leggibilità del codice.
Lascio qui alcuni esempi di algoritmi ricorsivi ed iterativi ed i benchmark relativi al calcolo dell' n-simo termine della successione di fibonacci.
Fattoriale:
Ricorsivo:
Iterativo:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Iterativo:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Successione di Fibonacci:
Ricorsivo:
Iterativo:
Benchmark:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Iterativo:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Perfavore,
Entra
oppure
Registrati
per vedere i Link!
Pari o dispari
Ricorsivo:
Iterativo:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Iterativo:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
