Ejercicios selectos (recursividad).
- En la entrada Recursividad (Definición y conceptos), se presenta y describe brevemente una figura geométrica generada mediante un proceso recursivo potencialmente infinito. Siguiendo lo descrito en dicha entrada, dibuje en papel la figura geométrica correspondiente de Nivel 5.
- Haga un análisis de los llamados y retornos recursivos como los realizados en la entrada "Soluciones iterativas vs. recursivas" para los llamados de función factorial(5) y factorial(6).
- Escriba un programa que, a través de una función recursiva, calcule el producto de dos números enteros positivos a y b por medio de sumas sucesivas, esto es: a * b = a + a + . . . + a, donde a se suma tantas veces como lo indique b. Para este ejercicio, asuma que b siempre será positivo, la idea de toda esta sección es poner en práctica la recursividad más que el análisis de todos los casos posibles para a y b.
- Realice en una hoja de papel el árbol de recursividad que se genera para el cálculo de fibonacci(5) y fibonacci(6) como el que se mostró en "Soluciones iterativas vs. recursivas".
- Escriba un programa que, a través de una función recursiva, calcule el cociente entero de dos números enteros positivos a y b por medio de restas sucesivas, esto es a / b ==>
- a - b = c1, si c1 >= b, entonces
- c1 - b = c2, si c2 >= b, entonces
- c2 - b = c3, si c3 >= b, entonces
- . . . donde
el cociente estará dado por el número de veces que se haya podido
repetir el procedimiento descrito.
- Escriba un programa que, a través de una función recursiva, calcule la potencia de dos números enteros positivos a y b por medio de productos sucesivos, esto es: a^b = a * a * . . . * a, donde a se multiplica tantas veces como lo indique b.
- Compare las versiones recursivas con las versiones iterativas descritas en el blog y analícelas. Simplemente por la lectura del código, ¿qué versión representa una mejor abstracción de las definiciones matemáticas? Realice diferentes ejecuciones y determine qué versión tiene un mejor rendimiento.
- Tanto el factorial como la serie de Fibonacci crecen de manera exponencial y no hay tipo de dato que las pueda contener. En el lenguaje de programación C, los tipos de datos numéricos dividen su rango tanto en números positivos como en números negativos, por lo que su capacidad de almacenamiento se ve, por decirlo de alguna manera, dividida. Sin embargo, existe el modificador unsigned (sin signo), que instruye al compilador para usar todo el rango de bits del tipo de dato para representar números positivos incluyendo el cero. Pruebe con este modificador de tipo de datos, documéntese en su funcionamiento y su especificador de formato, y amplíe la capacidad de representación para los resultados de los ejemplos estudiados en el blog.
- En base a lo indicado en el ejercicio anterior, calcule con la versión iterativa y recursiva respectivamente, fibonacci(52), ¿qué observa? ¿qué puede deducir?
- En base a lo expuesto en el blog y basándose en el Ejemplo 5.5, determine el tiempo en segundos que tarda la función de Fibonacci en determinar, por ejemplo, fibonacci(49) en sus respectivas versiones: iterativa y recursiva.
- Escriba un programa que, en base al algoritmo descrito para las Torres de Hanoi, resuelva dicho problema por medio de una función recursiva. Note que es un proceso de simple traducción al lenguaje C, ya que tanto las relaciones de recurrencia, como el criterio de paro están dados en el algoritmo.
- Basándose en el ejercicio anterior y en el Ejemplo 5.5, determine el tiempo en segundos que tarda la función que da solución al problema de las torres de Hanoi para 20, 35 y 50 discos por ejemplo.
