Concetti Chiave
- La ricorsione è un concetto complesso che implica l'uso di funzioni che chiamano sé stesse.
- Fondamentale per la ricorsione è la presenza di una condizione di uscita per evitare loop infiniti.
- La ricorsione scompone problemi complessi in sottoproblemi più semplici fino a raggiungere una soluzione nota.
- Un svantaggio della ricorsione è l'alto consumo di memoria dovuto alle molteplici chiamate di funzione.
- Uno dei vantaggi della ricorsione è la riduzione del codice, che risulta più leggibile.
C - Ricorsione
Il concetto della ricorsione in ambito informatico è uno dei concetti più complessi ed anti-intuitivi; la ricorsione si basa sulle chiamate di funzioni all’interno del corpo della stessa funzione chiamante.
Es.
int fattoriale(int n)
{
if (n == 0)
return 1;
else
return n*fattoriale(n-1);
}
Questo meccanismo per essere utilizzabile ha bisogno però di una condizione di uscita che permetta di non eseguire una ricorsione infinita, la ricorsione si basa infatti sulla divisione di un problema in problemi di grado minore fino a scomporli in un problema di cui si conosce il risultato, per poi mettere insieme tutte le soluzioni elementari trovate per comporre la soluzione del problema iniziale. Nel caso del fattoriale infatti sappiamo che il fattoriale di 0 è uguale ad 1, pertanto ricorriamo cercando il fattoriale di n-1 finchè non raggiungiamo la soluzione elementare, 0! = 1, per poi ricomporre la soluzione del fattoriale.
Un inconveniente della ricorsione è l’utilizzo di memoria centrale ad ogni esecuzione ricorsiva della funzione, che per problemi di ordine esponenziale possono portare ad un tempo di esecuzione non accettabile.
Come vantaggio, la ricorsione porta però un ridotto quantitativo di codice facilmente leggibile anche se di difficile interpretazione logica.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
