Primi passi con F# - La successione di Fibonacci

Oggi vediamo un esempio di funzione ricorsiva e di pattern matching con F#. Per farlo presenteremo una semplice implementazione della notissima funzione di Fibonacci.

La funzione che implementeremo riceverà in input un intero n e restituirà l'n-esimo numero della successione di Fibonacci. Per maggiori dettagli sulla matematica consigliamo wikipedia. Il codice consisterà essenzialmente in due funzioni, una nidificata dentro l'altra. La funzione più interna è ricorsiva, come indicato anche dal modificatore "rec" obbligatorio in F#.

let Fibonacci n = 
        let rec fib x = 
            match x with 
            | u::v::_ when x.Length < n -> fib (u+v::x) 
            | [] -> fib [1] 
            | u::[] -> fib [1;1] 
            | _ -> x               
        let risu = fib [] 
        risu.Head

La funzione "fib" prende in input una lista di interi e poi fa il "match" contro diversi pattern, il codice aggiunge un nuovo numero alla successione ottenuto sommando gli ultimi due. Il punto fondamentale è il terzo pattern, dove "bindiamo" gli ultimi due valore della successione alle variabili "u" e "v" e poi tralasciamo il resto con il simbolo "wildcard" _ fermandoci quando la lunghezza della lista raggiunge il valore "n". I primi due pattern gestiscono i casi in cui non abbiamo 2 elementi. L'ultimo pattern fa il match con qualunque sequenza non venga coperta dai casi precedenti e ritorna la sequenza stessa.

Supponiamo che n=5, il primo "calcolo" del codice avviene alla riga 9 dove viene chiamata la funzione ricorsiva, riportiamo la sequenza di argomenti e risultati della funzione "fib" di ognuna delle chiamate:

1)  x = [], match con il secondo pattern, restituisce [1]

2) x = [1], match con il terzo pattern, restituisce [1,1]

3) x = [1,1] e lunghezza = 2 < n  = 5, match con il primo pattern, restituisce [2,1,1]

4) x = [2,1,1] e lunghezza = 3 < n  = 5, match con il primo pattern, restituisce [3,2,1,1]

5) x = [3,2,1,1] e lunghezza = 4 < n  = 5, match con il primo pattern, restituisce [5,3,2,1,1]

6) x = [5,3,2,1,1] e lunghezza = 5 = n, può fare match solo con l'ultimo pattern e restituisce [5,3,2,1,1]