Recursão múltipla com o triângulo de Sierpinski

Até agora, os exemplos de recursividade que vimos exigiam que você fizesse uma chamada recursiva por vez. Mas às vezes você precisa fazer múltiplas chamadas recursivas. Aqui está um bom exemplo, uma construção matemática que é um fractal conhecido como Triângulo de Sierpinski:

Como você pode ver, ele é uma coleção de pequenos quadrados desenhados em um padrão específico dentro de uma região quadrada. É assim que o desenhamos. Comece com a região quadrada inteira, e divida-a em quatro partes, assim:

Tome os três quadrados marcados com um sinal de × — o do canto superior esquerdo, o do canto superior direito e o do canto inferior direito — e divida-os em quatro partes, do mesmo modo:

Continue fazendo isso. Divida todos os quadrados marcados com um sinal de × em quatro partes, e coloque um sinal de × nos quadrados dos cantos superior esquerdo e direito e inferior direito, mas nunca no canto inferior esquerdo.

Quando os quadrados ficarem pequenos o bastante, pare de dividir. Se você preencher todos os quadrados marcados com × e deixar os desmarcados de lado, obterá um Triângulo de Sierpinski. Aqui está ele de novo:

Para resumir, é assim que desenhamos um Triângulo de Spierpinski em um quadrado:

Observe que você precisa fazer não apenas uma, mas três chamadas recursivas. É por isso que escolhemos o desenho de um Triângulo de Sierpinski para mostrar a recursão múltipla.

Você pode escolher quaisquer três dos quatro triângulos nos quais desenhou recursivamente triângulos de Sierpinski. O resultado simplesmente será girado por um múltiplo de 90 graus a partir do desenho acima. (Se você desenhar recursivamente triângulos de Sierpinski em qualquer outro número de quadrados, não obterá um resultado interessante).

O programa abaixo desenha um triângulo de Sierpinski. Tente comentar e remover os comentários de algumas de suas chamadas recursivas para obter triângulos rotacionados.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.