Recursão em

Sobre Recursão

A capacidade de algo ser definido em termos de si mesmo chama-se recursão. Em F#, a recursão aparece com mais frequência nas funções recursivas, que são funções que chamam a si mesmas.

Uma função recursiva precisa ter pelo menos um caso base e pelo menos um caso recursivo. Um caso base retorna um valor sem chamar a função de novo. Um caso recursivo chama a função de novo, modificando a entrada para que em algum momento ela corresponda ao caso base.

As funções recursivas são definidas como funções normais, mas com o modificador rec. Sem esse modificador, uma função não consegue chamar a si mesma, e qualquer tentativa de fazê-lo resulta em um erro de compilação. A recursão, portanto, precisa ser habilitada explicitamente.

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

Listas costumam ser processadas de forma recursiva. Por exemplo, veja 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 internas são definidas de forma recursiva.

Um possível problema com as funções recursivas é que cada chamada (recursiva) da função gera alocações na pilha, fazendo com que ela cresça. Como a pilha tem uma quantidade limitada de memória, funções que fazem muitas chamadas recursivas podem fazer com que uma StackOverflowException seja lançada. Quantas chamadas recursivas acionam esse comportamento depende de vários fatores, como a memória disponível na pilha e quantos dados cada chamada da função ocupa na pilha.

A melhor forma de evitar que funções recursivas estourem a pilha é escrevê-las como funções recursivas de cauda. Quando uma função é recursiva de cauda, o compilador pode otimizar sua saída de modo 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 retornado diretamente pela função, sem nenhum código adicional que processe o resultado da chamada recursiva. A forma mais comum de fazer isso é criar uma função auxiliar que recebe um argumento acumulador adicional, atualizado a cada chamada recursiva e retornado quando a recursão termina. Esta página entra em grande detalhe sobre como o compilador processa as funções recursivas de cauda.

Veja a versão recursiva de cauda da função de 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

É bem 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# dá suporte a tipos recursivos por meio de tipos de união discriminada. Em um tipo de união discriminada recursivo, um ou mais de seus casos referenciam o próprio tipo de união discriminada em seus dados. Assim como as funções recursivas, os tipos recursivos precisam ter um caso base. Diferentemente das funções recursivas, os tipos recursivos não usam a palavra-chave rec.

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

Veja 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