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:
  • Sprawdź, jak mały jest ten kwadrat. Jeśli jest dostatecznie mały, aby stać się przypadkiem bazowym, wypełnij kwadrat. Musisz zdecydować, co to znaczy "dostatecznie mały".
  • Jeśli nie jest dostatecznie mały, podziel kwadrat na cztery mniejsze kwadraty: górny lewy, górny prawy, dolny lewy i dolny prawy kwadrat. Użyj rekurencji, aby "rozwiązać" trzy podproblemy:
    1. Narysuj dywan Sierpińskiego w lewym górnym kwadracie.
    2. Narysuj dywan Sierpińskiego w prawym górnym kwadracie.
    3. Narysuj dywan Sierpińskiego w prawym dolnym 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.
Ładowanie