Introduzione a F# : Parte 3 - Le funzioni ricorsive in F#

Una delle caratteristiche più interessanti di F# è la sua propensione a utilizzare le funzioni ricorsive invece dei cicli, utilizzati nella programmazione imperativa. Le funzioni ricorsive sono più vantaggiose dei cicli, perché possono essere incorporate o invocate da altre funzioni, con un approccio molto simile alle espressioni matematiche. Vediamo, quindi, in modo più approfondito cosa intendiamo con funzioni ricorsive.

Ricorsività

Le funzioni ricorsive non sono molto semplici da assimilare dal punto di vista concettuale, soprattutto all’inizio, ma sono estremamente potenti. Per analizzare il funzionamento di una funzione ricorsiva bisogna cambiare nettamente punto di vista, passando da ogni stato “superiore” allo stato immediatamente “inferiore”, come scendendo di livello, e via via da un livello all’altro appena inferiore, procedendo verso una dimensione sempre più piccola finché non si raggiunge lo stato elementare, quello che non può più richiamare la funzione ricorsiva perché è uno stato elementare, una “singolarità”. In questo punto troviamo solitamente un “valore-sentinella” che impedisce di continuare e che impone di ritornare indietro. Da quel livello, poi, si ritorna al livello precedente, poi ancora quello precedente, sempre portandosi dietro il risultato di ciascun livello, fino a tornare al livello più esterno dove otterremo il risultato finale.

Confronto tra funzione “tradizionale” e funzione ricorsiva

Facciamo un esempio pratico della differenza tra una funzione con istruzioni imperative e una funzione ricorsiva: scorriamo in un ciclo i numeri da 1 a 100, li sommiamo e li visualizziamo in Console. Come probabilmente saprete, la somma dei numeri da 1 a 100 è uguale a 5.050 (per verificare il risultato potete semplicemente inserire i numeri da 1 a 100 in una colonna di un foglio Excel e selezionare la colonna: vedrete che la somma è proprio questa).

Con le istruzioni imperative possiamo scrivere un blocco di codice simile a quello seguente:

let funz =
let mutable somma = 0
for i in 1 .. 100 do
somma <- somma + i
somma
printfn "%A" funz

Qui abbiamo definito una funzione di nome funz, poi abbiamo dichiarato la variabile somma con la clausola mutable, perché in F# tutti gli identificativi sono immutabili e quindi se vogliamo una variabile modificabile dobbiamo dirlo esplicitamente a F#. È praticamente il contrario di quello che succede in C# dove abbiamo tutte variabili modificabili a meno che non dichiariamo una costante (non modificabile).

Subito dopo eseguiamo il ciclo da 1 a 100, sommando il valore dell’indice “i” nella variabile somma. Al termine del ciclo vediamo che c’è solo il nome della variabile somma: questo è il valore che viene restituito dalla funzione, perché ogni funzione deve restituire un valore.

Infine, il risultato viene visualizzato in Console.

A parte l’aspetto particolare della sintassi di F#, ci sembra che fino qui sia tutto chiaro e praticamente identico a quello che faremmo con C#.
Ora vediamo cosa succede se cambiamo il nostro punto di vista concettuale e ribaltiamo la funzione in una funzione ricorsiva.

Questo è il codice che possiamo definire per il risultato che vogliamo ottenere:

let rec somma n =
if n < 1 then 0
else n + somma (n-1)

let risultato = somma 100
printfn "%A" risultato

Abbiamo tre parti: la definizione della funzione ricorsiva di nome somma, l’istruzione che chiama la funzione passando il parametro 100 e registrando il risultato nell’identificatore risultato e, infine, la solita visualizzazione del risultato in Console.

Prima di tutto notiamo la parola riservata rec che indica che è una funzione ricorsiva. Subito dopo abbiamo il nome della funzione (somma), il parametro che passiamo alla funzione (n) e il simbolo = che serve a indicare che quello che segue è il corpo della funzione, il cui risultato è assegnato alla funzione somma.

La prima riga della definizione (if n < 1 then 0) impone che “se n è inferiore a 1, allora restituisci 0”. Questa è la classica istruzione “sentinella”: impedisce che la funzione ricorsiva continui all’infinito o, perlomeno, finché il programma non va in overflow.

La riga successiva, invece, esegue semplicemente la somma tra l’attuale numero e la somma delle esecuzioni precedenti, determinata dalla chiamata alla funzione medesima, passando il parametro (n-1).

Riepilogo del flusso delle istruzioni

1. Si parte con il valore massimo di n che è 100 e a questo si somma il valore della funzione somma, passando il parametro 99. Dato che non sappiamo ancora quanto vale la funzione somma a questo punto, l’operazione rimane momentaneamente in sospeso;
2. dato che viene chiamata di nuovo la funzione somma, si aggiunge al valore n=99 il risultato della funzione somma, passando il parametro 98. Anche in questo caso non abbiamo il risultato e quindi l’operazione resta in sospeso;
3. si va avanti chiamando sempre la funzione somma con il parametro n diminuito di una unità, finché non si arriva a n=0. A questo punto la funzione somma non viene più chiamata e si inizia a tornare indietro, di chiamata in chiamata, dove al primo passaggio si ritorna somma=0. Al secondo passaggio la somma diventa uguale a 1 + la precedente somma che era zero, quindi somma=1. Al terzo passaggio la somma diventa uguale a 2 + la precedente somma che era uguale a 1 e quindi somma = 3. Si continua così, fino a quando n=100 e la somma precedente che ha raccolto tutte le somme per 99 volte, ottenendo il risultato finale di 5.050.

In sostanza, il flusso è simile a quello che potete vedere nella Fig. 1 (anche se nella figura ci sono solo poche chiamate alla funzione somma, immaginate che ce ne siano 100).

Fig. 1 – Flusso delle chiamate della funzione somma (percorso verde) e del ritorno dei valori calcolati (percorso rosso).

Conclusione

Ovviamente l’esempio che abbiamo fatto è ben poca cosa, rispetto a funzioni che calcolano espressioni molto più complesse, ma crediamo di avervi mostrato come si definiscono e come si utilizzano le funzioni ricorsive in F#.

La nostra speranza è anche quella di essere riusciti a mostrarvi almeno qualche aspetto significativo delle capacità del linguaggio F#, un linguaggio (non solo) funzionale che forse non ha ancora espresso tutto il suo potenziale nello sviluppo di applicazioni anche di tipo commerciale.