Wielokrotna rekurencja na przykładzie Trójkąta Sierpińskiego

Jak dotąd przedstawione tu przykłady rekurencji, wymagały od ciebie tylko jednego wywołania rekurencyjnego za każdym razem. Ale czasem trzeba wykonać wiele wywołań rekurencyjnych. Oto dobry przykład: matematyczna konstrukcja, będąca fraktalem, zwana Trójkątem Sierpińskiego:

Jak widać, jest to kolekcja małych kwadratów narysowanych według szczególnego wzoru na kwadratowym obszarze. Oto jak ją narysować. Zacznijmy od dużego kwadratu, stanowiącego cały obszar, i podzielmy go na cztery równe obszary jak poniżej:

Weźmy teraz pod uwagę trzy kwadraty zaznaczone × czyli — górny z lewej strony, górny z prawej strony i dolny z prawej strony — i podzielmy je na cztery obszary w taki sam sposób jak powyżej:

Powtarzaj te same operacje. Dziel każdy kwadrat oznaczony × na cztery obszary i umieszczaj × w kwadratach: górnym lewym, górnym prawym i dolnym prawym, ale nigdy nie w dolnym lewym.

Gdy kwadraty są już wystarczająco małe, przestań je dzielić. Wypełnij teraz kolorem każdy kwadrat zawierający ×, ale pomiń pozostałe kwadraty. W ten sposób dostajesz Trójkąt Sierpińskiego. Oto on jeszcze raz:

Podsumowując, oto jak narysować trójkąt Sierpińskiego w kwadracie:

Zauważ, że potrzebujesz wykonać tu nie tylko jedno, ale trzy odwołania rekurencyjne. Dlatego właśnie rozważaliśmy rysowanie trójkąta Sierpińskiego jako przykład wielokrotnego wywołania rekurencyjnego.

Możesz wybrać jakikolwiek trzy z czterech kwadratów, w których rekurencyjnie narysujesz trójkąt Sierpińskiego. Rezultatem będzie po prostu rysunek odwrócony o jakąś wielokrotność 90 stopni w stosunku do podawanego tu przykładu. (Jeśli narysujesz trójkąt Sierpińskiego z jakąkolwiek inną liczbą kwadratów, nie dostaniesz interesującego wyniku).

Poniższyprogram rysuje dywan Sierpińskiego. Spróbuj skomentować lub usunąć komentarz z niektórych rekurencyjnych odwołań, aby otrzymać obrócone trójkąty:

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.