F # Tail Recursive Function Example

Question

Soy nuevo en F # y estaba leyendo acerca de las funciones recursivas de la cola y esperaba que alguien pudiera darme dos implementaciones diferentes de una función foo, una que es recursiva de cola y otra que no lo es. comprender mejor el principio.

Answer 1

Comience con una tarea simple, como asignar elementos de 'a a' b en una lista. Queremos escribir una función que tiene 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] 

de inicio con no recursiva cola versión:

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

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

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

utilizar un acumulador variable de para que sea recursiva cola:

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 al revés, necesitamos invertir la lista de salida antes de devolverla al usuario.

Si estás en un poco de urdimbre mente, se puede utilizar continuación pasa para escribir el código de forma 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 

Desde la llamada a loop y cont son las últimas funciones llamadas sin trabajo adicional, son recursivas de la cola.

Esto funciona porque la continuación cont es capturado por una nueva continuación, que a su vez es capturado por otro, lo que resulta en una especie de estructura de datos de árbol similar a la siguiente:

(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 se acumula una lista en orden sin necesidad de revertirlo.

---

Por lo que su valor, empezar a escribir funciones en forma recursiva no la cola, son más fáciles de leer y trabajar con ellos.

Si tiene que completar una gran lista, use una variable de acumulador.

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

Answer 2

Un intento de una explicación más corto 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 foo de forma recursiva con el fin de evaluar "2 + foo (n-1)" y devolverlo.

barra es recursivo de cola, porque la barra no tiene que usar el valor de retorno de la llamada recursiva para devolver un valor. Puede dejar que la barra llamada recursivamente devuelva su valor inmediatamente (sin volver a subir por la pila de llamadas). El compilador ve esto y 'trucos' reescribiendo la recursión en un bucle.

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

Answer 3

Además, al realizar pruebas, no olvide que la recursión de cola indirecta (tailcall) se desactiva de forma predeterminada al compilar en modo Depuración. Esto puede provocar que la recursión de tailcall desborde la pila en modo Debug pero no en modo Release.

Answer 4

Este es un ejemplo más obvio, compáralo con lo que normalmente harías para un factorial.

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

Ésta es un poco compleja, pero la idea es que usted tiene un acumulador que mantiene una cuenta corriente, en lugar de modificar el valor de retorno.

Además, este estilo de envoltura es generalmente una buena idea, de esa manera la persona que llama no tiene que preocuparse por la siembra del acumulador (tenga en cuenta este hecho es local a la función)

Answer 5

estoy aprendiendo F # demasiado . Las siguientes son recursivas sin cola y función recursiva de cola para calcular los números de fibonacci.

no cola versión recursiva

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

cola versión recursiva

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 fibanacci podría crecer muy rápido podría reemplazar última línea tfib 0 1 n-
tfib 0I 1I n para aprovechar la estructura Numerics.BigInteger en F #