Funciones recursivas: 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
...

Comentarios

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^de 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 recomputaciones innecesarias. Por ejemplo, el generador de números de Fibonacci anterior se puede reescribir de la siguiente 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 buen ejemplo de un algoritmo «ingenuo» 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:

• Una función interna recursiva denominada loop, que es un patrón de 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 cumpla una condición determinada.

El motivo por el que se trata de tail-recursive 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 de 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 llamadores.

A partir de F# 8.0, puede utilizar el atributo TailCall para indicar explícitamente al compilador su intención de definir una función recursiva de cola. El compilador le advertirá entonces si su función hace llamadas recursivas que no estén en cola. Puede utilizar el atributo en métodos y funciones a nivel de módulo.
Por ejemplo, utilizándolo en la primera definición fib:

[<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 sin 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í. Debes definir estas funciones juntas en un enlace let, mediante la palabra clave and 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 puedes definir un letvalor enlazado para que sea recursivo. Esto se hace a veces para el registro. Con F# 5 y la nameof función, puedes hacerlo:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Vea también

• Funciones