Funções recursivas: A palavra-chave rec

A rec palavra-chave é usada juntamente com a let palavra-chave 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
...

Observações

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

O exemplo a seguir mostra uma função recursiva que calcula o n^ésimo número de Fibonacci usando a definição matemática.

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

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 rec palavra-chave. Por exemplo:

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

let No entanto, as ligações dentro das classes não são implicitamente recursivas. Todas as letfunções vinculadas requerem a rec palavra-chave.

Recursão da 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 de Fibonacci anterior pode ser reescrito assim:

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 de Fibonacci é um ótimo exemplo de um algoritmo "ingênuo" que é matematicamente puro, mas ineficiente na prática. Embora esta seja uma implementação mais complicada, vários aspetos a tornam eficiente em F# enquanto ainda permanecem definidas recursivamente:

• Uma função interna recursiva chamada loop, que é um padrão F# idiomático.
• Dois parâmetros acumuladores, que passam valores acumulados para chamadas recursivas.
• Uma verificação do valor de n para devolver 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.

A razão pela qual isso é tail-recursive é porque a chamada recursiva não precisa salvar nenhum valor na pilha de chamadas. Todos os valores intermédios que estão a ser calculados são acumulados através 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 while loop.

É 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 recursão de cauda, enquanto a função externa tem uma interface melhor para chamadores.

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

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

acionaria avisos do compilador sobre as duas chamadas recursivas não caudais.

Funções mutuamente recursivas

Às vezes, as funções são mutuamente recursivas, o que significa que as chamadas formam um círculo, onde uma função chama outra que, por sua vez, chama a primeira, com qualquer número de chamadas no meio. Você deve definir essas funções juntas em uma let ligação, usando a and palavra-chave 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 letvalor -bound para ser recursivo. Às vezes, isso é feito para o registro. Com o F# 5 e a função, você pode fazer o nameof seguinte:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Ver também

• Funções