¿Es esta implementación recursiva recursiva

Question

? Leí en un libro algorítmico que la función de Ackermann no puede ser recursiva por la cola (lo que dicen es "no se puede transformar en una iteración"). Estoy muy perplejo acerca de esto, así que probé y llegar a esto:

let Ackb m n = 
    let rec rAck cont m n = 
    match (m, n) with 
     | 0, n -> cont (n+1) 
     | m, 0 -> rAck cont (m-1) 1 
     | m, n -> rAck (fun x -> rAck cont (m-1) x) m (n-1) 
    in rAck (fun x -> x) m n 
;; 

(Es OCaml/F # código).

Mi problema es que no estoy seguro de que esto sea recursivo en la cola. ¿Podrías confirmar que es? Si no, ¿por qué? Y, finalmente, ¿qué significa cuando la gente dice que la función de Ackermann no es recursiva primitiva?

Gracias!

Answer 1

Sí, es cola recursiva. Todas las funciones se pueden hacer recíprocamente mediante una transformación explícita a Continuation Passing Style.

Esto no significa que la función se ejecutará en la memoria constante: construirá pilas de continuaciones que deben asignarse. Puede ser más eficiente que defunctionalize las continuaciones para representar esos datos como un tipo de datos algebraico simple.

Ser primitive recursive es una noción muy diferente, relacionada con la expresividad de una cierta forma de definición recursiva que se utiliza en teoría matemática, pero probablemente no muy relevante para la informática como la conoce: son de expresividad muy reducida, y los sistemas con composición de funciones (comenzando con el Sistema T de Gödel), como todos los lenguajes de programación actuales, son mucho más potentes.

En términos de lenguajes de programación, las funciones recursivas primitivas corresponden aproximadamente a programas sin recursión general donde todos los ciclos/iteraciones están estáticamente acotados (se conoce el número de repeticiones posibles).

Answer 2

Sí.

Por definición, cualquier función recursiva se puede transformar en una iteración siempre que tenga acceso a una ilimitada constructo de pila,. La pregunta interesante es si se puede hacer sin una pila o cualquier otro almacenamiento de datos sin límites.

Una función recursiva de cola puede convertirse en dicha iteración solo si el tamaño de sus argumentos es limitado. En su ejemplo (y casi cualquier función recursiva que use continuaciones), el parámetro cont es para todos los medios y propósitos una pila que puede crecer a cualquier tamaño. De hecho, todo el punto de estilo de continuación y paso es almacenar datos generalmente presentes en la pila de llamadas ("¿qué hacer después de regresar?") En cambio en un parámetro de continuación.