Ricorsione in java parte 1, definizione ed esempio
14 ottobre 2013  //  By:   //  Java  //  5 Comments   //   743 Views

Definiamo un metodo riscorsivo, un metodo che richiama se stesso direttamente o indirettamente, ossia attraverso un altro metodo.

Per comprendere al meglio il concetto di ricorsione dobbiamo capire come questa “ragioni”, diciamo subito che quando chiamiamo una funzione o metodo ricorsivo per risolvere un determinato problema, il metodo sa solo come risolvere i casi più semplici del problema in questione, chiamati casi base.Quando il metodo è invocato su un caso base, questo ritorna subito un risultato, se invece il metodo è invocato su un input più complesso, questo viene suddiviso in problemi più piccoli e più semplici, una che può essere risolta tramite il caso base, e una ancora troppo complessa che dovrà  essere nuovamente scomposta.
La ricorsione è fattibile proprio se questa seconda parte ancora troppo complessa, somiglia al problema originale ma in una versione semplificata. Nasce da qui il concetto di scomporre il problema in sotto problemi più semplici che siamo in grado di risolvere,fino ad arrivare al caso base.
Quindi visto che il sotto problema somiglia all’originale ma è più semplice chiameremo una copia della funzione su questo sottoproblema, questa procedura è detta chiamata ricorsiva e solitamente include la parola chiave return, perchè il risultato deve “ritornare” ai vari sottoproblemi al fine di risolvere il problema originale.

Continueremo con questa spiegazione teorica ma adesso vediamo un esempio

Il Primo esempio: IL FATTORIALE

Collaudo con metodo main

Vediamo cosa succede in pratica

Il fattoriale di un numero n, scritto con n! è il prodotto di:

n * (n-1) * (n-2) * …. * 1

in cui 1! da come risultato 1, così come 0!

Facciamo un esempio: il fattoriale di 5 è il prodoto di 5*4*3*2*1 = 120.

Prendiamo in considerazione il nostro metodo fattoriale scritto sopra, osserviamo questa relazione:

n! = n * (n-1)!

Nel 5! avremmo 5 * 4! cioè

5! = 5 * 4 * 3 * 2 * 1
5! = 5 * (4 * 3 * 2 * 1)
5! = 5 * (4!)

Quindi visivamente i valori ritornati dalla chiamata ricorsiva saranno:

Valore finale 120
5!
il valore ritornato è 5! = 5* 24 = 120
5 * 4!
il valore ritornato è 4! = 4 * 6 = 24
4 * 3!
il valore ritornato è 3! = 3 * 2 = 6
3 * 2!
il valore ritornato è 2! = 2 * 1 = 2
2 * 1!
il valore ritornato è 1 (caso base)
1

Nel prossimo articolo vedremo la .

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

5 Comments to “Ricorsione in java parte 1, definizione ed esempio”

Leave a reply