Recursión doble

En la teoría de funciones recursivas , la doble recursión es una extensión de la recursión primitiva que permite la definición de funciones recursivas no primitivas, como la función de Ackermann .

Raphael M. Robinson denominó funciones de dos variables numéricas naturales G ( n , x ) doblemente recursivas con respecto a funciones dadas , si 

• G (0, x ) es una función dada de x .  
• G ( n  +  1,  0) se obtiene por sustitución de la función G ( n ,  ·) y funciones dadas.
• G ( n  +  1, x + 1) se obtiene por sustitución de G ( n + 1, x ), la función G ( n , ·) y funciones dadas. ^{[ 1 ]}       

Robinson procede a proporcionar una función recursiva doble específica (definida originalmente por Rózsa Péter ).

• G (0, x ) = x + 1   
• G ( n  +  1,  0) = G ( n ,  1)
• G ( n  +  1, x + 1) = G ( n , G ( n + 1, x ))       

donde las funciones dadas son recursivas primitivas, pero G no lo es. De hecho, esta es precisamente la función ahora conocida como la función de Ackermann .

• Recursión primitiva
• función de Ackermann