La recursividad es una técnica que expresar algo en términos de si mismo. Muy Fácil de entender, ¿cierto? Bueno, la verdad es que no. Muchas personas encuentran esto chocante o antinatural y en términos de programación esta antinaturalidad es peor si ya aprendieron a programar de manera no recursiva. Bien pues aquí van ejemplos de la vida real.
- La definición de Recursividad está aquí.
- Recursión = Recursividad. Recursividad = Recursión
Bueno, de todos modos voy a poner algunos ejemplos con Logo y con matemáticas. Más entretenidos y fáciles de entender.
Un ejemplo: Factorial
La operación factorial (se denota n! y se lee n factorial o factorial de n) lo que hace es multiplicar todos los números desde n hasta 1. La definición formal de esta función es:
- n! =
- 0! es igual a 1
- Si n>1 entonces n! = n * (n-1)!
¿Qué implica esa definición? Si queremos obtener 5! deberemos hacer lo siguiente:
- 5! =
- 5 * 4!
- 5 * 4 * 3!
- 5 * 4 * 3 * 2!
- 5 * 4 * 3 * 2 * 1!
- 5 * 4 * 3 * 2 * 1 * 0!
- 5 * 4 * 3 * 2 * 1 * 1
- 120
Sí, lo se. Se ve aburrido, largo y tedioso, pero como para eso están las computadoras no debemos preocuparnos por ello.
Anatomía de una función recursiva
Una función recursiva en general se divide en casos. Según sea su propósito puede basarse en el principio de “divide y venceras”. Las dos partes que componen una función de este tipo son las siguientes.
- Expresión recursiva de la función:
- Lo que hace es expresar la función de modo más simple en términos de si misma. Por ejemplo, en el caso del factorial el problema se convierte en uno más sencillo: en lugar de obtener 5! se obtiene 5 * 4!, 4! es más sencillo que 5!.
- Condición de parada:
- Este es el caso más simple de todos y es el que sabemos resolver. Por supuesto, puede ser que podamos agregar código para otros un poco más complejos, pero al colocar código solamente para el caso más simple crearemos mejores programas, más fáciles de leer, mantener, etc.
- La condición de parada no debe ser necesariamente una sola, eso depende de lo que uno quiere hacer.
¿Porqué usarla?
Este punto es en su mayor parte cuestión de gustos. Las funciones recursivas ofrecen una solución elegante a los problemas. Además hay lenguajes de programación donde esta es la manera natural de programar (por ejemplo Scheme). En Logo no es la manera natural de programar, pero de todos modos hay que conocerla.
Implementación en Logo
Para implementar un algoritmo de esta manera en Logo se hace igual a como se haría cualquier otro. A modo de ejemplo voy a implementar el código de factorial.
Para ejecutar este código simplemente llamamos a factorial n, con n el valor que queremos (sea una variable, un número entero, etc).
Porqué no usar la recursión
Las computadoras, o más exactamente los programas que corren en ellas, usan una pila para guardar las direcciones de retorno de los procedimientos. Por ejemplo, si llamamos a factorial 5 la pila contendrá (entre otras cosas) lo siguiente:
En este ejemplo la pila es la sublista debajo de cada elemento.
- factorial 5
- dirección de inicio del programa
- factorial 4
- dirección de retorno a factorial 5
- dirección de inicio del programa
- factorial 3
- dirección de retorno a factorial 4
- dirección de retorno a factorial 5
- dirección de inicio del programa
- factorial 2
- dirección de retorno a factorial 3
- dirección de retorno a factorial 4
- dirección de retorno a factorial 5
- dirección de inicio del programa
- factorial 1
- dirección de retorno a factorial 2
- dirección de retorno a factorial 3
- dirección de retorno a factorial 4
- dirección de retorno a factorial 5
- dirección de inicio del programa
- factorial 0
- dirección de retorno a factorial 1
- dirección de retorno a factorial 2
- dirección de retorno a factorial 3
- dirección de retorno a factorial 4
- dirección de retorno a factorial 5
- dirección de inicio del programa
- en factorial 0 salto a donde indica el tope de la pila
dirección de retorno a factorial 1- dirección de retorno a factorial 2
- dirección de retorno a factorial 3
- dirección de retorno a factorial 4
- dirección de retorno a factorial 5
- dirección de inicio del programa
- en factorial 1 salto a donde indica el tope de la pila
dirección de retorno a factorial 2- dirección de retorno a factorial 3
- dirección de retorno a factorial 4
- dirección de retorno a factorial 5
- dirección de inicio del programa
- en factorial 2 salto a donde indica el tope de la pila
dirección de retorno a factorial 3- dirección de retorno a factorial 4
- dirección de retorno a factorial 5
- dirección de inicio del programa
- ……
Como se pudo ver, el uso de la pila del programa es intensivo. Mientras que hay lenguajes como Scheme que optimizan la ejecución del código para poder hacer funciones recursivas, Logo no obliga a las implementaciones a hacer estas optimizaciones. Esto provoca lo que se conoce como “stack overflow”: la pila se desborda y esto provoca una salida abrupta del programa. De hecho este es el error número 2 de la lista de errores de FMSLogo.
Además un procedimiento recursivo puede ser más lento que su contraparte iterativa (debido a los accesos al STACK, no se optimiza tan bien, etc).
Así que la decisión sobre si hay que usar o no recursividad debe considerar la facilidad de implementación, rendimiento y otras razones (como por ejemplo, que el profesor le haya dicho: DEBE HACERLO DE MANERA RECURSIVA). Definitivamente en las prácticas o tareas de procedimientos recursivos se espera que se use recursividad, je je.
Más ejemplos
Otros ejemplos de procedimientos recursivos son los siguientes:
- Suma de todos los números enteros desde 0 hasta n.
- NOTA: Este es un ejercicio curioso, pero si se quiere obtener esa suma es más sencillo y eficiente notar que es igual a n(n+1)/2.
- Números de Fibonacci:
- Fib de 0 es 0
- Fib de 1 es 1
- Fib de n, n>1 es Fib(n-1) + Fib(n-2)
- Máximo común divisor:
- Esta manera de implementarlo no es el método tradicional enseñado en la escuela, así que es probable que pocos lo conozcan. Sin embargo es utilísimo, en especial con números gigantes, donde la factorización de un número no se puede obtener con certeza.
- El algoritmo de Euclides para el MCD(a, b) es el siguiente:
- Si b es 0 entonces MCD(a, b) es a
- MCD(a, b) = MCD(b, residuo (a, b))
- residuo(a,b) es el residuo de dividir a entre b
A modo de práctica, intenten implementarlos de manera recursiva y de manera iterativa (usando ciclos). También pueden comparar el tiempo que tardan en ejecutarse usando la instrucción timemilli. Muchas veces la implementación iterativa consiste en usar ciclos para evitar las llamadas al mismo procedimiento.