Existen dos funciones clásicas y claves que se resuelven con recursividad:
- La función que calcula el factorial de un número entero positivo.
- La función que calcula los términos de la serie de Fibonacci.
Específicamente para estas dos funciones, el enfoque de la recursividad no es la manera más eficiente de resolverlas, pero ayudan significativamente a ilustrar el concepto de recursividad.
Por otro lado, dichas funciones son tan clásicas que, para no incurrir en algún tipo de maldición del estilo del programa “Hola mundo!”, se revisarán necesaria y rápidamente, primero en su versión iterativa (ciclos) y posteriormente en su versión recursiva.
Por otro lado, dichas funciones son tan clásicas que, para no incurrir en algún tipo de maldición del estilo del programa “Hola mundo!”, se revisarán necesaria y rápidamente, primero en su versión iterativa (ciclos) y posteriormente en su versión recursiva.
Factorial (Versión iterativa).
El factorial de n denotado por n! (n >= 0) se obtiene en base a lo definido en la siguiente expresión:
n! = n * (n-1) * (n-2) * . . . * 1
de tal forma que, si n = 5 se tiene:
5! = 5 * 4 * 3 * 2 * 1 = 120
De lo anterior puede observarse que la solución está dada por un ciclo. El Ejemplo 5.1 muestra la función que calcula de manera iterativa el factorial de un número. Note que la función asume que n >= 0.
En base a todos los ejemplos anteriores todas las sentencias del Ejemplo 5.1 deberían ser completamente entendidas. Asegúrese de que así sea antes de continuar.
En base a todos los ejemplos anteriores todas las sentencias del Ejemplo 5.1 deberían ser completamente entendidas. Asegúrese de que así sea antes de continuar.
Factorial (Versión recursiva).
Matemáticamente, la función factorial se define según lo expresado en la siguiente ecuación, para n >= 0.
La función del Ejemplo 5.2 es esencialmente una traducción al lenguaje C de la ecuación anterior, donde a las líneas 25 y 26 se les conoce como criterio de paro o caso base de la recursividad, mientras que la línea 28 contiene el paso recursivo.
Es importante hacer notar que en cada llamado recursivo se tiene una simplificación del problema original, lo que asegura que eventualmente se llegue al caso base de la recursividad, siempre que n >= 0.
Las siguientes figuras ilustra el funcionamiento de la función factorial (líneas 24-29) del Ejemplo 5.2 para n = 4:
Es importante hacer notar que en cada llamado recursivo se tiene una simplificación del problema original, lo que asegura que eventualmente se llegue al caso base de la recursividad, siempre que n >= 0.
Las siguientes figuras ilustra el funcionamiento de la función factorial (líneas 24-29) del Ejemplo 5.2 para n = 4:
 |
| (a) Llamados recursivos para el factorial del número cuatro. |
 |
| (b) Retornos recursivos para el factorial del número cuatro. |
En la figura (a) se muestran los llamados recursivos, note cómo en cada nivel de n existen valores pendientes de ser calculados debido precisamente al funcionamiento de la recursividad. Cuando finalmente se alcanza el caso base (n = 0), es posible determinar los valores que fueron quedando pendientes (las flechas de la figura (b) muestran dicho procedimiento), y calcular los resultados de n para cada nivel, los cuales son mostrados encerrados en círculos en la figura (b). Analice y estudie lo anterior hasta comprenderlo, ya que en buena medida, de ello depende la comprensión del Ejemplo 5.2.
Es preciso mencionar que una vez que se tiene la relación de recurrencia (una relación de recurrencia es una ecuación que relaciona a los términos de una sucesión con alguno de sus predecesores) que establece tanto el criterio de paro como el (los) paso(s) recursivo(s), el proceso de traducción al lenguaje C es muy sencillo, por lo que la deducción de dicha relación de recurrencia es en realidad la parte difícil en el diseño de funciones recursivas. Para el caso de la función factorial, la relación de recurrencia está dada por la definición matemática de la expresión que la define.
Es preciso mencionar que una vez que se tiene la relación de recurrencia (una relación de recurrencia es una ecuación que relaciona a los términos de una sucesión con alguno de sus predecesores) que establece tanto el criterio de paro como el (los) paso(s) recursivo(s), el proceso de traducción al lenguaje C es muy sencillo, por lo que la deducción de dicha relación de recurrencia es en realidad la parte difícil en el diseño de funciones recursivas. Para el caso de la función factorial, la relación de recurrencia está dada por la definición matemática de la expresión que la define.
Por último, note que se ha utilizado el tipo de dato long debido a que el factorial de un número crece de manera exponencial. La salida de los Ejemplos 5.1 y 5.2 para n = 4 se muestra en la siguiente figura:
 |
| Salida de los Ejemplos 5.1 y 5.2 para n = 4. |
Fibonacci (Versión iterativa).
Otra función matemática clásica y clave es la función que genera la serie o sucesión de Fibonacci. La serie de Fibonacci, es la siguiente sucesión infinita de números:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
Observe que, con excepción de los dos primeros términos, cada término de la serie se obtiene como la suma de los dos términos anteriores:
- fib(0) = 0
- fib(1) = 1
- fib(2) = 1
- fib(3) = 2
- fib(4) = 3
- fib(5) = 5
- fib(6) = 8
- fib(7) = 13
- fib(8) = 21
- fib(9) = 34
- fib(10) = 55
- fib(11) = 89
- . . .
De los elementos de la serie mostrados, es posible deducir que la solución puede obtenerse también mediante un ciclo.
El Ejemplo 5.3 muestra la función que calcula de manera iterativa el número de Fibonacci para un término de la serie. Observe que la función asume que n >= 0.
Asegúrese de entender el programa del Ejemplo 5.3 antes de continuar, particularmente la función fibonacci. Note que, al igual que antes, se ha utilizado el tipo de dato long.
El Ejemplo 5.3 muestra la función que calcula de manera iterativa el número de Fibonacci para un término de la serie. Observe que la función asume que n >= 0.
Asegúrese de entender el programa del Ejemplo 5.3 antes de continuar, particularmente la función fibonacci. Note que, al igual que antes, se ha utilizado el tipo de dato long.
Fibonacci (Versión recursiva).
Ahora bien, matemáticamente, la función de Fibonacci que genera los términos de la sucesión de Fibonacci se define en base a lo expresado en la siguiente ecuación para n >= 0:
Note que la función fibonacci del Ejemplo 5.4 es una traducción al lenguaje C de la ecuación anterior. Observe también que las líneas 25 y 26 implementan el criterio de paro o caso base de la recursividad, mientras que la línea 28 contiene los dos pasos recursivos involucrados en el cálculo de los términos de la serie.
Para n >= 2 cada término de la serie se calcula como la suma de dos llamados recursivos, por lo que la función fibonacci del Ejemplo 5.4 genera un árbol de recursividad como el que se muestra en la siguiente figura para n = 4:
Para n >= 2 cada término de la serie se calcula como la suma de dos llamados recursivos, por lo que la función fibonacci del Ejemplo 5.4 genera un árbol de recursividad como el que se muestra en la siguiente figura para n = 4:
 |
| Árbol de recursividad de la serie de Fibonacci para n =4. |
Observe que el término fibonacci(2) se repite en la rama derecha y en la rama izquierda del árbol. Dicha repetición de cálculos aunada al overhead implicado en cada llamado de función, hace que las implementaciones recursivas sean en general ineficientes respecto del tiempo y del espacio en memoria.
Lo anterior debe reafirmar en la mente del lector que las implementaciones recursivas de las funciones factorial y fibonacci son ineficientes, y por consiguiente, un mal enfoque de solución; sin embargo, ambas funciones ilustran de manera extraordinaria el concepto de recursividad. Por otro lado, basta con ver las definiciones matemáticas y compararlas con sus correspondientes versiones escritas en lenguaje C para darse cuenta de la elegancia, la correspondencia directa, y la simplicidad inherente a las implementaciones recursivas.
La salida de los Ejemplos 5.3 y 5.4 para n = 4 se muestra en la siguiente figura:
Lo anterior debe reafirmar en la mente del lector que las implementaciones recursivas de las funciones factorial y fibonacci son ineficientes, y por consiguiente, un mal enfoque de solución; sin embargo, ambas funciones ilustran de manera extraordinaria el concepto de recursividad. Por otro lado, basta con ver las definiciones matemáticas y compararlas con sus correspondientes versiones escritas en lenguaje C para darse cuenta de la elegancia, la correspondencia directa, y la simplicidad inherente a las implementaciones recursivas.
La salida de los Ejemplos 5.3 y 5.4 para n = 4 se muestra en la siguiente figura:
 |
| Salida de los Ejemplos 5.3 y 5.4 para n = 4. |
Investigación empírica.
El Ejemplo 5.5 muestra un esqueleto de programa para medir el tiempo en segundos de un proceso largo: una función que tarde más de un segundo en terminar.
La línea 6 incluye la biblioteca de funciones time.h necesaria para usar las funciones time (líneas 11 y 13) y difftime (línea 16).
La función time y el tipo time_t se han descrito brevemente con aterioridad en el Ejemplo 3.16, basta ahora con recordar que sirven para leer la fecha y hora del sistema en donde se ejecuta el programa. Por otro lado, la función difftime calcula la diferencia en segundos que existe entre las variables comienzo y final (líneas 9, 11 y 13).
La línea 12 representa el proceso al que se desea tomar el tiempo de ejecución en segundos. El Ejemplo 5.5 también sugiere que se incluya ahí el llamado a la función recursiva de la serie de Fibonacci con un argumento de 46 por proponer un determinado valor. Resultaría sumamente interesante probar éste y otros valores.
El Ejemplo 5.5 como tal y por sí mismo no ejecuta ni determina nada. De hecho si lo ejecuta tal cual visualizará siempre una salida de cero segundos. Sin embargo, dicho ejemplo resultará de mucha utilidad para poder medir, de manera empírica el tiempo en segundos que le toma a una función recursiva por ejemplo, terminar sus cálculos. Aunque para los seres humanos un segundo es poco, para una computadora un segundo es muchísimo tiempo, ya que en un segundo se procesan millones de micro instrucciones en el procesador, sin embargo esta forma de medir el tiempo en segundos para algunos de procesos (como las funciones recursivas), nos proporcionarán una idea más asequible del esfuerzo requerido por parte de algunas funciones.
La línea 6 incluye la biblioteca de funciones time.h necesaria para usar las funciones time (líneas 11 y 13) y difftime (línea 16).
La función time y el tipo time_t se han descrito brevemente con aterioridad en el Ejemplo 3.16, basta ahora con recordar que sirven para leer la fecha y hora del sistema en donde se ejecuta el programa. Por otro lado, la función difftime calcula la diferencia en segundos que existe entre las variables comienzo y final (líneas 9, 11 y 13).
La línea 12 representa el proceso al que se desea tomar el tiempo de ejecución en segundos. El Ejemplo 5.5 también sugiere que se incluya ahí el llamado a la función recursiva de la serie de Fibonacci con un argumento de 46 por proponer un determinado valor. Resultaría sumamente interesante probar éste y otros valores.
El Ejemplo 5.5 como tal y por sí mismo no ejecuta ni determina nada. De hecho si lo ejecuta tal cual visualizará siempre una salida de cero segundos. Sin embargo, dicho ejemplo resultará de mucha utilidad para poder medir, de manera empírica el tiempo en segundos que le toma a una función recursiva por ejemplo, terminar sus cálculos. Aunque para los seres humanos un segundo es poco, para una computadora un segundo es muchísimo tiempo, ya que en un segundo se procesan millones de micro instrucciones en el procesador, sin embargo esta forma de medir el tiempo en segundos para algunos de procesos (como las funciones recursivas), nos proporcionarán una idea más asequible del esfuerzo requerido por parte de algunas funciones.
Como versión alternativa del Ejemplo 5.5, se muestra también el Ejemplo 5.5.1 que mide el tiempo en milisegundos y por consiguiente, de una manera un poco más precisa que el primero. Tome en cuenta que aunque para el ser humano promedio un segundo es prácticamente nada, para una computadora es mucho tiempo, ya que en ese segundo ésta es capaz de realizar decenas de millones de microinstrucciones, por lo que este último ejemplo proporcionará una medición un poco más precisa respecto al tiempo que consume una función. Al ser ambos ejemplos esencialmente iguales, se dejan los detalles de este último ejemplo como ejercicio de investigación para el lector.
