Hola a todos!
Les comparto unas notas sobre recursión, donde se explica de manera muy breve qué es la recursión y se centra más en ejemplos y ejercicios al respecto. El ejercicio consiste en definir una función recursiva que realice la suma de los primos entre 1 y un número n natural dada. Para esto, también habrá que definir una función que determine si un número es primo y para ello también podemos usar recursión y aplicar la función auxiliar que ayuda a determinar si un número es primo para todos sus anteriores.
Por ejemplo, para saber si 6 es primo, necesitamos ver si es divisible entre 5. Como esto es falso, ahora comprobamos contra 4. También es falso. Pero al comprobar contra 3, es cierto que 6 es divisible por 3. Por lo tanto 6 no es primo (ya que tiene un divisor distinto de la unidad y de sí mismo). Pero si hacemos el mismo procedimiento con 7, llegaríamos a 2 notando que nadie entre 6 y 2 divide a 7. Por lo tanto 7 es primo. La función que determina si 7 o cualquier otro número es primo, realizaría este procedimiento de forma recursiva; es decir, llamándose a sí misma, hasta encontrar un divisor del número, o llegar a 2.
Luego, el ejercicio solicita crear una versión iterativa de estas soluciones recursivas, utilizando algún ciclo en lugar de llamadas a la misma función.
No quisiera publicar la respuesta al problema junto con las notas, preferiría que si alguien se quiere tomar la molestia, lo haga en los comentarios en alguna forma.
Enlace al texto: http://www.nachintoch.mx/teaching/intro_data_structure/25_feb-Benchmarks%20y%20recursi%C3%B3n.pdf
Un comentario adicional
Yo sé que estas notas de alguna manera invocan a lo que alguna vez fuera la publicación más visitada y con mayor discusión en los comentarios en este blog: «Un simple algoritmo para calcular números primos» (hasta que se me ocurrió cambiar el nombre de dominio ¬¬). Las amplias discuciones y dudas respecto al porqué algo «tan simple» cómo determinar si el número 1’744,263 es primo, daban para mucho material sobre complejidad computacional. Y sí, llevo ya varios meses trabajando en una entrada larga y exhaustiva donde explico qué es la complejidad computacional, porqué el inocente problema de encontrar primos no es trivial, qué es el No-Determinismo y cómo es que todos nuestros sistemas criptográficos (nuestras contraseñas de sesión, facebook, email, contraseñas del IEEE 802.11 (WiFi), etc), dependen del hecho de que encontrar número primos grandes es computacionalmente muy costoso y si un día alguien logra resolver el problema con un algoritmo verdaderamente simple, se nos acaba la seguridad informática como la conocemos, y esa persona se haría acreedora a un premio de 1 millón de dólares (es en serio).
Pero desgraciadamente, por falta de tiempo y la mala costumbre de dormir varias horas de vez en cuando, no la he podido terminar aunque ya va bastante avanzada dicha entrada. Sus comentarios y aportaciones son muy valiosas y estímulos para retomarla más seguido.
En fin, espero estas «simples» notas, les sean de utilidad 😛
Saludos!
Nachintoch 