La recursividad primitiva es una forma de codificar matemáticamente la idea de un cierto tipo de algoritmo. En lugar de dar definiciones, ilustraré la distinción con ejemplos que deberían ser lo suficientemente claros. En particular, daré dos algoritmos para dividir un número entero par entre 2.
Ejemplo de recursividad primitiva
Cuenta de 1 a n. Cada vez que toque un número par, agregue uno a su respuesta. Por ejemplo:
1
2 X
3
4 XX
5 5
6 XXX
- Noté que cuando tomo 2 números primos consecutivos (digamos [math] p [/ math] y [math] q [/ math]), la diferencia entre [math] pq [/ math] y [math] \ lceil \ sqrt {pq} \ \ rceil ^ 2 [/ math] siempre parece ser un cuadrado perfecto. ¿Es esto cierto? ¿Y por qué?
- ¿Qué matemáticos vivos están más cerca de resolver la hipótesis de Riemann?
- ¿Por qué las semiprimes tardan tanto tiempo en factorizarse?
- ¿Cuáles son las probabilidades de que la NSA haya descifrado el factorización de enteros en el tiempo polinómico?
- Explicaciones de Layman: ¿Por qué podemos encontrar una fórmula para resolver ecuaciones polinómicas de orden cuatro pero no de orden cinco?
Esto muestra que 6 dividido por 2 es 3.
Ejemplo de [math] \ mu [/ math] -Recursion
Verifique 1 para ver si 1 x 2 = n. Si no, marque 2 a continuación. Sigue revisando hasta que lo encuentres. Por ejemplo:
1 x 2 = 2 NO
2 x 2 = 4 NO
3 x 2 = 6 SÍ
Esto también muestra que 6 dividido por 2 es 3.
¿Por qué es importante la distinción?
(Esta sección se ha mejorado sustancialmente después de los comentarios de Jesse Tov.)
Mirando el primer algoritmo, está claro que terminará sin importar lo que agreguemos; puede tomar como máximo n pasos, después de lo cual se hará. Las funciones recursivas primitivas son buenos modelos para programas, porque modelan programas que no pueden entrar en bucles infinitos. Sería bueno si pudiéramos entender todo usándolos. Entonces, una pregunta natural sería si podríamos tomar un algoritmo como el segundo y convertirlo automáticamente en un algoritmo como el primero.
Bueno, tenga en cuenta que en este caso realmente no podemos, en particular, si ponemos un número impar en el programa, obtendremos un bucle infinito, que no podemos replicar con la función recursiva primitiva. Sin embargo, dado que nos gustaría evitar que tales cosas sucedan de todos modos, una pregunta más natural es esta: si tenemos un algoritmo como el segundo que sabemos que termina para todas las entradas , ¿podemos convertirlo en un algoritmo como el primero?
Para hacer esto preciso, definimos dos clases de funciones. (Tenga en cuenta que estas son funciones en el sentido matemático más que en el sentido de la programación informática).
- Las funciones recursivas primitivas , que es básicamente la clase de funciones que se pueden construir a partir de la suma y la recursividad primitiva.
- El total de funciones recursivas, que es básicamente la clase de funciones creadas a partir de la suma y [math] \ mu [/ math] -recursion que se definen para cada entrada posible.
¡Quizás sorprendentemente, hay funciones recursivas totales que no son funciones recursivas primitivas! Puede (es decir, debería) preguntarse por qué podría ser el caso, ya que saber que un programa termina parece implicar que conoce un límite superior de cuán grande puede ser la respuesta. Esta aparente paradoja se resuelve observando que, para utilizar la recursividad primitiva, debe poder suministrar el límite superior a través de una función recursiva primitiva. Resulta que hay funciones que crecen absurdamente rápido, tan rápido que no pertenecen a la clase de funciones recursivas primitivas. Una de esas funciones es la función de Ackermann, que, sin embargo, es una función recursiva total.