Funzioni ricorsive: parola chiave rec

Articolo
11/10/2023

La rec parola chiave viene usata insieme alla let parola chiave per definire una funzione ricorsiva.

Sintassi

// Recursive function:
let rec function-name parameter-list =
    function-body

// Mutually recursive functions:
let rec function1-name parameter-list =
    function1-body

and function2-name parameter-list =
    function2-body
...

Osservazioni:

Le funzioni ricorsive, ovvero funzioni che chiamano se stesse, vengono identificate in modo esplicito nel linguaggio F# con la rec parola chiave . La rec parola chiave rende disponibile il nome dell'associazione let nel corpo.

Nell'esempio seguente viene illustrata una funzione ricorsiva che calcola il numero n^di Fibonacci usando la definizione matematica.

let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

Nota

In pratica, il codice come l'esempio precedente non è ideale perché ricompila inutilmente i valori già calcolati. Ciò è dovuto al fatto che non è ricorsivo dalla coda, come illustrato più avanti in questo articolo.

I metodi sono in modo implicito ricorsivo all'interno del tipo in cui sono definiti, ovvero non è necessario aggiungere la rec parola chiave . Ad esempio:

type MyClass() =
    member this.Fib(n) =
        match n with
        | 0 | 1 -> n
        | n -> this.Fib(n-1) + this.Fib(n-2)

let le associazioni all'interno delle classi non sono però ricorsive in modo implicito. Tutte le letfunzioni associate richiedono la rec parola chiave .

Ricorsione della parte finale

Per alcune funzioni ricorsive, è necessario effettuare il refactoring di una definizione più "pura" a una coda ricorsiva. In questo modo si evitano ricomputazioni non necessarie. Ad esempio, il generatore di numeri di Fibonacci precedente può essere riscritto come segue:

let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ ->
            loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

La generazione di un numero di Fibonacci è un ottimo esempio di algoritmo "ingenuo" che è matematicamente puro ma inefficiente in pratica. Anche se si tratta di un'implementazione più complessa, diversi aspetti lo rendono efficiente in F# pur rimanendo in modo ricorsivo:

Funzione interna ricorsiva denominata loop, che è un modello F# idiomatico.
Due parametri dell'accumulatore, che passano valori accumulati alle chiamate ricorsive.
Controllo sul valore di n per restituire un diagramma specifico.

Se questo esempio è stato scritto in modo iterativo con un ciclo, il codice sarà simile a due valori diversi accumulando numeri fino a quando non viene soddisfatta una determinata condizione.

Il motivo per cui si tratta di una coda ricorsiva è dovuto al fatto che la chiamata ricorsiva non deve salvare alcun valore nello stack di chiamate. Tutti i valori intermedi calcolati vengono accumulati tramite input alla funzione interna. In questo modo il compilatore F# consente anche di ottimizzare il codice come se fosse stato scritto qualcosa di simile a un while ciclo.

È comune scrivere codice F# che elabora in modo ricorsivo un elemento con una funzione interna ed esterna, come illustrato nell'esempio precedente. La funzione interna usa la ricorsione della parte finale, mentre la funzione esterna ha un'interfaccia migliore per i chiamanti.

A partire da F# 8.0, è possibile usare l'attributo per dichiarare in modo esplicito l'intenzione TailCall di definire una funzione ricorsiva della parte finale al compilatore. Il compilatore avvisa quindi se la funzione esegue chiamate ricorsive non tail. È possibile usare l'attributo nei metodi e nelle funzioni a livello di modulo.
Ad esempio, usandolo nella prima fib definizione:

[<TailCall>]
let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

attiverebbe avvisi del compilatore sulle due chiamate ricorsive non tail.

Funzioni ricorsive a vicenda

A volte le funzioni sono ricorsive a vicenda, vale a dire che le chiamate formano un cerchio, dove una funzione chiama un'altra che a sua volta chiama il primo, con un numero qualsiasi di chiamate tra di esse. È necessario definire queste funzioni insieme in un'unica let associazione, usando la and parola chiave per collegarle.

L'esempio seguente illustra due funzioni ricorsive a vicenda.

let rec Even x = if x = 0 then true else Odd(x - 1)
and Odd x = if x = 0 then false else Even(x - 1)

Valori ricorsivi

È anche possibile definire un letvalore associato a un valore ricorsivo. Questa operazione viene talvolta eseguita per la registrazione. Con F# 5 e la nameof funzione è possibile eseguire questa operazione:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Vedi anche

Funzioni

Condividi tramite