Funções recursivas: a palavra-chave rec

A rec palavra-chave é usada junto 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 chamam - são identificadas explicitamente na linguagem F# com a rec palavra-chave. A rec palavra-chave disponibiliza o nome da let associação em seu corpo.

O exemplo a seguir mostra uma função recursiva que calcula o n^número fibonacci 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 recompila desnecessariamente valores que já foram computados. Isso ocorre porque ele não é recursivo final, 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 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 associações dentro das classes não são implicitamente recursivas. Todas as letfunções associadas exigem 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 impede recomputações desnecessárias. Por exemplo, o gerador de número 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# e 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 do valor de n 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 final é 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 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 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 TailCall atributo para declarar explicitamente sua intenção de definir uma função recursiva de cauda para o compilador. Em seguida, o compilador avisará se a função fizer chamadas recursivas que não sejam de cauda. 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)

dispararia avisos do compilador sobre as duas chamadas recursivas não traseiras.

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 em uma associação let , 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 associado a ser recursivo. Às vezes, isso é feito para registrar em log. Com f# 5 e a nameof função, você pode fazer isso:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Consulte também

• Funções