Ricorsione in java parte 3
18 ottobre 2013  //  By:   //  Java  //  2 Comments   //   925 Views

Negli articoli precedenti è stato implementato il codice ricorsivo sul fattoriale e su

Ora andremo a spendere alcune righe per parlare del comportamento degli algoritmi ricorsivi simili a quelli di fibonacci.

Ogni invocazione del metodo fibonacci che non ricade in uno dei due casi base produce due chiamate ricorsive allo stesso metodo fibonacci.
Pensate che il calcolo del 20° numero di fibonacci richiede in totale 21891 chiamate ricorsive, il numero delle chiamate ricorsive cresce molto rapidamente, con tale problemi si dice che abbiano complessità  esponenziale! Ed esistono alcune strutture che permettono di migliorane il tempo di esecuzione, e questo ricade nello studio degli “algoritmi”.

L’albero delle chiamate ricorsive del metodo fibonacci è il seguente:

immagine_ric4

 

Per dare un accenno a chi di voi è già  semi addentrato nella materia, possiamo dire che l’errore che fa il nostro metodo di fibonacci, per quanto generi sempre un risultato corretto, è quello di ricalcolare più e più volte risultati già calcolati, come mostrato nella seguente immagine:

immagine_ric5

 

Nei cerchi rossi sono evidenziate le chiamate ricorsive che continuano ad essere effettuate per ogni ramo dell’albero anche se per tali chiamate già  conosciamo la soluzione, sarebbe infatti possibile mantenere tali risultati in una struttura dati ad esempio un array, ed evitare ogni volta di ricalcolarli.

Provate ad implementare un metodo del genere non è difficile!

About the Author :

BI CONSULTING. Studente di Ingegneria Informatica, Sistemista Linux e appassionato di tutto ciò che sia tecnologico ma soprattutto Open Source. Distro: Debian e Arch LInux. Smartphone: Nexus / Lg G2 Buona Lettura  Visualizza il profilo su Linkedln

2 Comments to “Ricorsione in java parte 3”

Leave a reply