Funções recursivas: a palavra-chave rec

A palavra-chave rec é usada junto com a palavra-chave let para definir uma função recursiva.

Sintaxe

// 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
...

Comentários

As funções recursivas – funções que se autodenominam – são identificadas explicitamente na linguagem F# com a palavra-chave rec. A palavra-chave rec disponibiliza o nome da associação let em seu corpo.

O exemplo a seguir mostra uma função recursiva que calcula o número Fibonaccin^th usando a definição matemática.

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

Observação

Na prática, código como o exemplo anterior não é ideal porque recompõe desnecessariamente valores que já foram calculados. Isso ocorre porque ele não é uma recursiva de cauda, o que é explicado mais adiante neste artigo.

Os métodos são implicitamente recursivos dentro do tipo em que são definidos, o que significa que não há necessidade de adicionar a palavra-chave rec. Por exemplo:

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

No entanto, as associações let as associações dentro das classes não são implicitamente recursivas. Todas as funções associadas let exigem a palavra-chave rec.

Recursão de cauda

Para algumas funções recursivas, é necessário refatorar uma definição mais "pura" para uma que seja recursiva de cauda. Isso evita recálculos desnecessários. Por exemplo, o gerador de números Fibonacci anterior pode ser reescrito da seguinte maneira:

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

Gerar um número Fibonacci é um grande exemplo de um algoritmo "ingênuo" matematicamente puro, mas ineficiente na prática. Embora essa seja uma implementação mais complicada, vários aspectos a tornam eficiente em F#, enquanto ainda permanecem recursivamente definidos:

• Uma função interna recursiva chamada loop, que é um padrão F# idiomático.
• Dois parâmetros de acumulador, que passam valores acumulados para chamadas recursivas.
• Uma verificação sobre o valor de n para retornar um acumulador específico.

Se este exemplo fosse escrito iterativamente com um loop, o código seria semelhante com dois valores diferentes acumulando números até que uma condição específica fosse atendida.

O motivo pelo qual isso é recursivo é porque a chamada recursiva não precisa salvar nenhum valor na pilha de chamadas. Todos os valores intermediários que estão sendo calculados são acumulados por meio de entradas para a função interna. Isso também permite que o compilador F# otimize o código para ser tão rápido quanto se você tivesse escrito algo como um loop while.

É comum escrever código F# que processa recursivamente algo com uma função interna e externa, como mostra o exemplo anterior. A função interna usa a recursão final, enquanto a função externa tem uma interface melhor para os chamadores.

A partir do F# 8.0, você pode usar o atributo TailCall para declarar explicitamente sua intenção de definir uma função recursiva de cauda para o compilador. O compilador avisará você se a sua função fizer chamadas recursivas sem caudas. Você pode usar o atributo em métodos e funções no nível do módulo.
Por exemplo, usá-lo na primeira definição de fib:

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

dispararia avisos do compilador sobre as duas chamadas recursivas sem caudas.

Funções mutuamente recursivas

Às vezes, as funções são mutuamente recursivas, o que significa que as chamadas formam um círculo, no qual uma função chama outra que, por sua vez, chama a primeira, com qualquer número de chamadas entre elas. Você deve definir essas funções em uma associação let, usando a palavra-chave and para vinculá-las.

O exemplo a seguir mostra duas funções mutuamente recursivas.

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)

Valores recursivos

Você também pode definir um valor associado a let a ser recursivo. Às vezes, isso é feito para registro em log. Com o F# 5 e a função nameof, você pode fazer isso:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Confira também

• Funções