Ricorsione in

Informazioni su Ricorsione

La capacità di qualcosa di essere definito in termini di se stesso si chiama ricorsione. In F#, la ricorsione si trova più comunemente nelle funzioni ricorsive, cioè 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 potrà chiamare se stessa e qualsiasi tentativo di farlo comporterà un errore di compilazione. La ricorsione va quindi scelta esplicitamente.

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

Gli array vengono spesso elaborati in modo ricorsivo. Per esempio, ecco come usare la ricorsione per calcolare la lunghezza di un array:

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

Molte delle funzioni integrate sono definite in modo ricorsivo.

Un possibile problema con le funzioni ricorsive è che ogni chiamata (ricorsiva) alla funzione comporta allocazioni sullo stack, che quindi cresce. Dato che lo stack ha una quantità limitata di memoria, le funzioni che fanno molte chiamate ricorsive possono far sì che venga lanciata un'eccezione StackOverflowException. Quante chiamate ricorsive facciano scattare questo comportamento dipende da diversi fattori, come la memoria disponibile sullo stack e quanto spazio occupa sullo stack ogni chiamata alla funzione.

Il modo migliore per evitare che le funzioni ricorsive facciano overflow sullo stack è scriverle come funzioni ricorsive in coda. Quando una funzione è ricorsiva in coda, il compilatore può ottimizzare l'output in modo che non ci siano allocazioni aggiuntive sullo stack per ogni chiamata ricorsiva. L'unica regola per le funzioni ricorsive in coda è che il risultato di una chiamata ricorsiva deve essere restituito direttamente dalla funzione: non deve esserci altro codice che elabori il risultato della chiamata ricorsiva. Il modo più comune per farlo è creare una funzione ausiliaria che prende un ulteriore argomento accumulatore, aggiornato per ogni chiamata ricorsiva e restituito quando la ricorsione termina. Questa pagina spiega in grande dettaglio come il compilatore elabora le funzioni ricorsive in coda.

Ecco una versione ricorsiva in coda della funzione che calcola la lunghezza di un array:

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

È abbastanza comune definire la funzione ausiliaria ricorsiva come funzione annidata, il che nasconde al chiamante la natura ricorsiva della funzione:

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

F# supporta i tipi ricorsivi tramite i tipi unione discriminata. In un tipo unione discriminata ricorsivo, uno o più casi fanno riferimento al tipo unione discriminata stesso nei loro dati. Come le funzioni ricorsive, i tipi ricorsivi devono avere un caso base. A differenza delle funzioni ricorsive, i tipi ricorsivi non usano la parola chiave rec.

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

Ecco una funzione (non ricorsiva in coda) che lavora con il tipo ricorsivo qui sopra:

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1