Recursão em

Sobre Recursão

A capacidade de algo ser definido em termos de si próprio chama-se recursão. No F#, a recursão encontra-se mais frequentemente nas 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 este acabe por corresponder 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 resulta 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)

As listas são frequentemente processadas de forma recursiva. Por exemplo, eis como usar a recursão para calcular o comprimento de uma lista:

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

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

Muitas das funções incorporadas são definidas de forma recursiva.

Um possível problema das funções recursivas é que cada chamada de função (recursiva) resulta em alocações na pilha, o que faz com que esta cresça. Como a pilha tem uma quantidade limitada de memória, as funções que usam muitas chamadas recursivas podem levar a que seja lançada uma StackOverflowException. O número de chamadas recursivas necessário para desencadear este comportamento depende de vários fatores, como a memória disponível na pilha e a quantidade de dados que cada chamada de função ocupa na pilha.

A melhor forma de evitar que as funções recursivas provoquem um transbordamento da pilha é escrevê-las como funções recursivas de cauda. Quando uma função é recursiva de cauda, o compilador pode otimizar o código que gera de forma a que não haja alocações adicionais na pilha a cada chamada recursiva. A única regra das funções recursivas de cauda é que o resultado de uma chamada recursiva deve ser devolvido diretamente pela função, não pode haver código adicional que processe o resultado dessa chamada. A forma mais comum de o fazer é criar uma função auxiliar que recebe um argumento acumulador adicional, que é atualizado a cada chamada recursiva e devolvido quando a recursão termina. Esta página explica em grande detalhe como o compilador processa as funções recursivas de cauda.

Eis uma versão recursiva de cauda da função que calcula o comprimento de uma lista:

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

let length list = lengthRecursive 0 list

É bastante comum definir a função auxiliar recursiva como uma função aninhada, o que esconde a natureza recursiva da função de quem a chama:

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

    lengthRecursive 0 list

O F# suporta tipos recursivos através de tipos de união discriminada. Um tipo de união discriminada recursivo tem um ou mais dos seus 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

Eis uma função (não recursiva de cauda) para trabalhar com o tipo recursivo acima:

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

layers (Layer Doll)
// => 1