Funciones recursivas: la palabra clave rec

La rec palabra clave se usa junto con la let palabra clave para definir una función recursiva.

Sintaxis

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

Observaciones

Las funciones recursivas ( funciones que se llaman a sí mismas) se identifican explícitamente en el lenguaje F# con la rec palabra clave . La rec palabra clave hace que el nombre del let enlace esté disponible en su cuerpo.

En el ejemplo siguiente se muestra una función recursiva que calcula el número nº Fibonacci mediante la definición matemática.

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

Nota:

En la práctica, el código como el ejemplo anterior no es ideal porque vuelve a calcular innecesariamente los valores que ya se han calculado. Esto se debe a que no es recursivo de cola, que se explica más adelante en este artículo.

Los métodos son recursivos implícitamente dentro del tipo en el que se definen, lo que significa que no es necesario agregar la rec palabra clave . Por ejemplo:

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

let sin embargo, los enlaces dentro de las clases no son recursivos implícitamente. Todas las letfunciones enlazadas requieren la rec palabra clave .

Recursividad de cola

Para algunas funciones recursivas, es necesario refactorizar una definición más "pura" a una que sea recursiva de cola. Esto evita las recomputaciones innecesarias. Por ejemplo, el generador de números de Fibonacci anterior se puede reescribir de esta manera:

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

Generar un número de Fibonacci es un gran ejemplo de un algoritmo "naïve" que es matemáticamente puro pero ineficaz en la práctica. Aunque se trata de una implementación más complicada, varios aspectos hacen que sea eficaz en F# mientras se sigue definiendo de forma recursiva:

• Función interna recursiva denominada loop, que es un patrón F# idiomático.
• Dos parámetros de acumulador, que pasan valores acumulados a llamadas recursivas.
• Comprobación del valor de n para devolver un acumulador específico.

Si este ejemplo se escribiera de forma iterativa con un bucle, el código tendría un aspecto similar con dos valores diferentes acumulando números hasta que se cumple una condición determinada.

La razón por la que se trata de una cola recursiva es porque la llamada recursiva no necesita guardar ningún valor en la pila de llamadas. Todos los valores intermedios que se calculan se acumulan a través de entradas a la función interna. Esto también permite al compilador de F# optimizar el código para que sea tan rápido como si hubiera escrito algo como un while bucle.

Es habitual escribir código F# que procesa de forma recursiva algo con una función interna y externa, como se muestra en el ejemplo anterior. La función interna usa la recursividad de cola, mientras que la función externa tiene una mejor interfaz para los autores de llamadas.

A partir de F# 8.0, puede usar el TailCall atributo para indicar explícitamente la intención de definir una función de cola recursiva al compilador. A continuación, el compilador le advertirá si la función realiza llamadas recursivas que no son de cola. Puede usar el atributo en métodos y funciones de nivel de módulo.
Por ejemplo, después de usarlo en la primera fib definición:

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

desencadenaría advertencias del compilador sobre las dos llamadas recursivas que no son de cola.

Funciones mutuamente recursivas

A veces, las funciones son mutuamente recursivas, lo que significa que las llamadas forman un círculo, donde una función llama a otra que, a su vez, llama a la primera, con cualquier número de llamadas entre sí. Debe definir estas funciones juntas en un let enlace, usando la and palabra clave para vincularlas juntas.

En el ejemplo siguiente se muestran dos funciones recursivas mutuamente.

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

También puede definir un letvalor enlazado para que sea recursivo. Esto a veces se hace para el registro. Con F# 5 y la nameof función, puede hacerlo:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Consulte también

• Funciones