Java/Ricorsione
Wikibooks, manuali e libri di testo liberi.
La ricorsione e' una tecnica di programmazione per cui si può definire una funzione in termini di se stessa. Matematicamente parlando, essa si basa sul principio di induzione:
- se una proprietà P vale per n = n0 -> caso base
- e si può verificare che, assumendola valida per n, allora vale anche per n + 1
- allora P vale per ogni n ≥ n0
Operativamente utilizzare un approccio ricorsivo comporta:
- identificare un caso base di cui conosciamo la soluzione
- esprimere la soluzione al caso generico n in termini dello stesso problema scomposto in casi più semplici (n - 1, n - 2, etc)
La ricorsione è largamente utilizzata nei linguaggi non dichiarativi (programmazione logica o funzionale).
[modifica] Vantaggi e svantaggi
L'utilizzo della ricorsione permette di scrivere algoritmi anche molto complessi con poche righe di codice in maniera elegante e sintetica.
Tuttavia essa ha anche un enorme svantaggio: le prestazioni. Una funzione che richiama se stessa ha un costo elevato in quanto ad ogni nuova chiamata il programma si ferma e inserisce i dati calcolati fino a quel punto in memoria, se le chiamate sono molte potremmo esaurire la memoria a disposizione.
Se nella pratica della programmazione sono pochi i casi in cui è consigliabile l'utilizzo della ricorsione, a livello didattico è utilissima per alzare il livello di astrazione nella risoluzione di un problema.
[modifica] Un esempio: il fattoriale
In matematica, se n è un intero positivo, si definisce n fattoriale e si indica con n! il prodotto dei primi n numeri interi positivi.
per cui il fattoriale di 3 si indica con 3! e si calcola come 1 * 2 * 3 = 6. Vediamo quindi una funzione ricorsiva per calcolare il fattoriale di un numero:
public static int fattoriale(int n){ if (n == 0 || n == 1) return 1; return n * fattoriale (n-1); }
La funzione accetta in input un numero intero n (per semplicità non eseguiamo il controllo su n intero positivo) e verifica se n = 0 oppure n = 1. In tal caso restituisce 1, altrimenti richiama se stessa con n - 1. Se richiamassimo la funzione con n = 3, avremmo due chiamate ricorsive:
3 * fattoriale (2) e 3 * fattoriale (1)
con l'ultima chiamata si verifica la condizione di terminazione (n == 1) e la funzione restituisce 1 alla chiamata in cui n era uguale a 2, quindi verrà valutato 2 * 1 = 2 ed il valore restituito alla chiamata in cui n era uguale a 3, quindi valutato 3 * 2 = 6 e restituito il valore alla funzione chiamante.
La versione iterativa della funzione fattoriale sarebbe:
public static int fattoriale(int n){ int fatt = 1; while (1 <= n){ fatt = fatt * n; n = n - 1; } return fatt; }
Come si vede la versione ricorsiva è estremamente più semplice ed elegante.
