Prezzo della pizza

Ricorsione

La capacità di una cosa di essere definita in termini di se stessa si chiama ricorsione. In F#, la ricorsione si trova più comunemente nelle funzioni ricorsive, cioè nelle funzioni che chiamano se stesse.

Una funzione ricorsiva deve avere almeno un caso base e almeno un caso ricorsivo. Un caso base restituisce un valore senza chiamare di nuovo la funzione. Un caso ricorsivo chiama di nuovo la funzione, modificando l'input in modo che a un certo punto corrisponda al caso base.

Le funzioni ricorsive si definiscono come le funzioni normali, ma con il modificatore rec. Senza questo modificatore, una funzione non sarà in grado di chiamare se stessa e qualsiasi tentativo di farlo produrrà un errore di compilazione. La ricorsione va quindi attivata esplicitamente.

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

F# supporta anche i tipi ricorsivi tramite le unioni discriminate. In un'unione discriminata ricorsiva, uno o più dei suoi casi fanno riferimento al tipo unione discriminata stesso all'interno dei loro dati. Come le funzioni ricorsive, anche i tipi ricorsivi devono avere un caso base. A differenza delle funzioni ricorsive, però, i tipi ricorsivi non usano la parola chiave rec.

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case