recursion - recursiva - recursividad directa e indirecta

recursividad de cola vs. recursión hacia adelante

Question

¿Puede alguien darme la diferencia entre estas dos clases de recurrencias y ejemplos (específicamente en OCaml)?

Answer 1

Aquí hay un ejemplo de una función factorial recursiva de cola:

let fac n =
let rec f n a =
    match n with
    0 -> a
    | _ -> f (n-1) (n*a)
in
f n 1

Aquí está su contraparte recursiva sin cola:

let rec non_tail_fac n =
match n with
0 -> 1
| _ -> (non_tail_fac n-1) * n

La función recursiva de cola utiliza un acumulador, a, para almacenar el valor del resultado de la llamada anterior. Esto permite que OCaml realice la optimización de la llamada de cola, lo que da como resultado que la pila no se desborde. Típicamente, una función recursiva de cola usará un valor de acumulador para permitir que ocurra la optimización de la llamada de cola.

Answer 2

Por ejemplo, una función recursiva build_word que toma una char list y los combina con una cadena, es decir [''f''; ''o''; ''o''] [''f''; ''o''; ''o''] [''f''; ''o''; ''o''] a la secuencia "foo" . El proceso de inducción se puede visualizar de esta manera:

build_word [''f''; ''o''; ''o'']
"f" ^ (build_word [''o''; ''o''])
"f" ^ ("o" ^ (build_word [''o''])    // base case! return "o" and fold back
"f" ^ ("o" ^ ("o"))
"f" ^ ("oo")
"foo"

Esa fue una recursión normal. Tenga en cuenta que cada par de paréntesis representa un nuevo marco de pila o llamada recursiva. La solución a este problema (es decir, "f", "fo" o "foo") no puede derivarse antes del final de la recursión (donde se cumple el caso base). Solo entonces el último cuadro devuelve el último resultado al anterior antes de "explotar", y viceversa.

En teoría, cada llamada crea un nuevo marco de pila (o alcance, si se quiere) para mantener el "lugar" para que la solución fragmentada se devuelva y se recopile hacia el principio. Esto puede conducir a (este enlace es una recursividad por cierto).

Una versión de llamada final se vería así:

build_word [''f''; ''o''; ''o''] ""
build_word [''o''; ''o''], "f"
build_word [''o''] ("f" ^ "o")
build_word [] ("f" ^ "o" ^ "o")
"foo"

Aquí, el resultado acumulado (a menudo almacenado en una variable conocida como accumulator ) se está transmitiendo. Con la optimización, la llamada de cola no tendría que crear un nuevo marco de pila porque no tiene que mantener los anteriores. La solución está siendo resuelta "hacia adelante" en lugar de "hacia atrás".

Aquí están las funciones build_word en dos versiones:

sin cola

let build_word chars = 
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd :: tl -> build_word tl
;;

cola

let build_word ?(acc = "") chars =
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd::tl -> build_word ~acc:(acc ^ Char.to_string hd) tl
;;

La recursión hacia adelante está bien explicada en la respuesta aceptada por @ sepp2k.

Answer 3

Una función recursiva de cola es una función donde la única llamada recursiva es la última en la función. Una función recursiva sin cola es una función donde ese no es el caso.

Una recursión hacia atrás es una recursión donde en cada llamada recursiva el valor del parámetro es menor que en el paso anterior. Una recursión hacia adelante es una recursión donde crece con cada paso.

Esos son dos conceptos ortogonales, es decir, una recursión hacia adelante puede o no ser recursiva de cola y lo mismo se aplica a las recursiones hacia atrás.

Por ejemplo, la función factorial a menudo se escribe así en idiomas imperativos:

fac = 1
for i from 1 to n:
    fac := fac * i

La versión recursiva común de factorial cuenta hacia atrás (es decir, se llama a sí misma con n-1 como parámetro); sin embargo, si tradujes directamente la solución imperativa anterior, obtendrás una versión recursiva que cuenta hacia arriba. Se vería algo como esto:

let fac n =
  let rec loop i =
    if i >= n
    then i
    else i * loop (i+1)
  in
    loop 1

Esta es una recursión hacia adelante y, como pueden ver, es un poco más engorrosa que la variante recursiva hacia atrás, ya que requiere una función de ayuda. Ahora bien, esto no es recursivo de cola ya que la última llamada en el loop es la multiplicación, no la recursión. Entonces, para que sea recursivo, harías algo como esto:

let fac n =
  let rec loop acc i =
    if i >= n
    then acc
    else loop (i*acc) (i+1)
  in
    loop 1 1

Ahora bien, esto es tanto una recursión hacia adelante como una recursión final porque la llamada recursiva es a) una llamada de cola yb) se llama a sí misma con un valor mayor ( i+1 ).