In Java, un metodo può chiamare se stesso, purché la chiamata utilizzi un valore più semplice. Il meccanismo per cui un metodo chiama se stesso per un numero ripetuto di volte si chiama ricorsione.
Esaminiamo il calcolo di 4! con il metodo factorial.
Per calcolare il fattoriale di 4, il metodo factorial(4) chiede di calcolare 4 * factorial(3). Non sapendo il risultato, si sospende temporaneamente questo calcolo e si intraprende il calcolo di factorial(3).
Per calcolare factorial(3) dobbiamo calcolare 3 * factorial(2). Non sapendo nemmeno questo risultato, si tralascia temporaneamente anche questo problema e si risolve factorial(2).
Per calcolare factorial(2) dobbiamo prima calcolare factorial(1).
Per calcolare factorial(1) dobbiamo prima calcolare factorial(0).
Il metodo factorial(0) restituisce 1, e a questo punto possiamo completare i calcoli lasciati in sospeso.
Ecco la successione delle chiamate e dei valori restituiti:
factorial(4) chiama factorial(3)
factorial(3) chiama factorial(2)
factorial(2) chiama factorial(1)
factorial(1) chiama factorial(0)
factorial(0) restituisce 1
factorial(1) restituisce 1 (1*1)
factorial(2) restituisce 2 (2*1)
factorial(3) restituisce 6 (3*2)
factorial(4) restituisce 24 (4*6)
==================================================
La fine della ricorsione
Esistono due requisiti chiave per assicurarsi che la ricorsione riesca:
Ciascuna chiamata ricorsiva deve semplificare in qualche modo l'elaborazione. (Nel metodo factorial le chiamate ricorsive si fanno su parametri più piccoli.)
Il metodo deve prevedere una clausola di chiusura per assicurarsi che le chiamate successive del metodo abbiano termine, ovvero devono esistere casi speciali per risolvere le elaborazioni più semplici.(Nel metodo factorial, il valore del parametro giunge inevitabilmente a zero, ed esiste un caso speciale per risolvere 0!).
Nessun commento:
Posta un commento