Recursie multiplă cu triunghiul lui Sierpinski

Până acum, exemplele de recursivitate pe care le-am analizat au avut un singur apel de fiecare dată. Dar, uneori, trebuie să includem mai multe apeluri recursive. Iată un exemplu bun: un fractal (desen matematic) numit modelul lui Sierpinski.

Observăm că este o colecție de pătrățele desenate după un anumit model într-o regiune pătrată. Iată cum îl desenăm: începem cu tot pătratu și îl împărțim în patru secțiuni:

Luăm cele trei pătrate marcate cu un x -stânga sus, dreapta sus și dreapta jos - și împărțim pe fiecare în patru secțiuni, în același mod:

Continuăm. Împărțim fiecare pătrat marcat cu x în patru secțiuni, apoi le marcăm cu câte un x pe cel din stânga sus, dreapta sus și dreapta jos, dar niciodată pe cel din stânga jos.

Atunci când pătratele devin suficient de mici, ne oprim. Colorăm numai pătratele care conțin un x, iar pe celelalte le lăsăm necolorate. Astfel, ajungem la modelul lui Sierpinski. Iată-l:

Să recapitulăm! Pașii pentru a desena modelul Sierpinski într-un pătrat sunt:

Observăm că aici apar trei apeluri recursive, nu doar unul singur. Am ales modelul Sierpinski pentru a evidenția recursivitatea multiplă.

Putem alege oricare trei din patru pătrate pentru care să desenăm recursiv modelul Sierpinski. Rezultatul este asemănător, dar rotit cu un unghi multiplu de 90 de grade față de desenul de mai sus. (Dacă am desena recursiv modelul Sierpinski pentru un alt număr de pătrate, rezultatul nu ar fi așa interesant).

programul de mai jos desenează un model Sierpinski. Încearcă să incluzi în comentarii sau să scoți din comentariu unele apeluri recursive pentru a obține modele rotite:

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.