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:
Triângulo de Sierpinski completo
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:
Triângulo de Sierpinski 2 por 2
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:
Triângulo de Sierpinski 4 por 4
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.
Triângulo de Sierpinski 8 por 8
Triângulo de Sierpinski 16 por 16
Triângulo de Sierpinski 32 por 32
Triângulo de Sierpinski 64 por 64
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:
Triângulo de Sierpinski completo
Para resumir, é assim que desenhamos um Triângulo de Spierpinski em um quadrado:
  • Determine quão pequeno um quadrado é. Se for pequeno o suficiente para ser um caso base, então então simplesmente preencha o quadrado. Você tem que descobrir quão pequeno é "pequeno o suficiente".
  • Caso contrário, divida o quadrado em um quadrado superior a direita, um quadrado superior a esquerda, um quadrado inferior a direita e um quadrado inferior a esquerda. Recursivamente "resolva" três subproblemas: 1. Desenhe um triângulo de Sierpinski no quadrado superior esquerdo. 2. Desenhe um triângulo de Sierpinski no quadrado superior a direita. 3. Desenhe um triângulo de Sierpinski no quadrado inferior a direita. Você precisa fazer não uma, mas três chamadas recursivas. Esse é o porque consideramos desenhar um triângulo de Sierpinski para mostrar as múltiplas recusões.
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 em relação ao desenho acima. (Se você desenhar recursivamente triângulos de Sierpinski em qualquer outro número de quadrados, não obterá um resultado interessante). Tente adicionar e remover comentários 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.
Carregando