Acerca de este experimento
Un árbol es un tronco con dos árboles más pequeños encima. Esa sola frase es un programa completo: una función que dibuja una rama y luego se llama a sí misma dos veces. La recursión transforma reglas breves en imágenes complejas. Observa cómo se construyen, llamada a llamada, un árbol, un triángulo de Sierpinski y un copo de nieve de Koch; sigue cómo la pila de llamadas crece y se reduce, y cuenta lo rápido que se dispara el número de llamadas al aumentar la profundidad.
Objetivos de aprendizaje
- Identificar el caso base y el caso recursivo de una función recursiva
- Seguir el orden en que se ejecutan y retornan las llamadas recursivas
- Explica qué contiene la pila de llamadas y por qué es importante su profundidad
- Calcula el número de llamadas para una profundidad determinada, como 2^(n+1) − 1 en un árbol binario
- Describe la autosimilitud y calcula una dimensión fractal sencilla
Cómo usarlo
- 1Elige el árbol de profundidad 3 y observa las llamadas paso a paso. ¿Qué rama se dibuja primero: la izquierda o la derecha? ¿Por qué?
- 2Haz una pausa cuando la pila alcance su máxima profundidad. ¿Qué representa cada marco de la pila? ¿Cuántos marcos hay en relación con la profundidad?
- 3Completa una tabla de profundidad y llamadas para el árbol. Encuentra la regla y compruébala con una profundidad de 10.
- 4Cambia el ángulo de las ramas y la proporción de longitud. ¿Qué ajustes hacen que las ramas se solapen?
- 5Cambia al triángulo de Sierpinski. ¿Dónde está el caso base en el código? ¿Cuántos triángulos se dibujan con una profundidad de 5?
- 6Construye el copo de nieve de Koch con una profundidad de 5. Usa los valores mostrados para explicar cómo el perímetro puede seguir creciendo mientras el área permanece limitada.
El modelo
Supuestos
- Las llamadas se ejecutan de una en una, en el orden del programa y en profundidad, exactamente como se ejecutan en un lenguaje de programación ordinario.
- El pseudocódigo pasa las posiciones y las direcciones como parámetros, así que no es necesario restaurar el estado de la tortuga cuando una llamada retorna.
- La dimensión fractal del árbol, log 2 / log(1/r), solo describe las puntas cuando las ramas no se superponen.
- Se limitan las profundidades máximas para que la reproducción paso a paso siga siendo rápida: 12 para el árbol, 7 para el triángulo y 6 para el copo de nieve.
Pruébalo en clase
- Q1¿Qué pasaría si la función del árbol no tuviera un caso base?
- Q2¿Cuántas llamadas hace la función de Sierpinski con profundidad 4? Explica tu respuesta con una suma.
- Q3¿Por qué la pila de llamadas nunca alcanza una profundidad mayor que la profundidad de recursión más uno, aunque se realicen miles de llamadas?
- Q4Escribe una función recursiva que calcule n! e identifica su caso base.
- Q5La costa de Gran Bretaña parece más larga cuanto más corta es la regla con la que se mide. ¿Cómo explica esto el copo de nieve de Koch?
Preguntas frecuentes
¿La recursión es más lenta que un bucle?
Cada llamada consume algo de tiempo y memoria para su marco de pila, por lo que un bucle suele ser ligeramente más rápido. Sin embargo, para estructuras ramificadas como árboles, carpetas anidadas o el análisis sintáctico, la recursión es mucho más sencilla de escribir, y cualquier recursión puede reescribirse usando una pila explícita propia.
¿Qué es un desbordamiento de pila?
Cada llamada que aún no ha terminado mantiene un marco en la pila de llamadas. Si la recursión alcanza demasiada profundidad, por ejemplo, porque nunca se llega al caso base, la pila se queda sin memoria y el programa se bloquea con un error de desbordamiento de pila.
¿Dónde se encuentran los fractales en la naturaleza?
Los helechos, el brócoli romanesco, las redes fluviales, los rayos, los vasos sanguíneos y las ramificaciones de las vías respiratorias de los pulmones son aproximadamente autosimilares a varias escalas; por eso se utilizan reglas recursivas para generarlos en gráficos por ordenador.