Recursión en

Acerca de Recursión

La capacidad de que algo se defina en términos de sí mismo se llama recursión. En F#, la recursión se encuentra con mayor frecuencia en las funciones recursivas, que son funciones que se llaman a sí mismas.

Una función recursiva necesita tener al menos un caso base y al menos un caso recursivo. Un caso base devuelve un valor sin volver a llamar a la función. Un caso recursivo vuelve a llamar a la función y modifica el argumento para que en algún momento coincida con el caso base.

Las funciones recursivas se definen como las funciones normales, pero con el modificador rec. Sin este modificador, una función no podrá llamarse a sí misma y cualquier intento de hacerlo dará como resultado un error de compilación. Por lo tanto, hay que optar explícitamente por la recursión.

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

Las listas a menudo se procesan de forma recursiva. Por ejemplo, así se usa la recursión para calcular la longitud de una lista:

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

Muchas de las funciones integradas se definen de forma recursiva.

Un posible problema con las funciones recursivas es que cada llamada a la función (recursiva) genera asignaciones en la pila, lo que hace que crezca. Como la pila tiene una cantidad limitada de memoria, las funciones que usan muchas llamadas recursivas pueden provocar que se lance una StackOverflowException. Cuántas llamadas recursivas desencadenan este comportamiento depende de varios factores, como la memoria disponible en la pila y cuántos datos ocupa cada llamada a la función en la pila.

La mejor manera de evitar que las funciones recursivas desborden la pila es escribirlas como funciones recursivas de cola. Cuando una función es recursiva de cola, el compilador puede optimizar su salida para que no haya asignaciones adicionales en la pila por cada llamada recursiva. La única regla para las funciones recursivas de cola es que el resultado de una llamada recursiva debe devolverse directamente desde la función; no debe haber ningún código adicional que procese el resultado de la llamada recursiva. La forma más común de hacerlo es crear una función auxiliar que reciba un argumento acumulador adicional, el cual se actualiza en cada llamada recursiva y se devuelve cuando termina la recursión. Esta página entra en gran detalle sobre cómo el compilador procesa las funciones recursivas de cola.

Aquí tienes una versión recursiva de cola de la función que calcula la longitud de una lista:

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

Es bastante común definir la función auxiliar recursiva como una función anidada, lo que oculta la naturaleza recursiva de la función a quien la llama:

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

F# admite tipos recursivos mediante tipos de unión discriminada. Un tipo de unión discriminada recursivo tiene uno o más de sus casos que hacen referencia al propio tipo de unión discriminada en sus datos. Al igual que las funciones recursivas, los tipos recursivos deben tener un caso base. A diferencia de las funciones recursivas, los tipos recursivos no usan la palabra clave rec.

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

Aquí tienes una función (no recursiva de cola) para trabajar con el tipo recursivo anterior:

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1