Preços de pizza

Recursão

A capacidade de algo ser definido em termos de si mesmo chama-se recursão. Em F#, a recursão aparece mais frequentemente em funções recursivas, que são funções que se chamam a si próprias.

Uma função recursiva tem de ter pelo menos um caso base e pelo menos um caso recursivo. Um caso base devolve um valor sem voltar a chamar a função. Um caso recursivo volta a chamar a função, modificando o valor de entrada para que, em algum momento, este corresponda ao caso base.

As funções recursivas definem-se como as funções normais, mas com o modificador rec. Sem este modificador, uma função não consegue chamar-se a si própria e qualquer tentativa de o fazer resultará num erro de compilação. Por isso, é preciso optar explicitamente pela recursão.

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

F# também suporta tipos recursivos através de tipos de união discriminada. Um tipo de união discriminada recursivo tem um ou mais casos que se referem ao próprio tipo de união discriminada nos seus dados. Tal como as funções recursivas, os tipos recursivos têm de ter um caso base. Ao contrário das funções recursivas, os tipos recursivos não usam a palavra-chave rec.

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