¿Cómo difiere la recursión primitiva de la recursividad "normal"?

Question

Actualmente estoy leyendo el The Craft of Functional Programming de Simon Thompson y cuando describo la recursión, también menciona una forma de recursión llamada Recursividad primitiva.

¿Puede explicar cómo este tipo de recursión es diferente de las funciones recursivas "normales"?

Aquí está un ejemplo de una función de recursión primitiva (en Haskell):

power2 n 
    | n == 0 = 1 
    | n > 0  = 2 * power2(n - 1) 

Answer 1

Una respuesta simplificada es que las funciones recursivas primitivas son aquellas que se definen en términos de otras funciones recursivas primitivas, y la recursión en la estructura de los números naturales. Los números naturales son conceptualmente como esto:

data Nat 
    = Zero 
    | Succ Nat -- Succ is short for 'successor of', i.e. n+1 

Esto significa que puede recursivo en ellos de esta manera:

f Zero  = ... 
f (Succ n) = ... 

Podemos escribir tu ejemplo como:

power2 Zero = Succ Zero -- (Succ 0) == 1 
power2 (Succ n) = 2 * power2 n -- this is allowed because (*) is primitive recursive as well 

Composición de funciones recursivas primitivas también es primitivo recursivo.

Otro ejemplo es los números de Fibonacci:

fib    Zero = Zero 
fib   (Succ Zero) = (Succ Zero) 
fib (Succ n@(Succ n' )) = fib n + fib n' -- addition is primitive recursive 

Answer 2

http://en.wikipedia.org/wiki/Primitive_recursive_function

Answer 3

funciones recursivas primitivos son una respuesta natural (de matemático) para el problema de la parada, al eliminar el poder de hacer auto-recursión ilimitada arbitraria.

Considérese una función de "mal"

f n 
    | n is an odd perfect number = true 
    | otherwise = f n+2 

¿Se terminan f? No puedes saber sin resolver el problema abierto de si hay números perfectos impares. Es la capacidad de crear funciones como estas lo que dificulta el problema de detención.

La recursión primitiva como construcción no le permite hacer eso; el punto es prohibir la cosa "f n + 2" sin dejar de ser lo más flexible posible - no se puede definir primitiva-recursivamente f (n) en términos de f (n + 1).

Tenga en cuenta que el hecho de que una función no sea primitiva recursiva no significa que no termina; La función de Ackermann es el ejemplo canónico.

Answer 4

las funciones recursivas que sólo pueden ser implementadas por hacer bucles son funciones recursivas primitivas.