4.8. El triángulo de Sierpinski

Otro fractal que exhibe la propiedad de auto-similitud es el triángulo de Sierpinski. Un ejemplo se muestra en la Figura 3. El triángulo de Sierpinski ilustra un algoritmo recursivo de tres vías. El procedimiento manual para dibujar un triángulo de Sierpinski es simple. Comience con un único triángulo grande. Divida este gran triángulo en cuatro nuevos triángulos conectando el punto medio de cada lado. Ignorando el triángulo medio que usted acaba de crear, aplique el mismo procedimiento a cada uno de los tres triángulos de las esquinas. Cada vez que cree un nuevo conjunto de triángulos, aplique recursivamente este procedimiento a los tres triángulos más pequeños de las esquinas. Usted podría seguir aplicando este procedimiento indefinidamente si tuviera un lápiz suficientemente afilado. Antes de seguir leyendo, intente dibujar el triángulo Sierpinski usted mismo, usando el método descrito.

../_images/sierpinski.png

Figura 3: El triángulo de Sierpinski

Figura 3: El triángulo de Sierpinski

Puesto que podemos seguir aplicando el algoritmo indefinidamente, ¿cuál es el caso base? Veremos que el caso base se establece arbitrariamente como el número de veces que queremos dividir el triángulo en partes. A veces llamamos a este número el “grado” del fractal. Cada vez que hacemos una llamada recursiva, le restamos 1 al grado hasta llegar a 0. Cuando alcancemos un grado de 0, dejaremos de hacer llamadas recursivas. El código que generó el Triángulo de Sierpinski de la Figura 3 se muestra en el ActiveCode 1.

El programa en el ActiveCode 1 sigue las ideas descritas anteriormente. Lo primero que hace sierpinski es dibujar el triángulo exterior. A continuación, hay tres llamadas recursivas, una para cada uno de los nuevos triángulos de las esquinas que obtenemos al conectar los puntos medios. Una vez más, hacemos uso del módulo estándar turtle que viene incorporado en Python. Usted puede aprender todos los detalles de los métodos disponibles en el módulo usando el comando help('turtle') desde la consola de Python.

Mire el código y piense en el orden en que se dibujarán los triángulos. Aunque el orden exacto de las esquinas depende de cómo se especifica el conjunto inicial, supongamos que las esquinas están en el siguiente orden: izquierda, arriba, abajo y derecha. Debido a la forma en que la función sierpinski se llama a sí misma, sierpinski se dirige hacia el triángulo más pequeño permitido en la esquina inferior izquierda, y luego comienza a llenar el resto de los triángulos dirigiéndose hacia atrás. Luego llena los triángulos en la esquina superior dirigiéndose hacia el triángulo más pequeño y más alto. Finalmente, llena la esquina inferior derecha, dirigiéndose hacia el triángulo más pequeño en la parte inferior derecha.

A veces es útil pensar en un algoritmo recursivo en términos de un diagrama de las llamadas de la función. La Figura 4 muestra que las llamadas recursivas siempre se hacen avanzando hacia la izquierda. Las funciones activas se indican en negro y las llamadas de función inactivas aparecen en gris. Cuanto más lejos vaya usted hacia la parte inferior de la Figura 4, más pequeños serán los triángulos. La función termina dibujando un nivel a la vez; una vez que ella termina con la parte inferior izquierda, se mueve a la parte inferior central, y así sucesivamente.

../_images/stCallTree.png

Figura 4: Construcción del triángulo de Sierpinski

Figura 4: Construcción del triángulo de Sierpinski

La función sierpinski depende en gran medida de la función obtenerMitad, la cual toma como argumentos dos puntos extremos y devuelve el punto intermedio entre ellos. Además, el ActiveCode 1 tiene una función que dibuja un triángulo relleno usando los métodos begin_fill y end_fill.

Next Section - 4.9. Problemas recursivos complejos