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.

Hai bisogno di aiuto in Informatica?
Trova il tuo insegnante su Skuola.net | Ripetizioni
Registrati via email