Recursión en

Acerca de Recursión

La capacidad de algo de definirse en términos de sí mismo se llama recursión. En F#, la recursión aparece 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, modificando la entrada para que en algún momento coincida con el caso base.

Las funciones recursivas se definen igual que 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á lugar a 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 suelen procesarse 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 están definidas de forma recursiva.

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

La mejor forma 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 de modo que no haya asignaciones adicionales en la pila por cada llamada recursiva a la función. 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 habitual de hacerlo es crear una función auxiliar que recibe un argumento acumulador adicional, el cual se actualiza en cada llamada recursiva y se devuelve cuando termina la recursión. Esta página explica con gran detalle cómo procesa el compilador 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 habitual definir la función auxiliar recursiva como una función anidada, lo que oculta su naturaleza recursiva 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 varios de sus casos que se refieren 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