4.7. Visualización de la recursividad¶
En la sección anterior examinamos algunos problemas que eran fáciles de resolver mediante la recursividad; sin embargo, todavía puede ser difícil encontrar un modelo mental o una forma de visualizar lo que está sucediendo en una función recursiva. Esto puede dificultar la comprensión de la recursividad. En esta sección examinaremos un par de ejemplos de uso de la recursividad para dibujar algunas imágenes interesantes. A medida que usted observe cómo toman forma estas imágenes, obtendrá una nueva perspectiva del proceso recursivo que puede ser útil para consolidar su comprensión de la recursividad.
La herramienta que utilizaremos para nuestras ilustraciones es el módulo gráfico de Python llamado turtle (tortuga). El módulo turtle es estándar en todas las versiones de Python y es muy fácil de usar. La metáfora es bastante simple. Usted puede crear una tortuga y la tortuga puede moverse hacia delante, hacia atrás, girar a la izquierda, girar a la derecha, etc. La tortuga puede tener su cola hacia arriba o hacia abajo. Cuando la cola de la tortuga está hacia abajo y la tortuga se mueve, dibuja una línea a medida que se desplaza. Para aumentar el valor artístico de la tortuga usted puede cambiar el ancho de la cola, así como el color de la tinta en el que la cola se empapa.
Aquí daremos un ejemplo sencillo para ilustrar algunos conceptos básicos de los gráficos con el módulo turtle. Utilizaremos el módulo para dibujar una espiral recursivamente. El ActiveCode 1 muestra cómo se hace. Después de importar el módulo turtle creamos una tortuga. Cuando creamos la tortuga también creamos una ventana para que ella dibuje adentro. A continuación definimos la función dibujarEspiral. El caso base para esta función simple se da cuando la longitud de la línea que queremos dibujar, dada por el parámetro len, se reduce a cero o menos. Si la longitud de la línea es mayor que cero, indicamos a la tortuga que siga adelante por len unidades y luego gire a la derecha 90 grados. El paso recursivo ocurre cuando llamamos dibujarEspiral de nuevo con una longitud reducida. Al final del ActiveCode 1 notará que llamamos a la función miVentana.exitonclick(), este es un método práctico de la ventana que pone a la tortuga en un modo de espera hasta que usted haga clic dentro de la ventana, después de lo cual el programa la limpia y cierra.
Eso es realmente todo lo que usted necesita saber respecto a los gráficos con el módulo turtle para hacer algunos dibujos bastante impresionantes. Para nuestro próximo programa vamos a dibujar un árbol fractal. Los fractales vienen de una rama de las matemáticas, y tienen mucho en común con la recursividad. La definición de un fractal implica que, que cuando usted lo mira, el fractal tiene la misma forma básica no importa cuánto lo magnifique. Algunos ejemplos de la naturaleza son las costas de los continentes, los copos de nieve, las montañas, e incluso los árboles o arbustos. La naturaleza fractal de muchos de estos fenómenos naturales hace posible que los programadores generen paisajes muy realistas para películas generadas por computadora. En nuestro próximo ejemplo generaremos un árbol fractal.
Para entender cómo va a funcionar esto es útil pensar en cómo podríamos describir un árbol usando un vocabulario fractal. Recuerde que hemos dicho anteriormente que un fractal es algo que se ve igual en todos los diferentes niveles de ampliación. Si traducimos esto a árboles y arbustos podríamos decir que incluso una pequeña ramita tiene la misma forma y características que un árbol entero. Usando esta idea podríamos decir que un árbol es un tronco, con un árbol más pequeño que va a la derecha y otro árbol más pequeño que va a la izquierda. Si usted piensa en esta definición recursivamente, ella significa que vamos a aplicar la definición recursiva de un árbol a los dos árboles más pequeños de izquierda y derecha.
Vamos a traducir esta idea a un código en Python. El Programa 1 muestra cómo podemos utilizar nuestra tortuga para generar un árbol fractal. Veamos el código un poco más de cerca. Usted verá que en las líneas 5 y 7 estamos haciendo una llamada recursiva. En la línea 5 hacemos la llamada recursiva justo después de que la tortuga gire 20 grados a la derecha; éste es el árbol derecho mencionado anteriormente. Luego en la línea 7 la tortuga hace otra llamada recursiva, pero esta vez después de girar 40 grados a la izquierda. La razón por la que la tortuga debe girar 40 grados a la izquierda es que necesita deshacer el giro original de 20 grados a la derecha y luego hacer un giro adicional de 20 grados a la izquierda para dibujar el árbol izquierdo. Observe también que cada vez que hacemos una llamada recursiva a arbol restaremos algo del parámetro longitudRama; esto es para asegurarnos de que los árboles recursivos se hagan más y más pequeños. Usted también debe reconocer la instrucción inicial if en la línea 2 como una verificación para el caso base que consiste en que el valor de longitudRama se vuelva demasiado pequeño.
Programa 1
1def arbol(longitudRama,t):
2 if longitudRama > 5:
3 t.forward(longitudRama)
4 t.right(20)
5 arbol(longitudRama-15,t)
6 t.left(40)
7 arbol(longitudRama-10,t)
8 t.right(20)
9 t.backward(longitudRama)
El programa completo para este ejemplo de árbol se muestra en el ActiveCode 2. Antes de ejecutar el código, piense en cómo espera usted ver que el árbol irá tomando forma. Mire las llamadas recursivas y piense en cómo se desarrollará este árbol. ¿Se dibujará simétricamente con las mitades derecha e izquierda del árbol tomando forma simultáneamente? ¿Será dibujado el lado derecho primero y depués el lado izquierdo?
Observe cómo cada punto de ramificación en el árbol corresponde a una llamada recursiva, y note cómo el árbol se dibuja por la derecha hasta llegar a su rama más corta. Puede ver esto en la Figura 1. Ahora, observe cómo el programa regresa al tronco sólo después que se ha dibujado todo el lado derecho del árbol. La mitad derecha del árbol puede verse en la Figura 2. Luego se dibuja el lado izquierdo del árbol, pero no yendo tan lejos hacia la izquierda como es posible. Más bien, una vez más, todo el lado derecho del árbol izquierdo se dibuja hasta que finalmente llegamos a la ramita más pequeña de la izquierda.
Figura 1: El comienzo de un árbol fractal¶
Figura 1: El comienzo de un árbol fractal
Figura 2: La primera mitad del árbol¶
Figura 2: La primera mitad del árbol
Este sencillo programa para dibujar un árbol es sólo un punto de partida para usted; notará además que el árbol no parece particularmente realista porque la naturaleza no es tan simétrica como un programa de computadora. Los ejercicios al final del capítulo le darán algunas ideas sobre cómo explorar algunas opciones interesantes para hacer que su árbol parezca más realista.
Autoevaluación
Modifique el programa de árbol recursivo utilizando una o todas las ideas siguientes:
Modifique el grosor de las ramas para que a medida que el valor de
longitudRamase haga más pequeño, la línea se haga más delgada.Modifique el color de las ramas de modo que cuando el valor de
longitudRamase vuelva muy pequeño se coloree como una hoja.Modifique el ángulo utilizado para girar la tortuga de manera que en cada punto de ramificación el ángulo se seleccione aleatoriamente dentro de algún rango. Por ejemplo, elija el ángulo entre 15 y 45 grados. Haga ensayos para ver si luce bien.
Modifique el valor de
longitudRamarecursivamente para que en vez de restar siempre la misma cantidad, usted reste una cantidad aleatoria dentro de algún rango.