recursividad - Ejemplo de la función recursiva de la cola F#

recursividad programacion

Question

Soy nuevo en F # y estaba leyendo sobre las funciones recursivas de la cola y esperaba que alguien pudiera darme dos implementaciones diferentes de una función foo: una que sea la cola recursiva y otra que no lo sea para que pueda entender mejor el principio.

Answer 1

Además, al realizar la prueba, no olvide que la recursión indirecta de cola (tailcall) está desactivada de forma predeterminada al compilar en el modo de depuración. Esto puede hacer que la recursión de la llamada final desborde la pila en el modo de depuración, pero no en el modo de lanzamiento.

Answer 2

Aquí hay un ejemplo más obvio, compárelo con lo que normalmente haría por un factorial.

let factorial n =
    let rec fact n acc =
        match n with
        | 0 -> acc
        | _ -> fact (n-1) (acc*n)
    fact n 1

Este es un poco complejo, pero la idea es que tenga un acumulador que mantenga una cuenta corriente, en lugar de modificar el valor de retorno.

Además, este estilo de envoltura suele ser una buena idea, ya que su interlocutor no necesita preocuparse por la siembra del acumulador (tenga en cuenta que el hecho es local a la función)

Answer 3

Estoy aprendiendo F # también. Las siguientes son funciones recursivas sin cola y funciones recursivas para calcular los números de fibonacci.

Versión recursiva sin cola

let rec fib = function
    | n when n < 2 -> 1
    | n -> fib(n-1) + fib(n-2);;

Versión recursiva cola

let fib n =
    let rec tfib n1 n2 = function
    | 0 -> n1
    | n -> tfib n2 (n2 + n1) (n - 1)
    tfib 0 1 n;;  

Nota: dado que el número de fibanacci podría crecer realmente rápido, podría reemplazar la última línea tfib 0 1 n a
tfib 0I 1I n para aprovechar la estructura Numerics.BigInteger en F #

Answer 4

Un intento de una explicación más corta que en los otros ejemplos:

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

let rec bar acc n =
    match n with
    | 0 -> acc
    | _ -> bar (acc+2) (n-1)

foo no es cola recursiva, porque foo tiene que llamar a foo recursivamente para evaluar "2 + foo (n-1)" y devolverlo.

la barra es cola recursiva, porque la barra no tiene que usar el valor de retorno de la llamada recursiva para devolver un valor. Simplemente puede dejar que la barra llamada recursivamente retorne su valor inmediatamente (sin que reaparezca completamente a través de la pila de llamadas). El compilador ve esto y "engaña" al reescribir la recursión en un bucle.

Cambiar la última línea en la barra a "| _ -> 2+ (barra (acc + 2) (n-1))" destruiría la recursividad del final de la cola.

Answer 5

Comience con una tarea simple, como asignar elementos de ''a'' a b en una lista. Queremos escribir una función que tenga la firma.

val map: (''a -> ''b) -> ''a list -> ''b list

Dónde

map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]

Comience con la versión recursiva sin cola :

let rec map f = function
    | [] -> []
    | x::xs -> f x::map f xs

Esto no es una cola recursiva porque la función aún tiene trabajo por hacer después de hacer la llamada recursiva. :: es azúcar sintáctica para List.Cons(fx, map f xs) .

La naturaleza no recursiva de la función podría ser un poco más obvia si reescribiera la última línea como | x::xs -> let temp = map f xs; fx::temp | x::xs -> let temp = map f xs; fx::temp | x::xs -> let temp = map f xs; fx::temp - obviamente está funcionando después de la llamada recursiva.

Usa una variable acumuladora para hacerla cola recursiva:

let map f l =
    let rec loop acc = function
        | [] -> List.rev acc
        | x::xs -> loop (f x::acc) xs
    loop [] l

Aquí estamos construyendo una nueva lista en una variable acc . Dado que la lista se construye a la inversa, necesitamos revertir la lista de salida antes de devolvérsela al usuario.

Si te encuentras con una pequeña distorsión mental, puedes usar el pase de continuación para escribir el código de manera más sucinta:

let map f l =
    let rec loop cont = function
        | [] -> cont []
        | x::xs -> loop ( fun acc -> cont (f x::acc) ) xs
    loop id l

Dado que la llamada a loop y cont son las últimas funciones llamadas sin trabajo adicional, son recursivas.

Esto funciona porque la continuación de cont es capturada por una nueva continuación, que a su vez es capturada por otra, resultando en una especie de estructura de datos tipo árbol como sigue:

(fun acc -> (f 1)::acc)
    ((fun acc -> (f 2)::acc)
        ((fun acc -> (f 3)::acc)
            ((fun acc -> (f 4)::acc)
                ((fun acc -> (f 5)::acc)
                    (id [])))))

que crea una lista en orden sin necesidad de revertirla.

Por lo que vale la pena, comience a escribir funciones de forma recursiva sin cola, son más fáciles de leer y trabajar con ellas.

Si tiene una lista grande para revisar, use una variable de acumulador.

Si no puede encontrar una manera de usar un acumulador de una manera conveniente y no tiene otras opciones a su disposición, use las continuaciones. Personalmente considero el uso no trivial y pesado de las continuaciones difíciles de leer.