F# - Funzioni ricorsive

Nel mondo dell'informatica odierna viene spesso incontrata l'espressione di funzione ricorsiva, una funzionalità che possiedono alcuni dei linguaggi di programmazione, molto utile al giorno d'oggi nello sviluppo delle applicazioni, perché permettono di semplificare estremamente il codice di un programma, che utilizza determinate strutture dati.

Vediamo più in dettaglio perché questa funzionalità è così importante al giorno d'oggi. Il motivo più importante che spinge i nuovi linguaggi di programmazione ad avere la possibilità di scrivere funzioni ricorsive è che la correttezza di una funzione ricorsiva è possibile dimostrare matematicamente sfruttando la dimostrazione per induzione, per cui viene resa possibile la ricerca matematica della soluzione ad un problema e la successiva traduzione dell'algoritmo matematico in codice.

Fino ad ora si è parlato delle funzioni ricorsive, ma non è stato ancora detto cosa sono, per cui procediamo con la definizione di esse: una funzione è detta ricorsiva quando nel suo corpo esegue una chiamata a se stessa, ovvero rincorre se stessa come fa il cane con la sua coda. 

Ma proviamo a vedere come si fa a creare una funzione ricorsiva in F#. Beh, è molto semplice, perché non ci sono molte differenze rispetto alla definizione di una normale funzione. L'unica differenza sta nel fatto che dobbiamo dichiarare esplicitamente che la funzione che stiamo definendo è una funzione ricorsiva, aggiungendo dopo let la parola chiave rec, inoltre non dobbiamo dimenticarci che la funzione deve richiamare se stessa per almeno una volta:

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

La funzione somma deve sostanzialmente restituire il risultato della somma di tutti i numeri interi da 0 a n. Ciò viene fatto sommando n alla somma di tutti i numeri da 0 a (n-1). Quando arriviamo alla condizione in cui n<1 restituiamo 0, e il ciclo si interrompe. La funzione può essere capita più facilmente analizzando i passaggi che esegue un compilatore in un esempio:

somma 5 -> (5 non è minore di 1, quindi esegue l'istruzione del ramo else)
5+(somma 4) -> (4 non è minore di 1, quindi esegue l'istruzione del ramo else)
5+(4+(somma 3)) -> (3 non è minore di 1, quindi esegue l'istruzione del ramo else)
5+(4+(3+(somma 2))) -> (2 non è minore di 1, quindi esegue l'istruzione del ramo else)
5+(4+(3+(2+(somma 1)))) -> (1 non è minore di 1, quindi esegue l'istruzione del ramo else)
5+(4+(3+(2+(1+(somma 0))))) -> (0<1, quindi restituisce 0)
5+(4+(3+(2+(1+0))))
5+(4+(3+(2+1)))
5+(4+(3+3))
5+(4+6)
5+10
15

Come potete vedere il risultato restituito dalla funzione è 15, che è uguale alla somma dei numeri interi da 0 a 5. Infatti, se guardiamo il 7° passaggio possiamo identificare proprio la somma dei primi n numeri naturali. E adesso, tolto il dubbio della correttezza della funzione, analizziamo perché è stato possibile arrivare a questo risultato. In pratica noi non abbiamo fatto altro che riutilizzare la funzione stessa, però passandogli un parametro, che è minore di 1 del precedente, finché siamo arrivati alla condizione in cui sappiamo con certezza qual è il risultato che la funzione deve restituire. Questa condizione viene chiamata caso base. A quel punto è diventato possibile il calcolo del risultato della funzione, il cui parametro è maggiore di 1 e così via, fino ad arrivare a n. 

Riassumendo, per scrivere una funzione ricorsiva dobbiamo trovare un caso base, ovvero una condizione in cui sappiamo con certezza il risultato della funzione, e richiamare la funzione stessa, modificando il parametro della funzione, per avvicinarlo al caso base, perché se il caso base non si verifica la funzione non termina.

Proviamo adesso a scrivere una funzione fatt, che calcolerà il fattoriale di un certo numero intero n>0. Ma prima di scrivere direttamente il codice della funzione vediamo la definizione matematica del fattoriale:

0! = 1
n! = n * (n-1)!

Partendo da questa definizione matematica, scrivere la funzione fatt sarà un gioco da ragazzi, perché il caso base è quando dobbiamo calcolare il fattoriale di 0, mentre in tutti gli altri casi basta moltiplicare n per il fattoriale di (n-1):

let rec fatt n =
    if n=0 then 1
    else n*(fatt (n-1));;

La funzione è praticamente identica alla precedente e, una cosa molto bella di F#, se proviamo a tradurre il codice in italiano otteniamo proprio la definizione matematica della funzione fattoriale. E questa è il vero punto di forza della programmazione funzionale. 

Ma se da una parte l'impiego delle funzioni ricorsive nella programmazione permette di semplificare notevolmente il codice di un programma, dall'altra parte viene richiesta molta più memoria rispetto alle versioni iterative delle funzioni, che vedremo più avanti.