Concetti Chiave
- La ricorsione è un concetto informatico complesso che implica chiamate di funzioni all'interno della stessa funzione.
- Richiede una condizione di uscita per evitare ricorsioni infinite, scomponendo i problemi in parti più piccole fino a raggiungere soluzioni note.
- Il fattoriale è un esempio pratico di ricorsione, dove si utilizza la conoscenza che 0! è uguale a 1 per ricomporre la soluzione finale.
- Un vantaggio della ricorsione è la riduzione del codice e la sua leggibilità, mentre uno svantaggio è l'elevato utilizzo di memoria centrale.
- Tempi di esecuzione non accettabili possono emergere quando si affrontano problemi di ordine esponenziale con la 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);
}
Meccanismo della ricorsione
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.
Quali sono i vantaggi e svantaggi della ricorsione?
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.
Domande da interrogazione
- Qual è il meccanismo fondamentale della ricorsione in informatica?
- Quali sono i principali vantaggi della ricorsione?
- Qual è uno svantaggio significativo della ricorsione?
La ricorsione si basa sulle chiamate di funzioni all'interno della stessa funzione, richiedendo una condizione di uscita per evitare ricorsioni infinite. Essa scompone un problema in problemi di grado minore fino a raggiungere una soluzione nota, come nel caso del calcolo del fattoriale.
Un vantaggio della ricorsione è la riduzione del quantitativo di codice, che risulta più leggibile, anche se può essere difficile da interpretare logicamente.
Un inconveniente della ricorsione è l'elevato utilizzo di memoria centrale ad ogni esecuzione, che può portare a tempi di esecuzione non accettabili per problemi di ordine esponenziale.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
