If you're seeing this message, it means we're having trouble loading external resources on our website.

Dacă sunteţi în spatele unui filtru de web, vă rugăm să vă asiguraţi că domeniile *. kastatic.org şi *. kasandbox.org sunt deblocate.

Conţinutul principal

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.
Modelul Sierpinski complet
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:
Modelul Sierpinski 2 pe 2
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:
Modelul Sierpinski 4 pe 4
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.
Modelul Sierpinski 8 pe 8
Modelul Sierpinski 16 pe 16
Modelul Sierpinski 32 pe 32
Modelul Sierpinski 64 pe 64
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:
Modelul Sierpinski complet
Să recapitulăm! Pașii pentru a desena modelul Sierpinski într-un pătrat sunt:
  • Determinăm cât de mic este pătratul. Dacă este suficient de mic pentru a fi caz elementar, atunci îl colorăm. Dar trebuie să stabilim clar ce înseamnă "suficient de mic".
  • Dacă este mai mare, atunci împărțim în cele patru pătrate: stânga sus, dreapta sus, dreapta jos și stânga jos. "Rezolvăm" recursiv trei subprobleme:
    1. Desenăm modelul Sierpinski în pătratul stânga sus.
    2. Desenăm modelul Sierpinski în pătratul dreapta sus.
    3. Desenăm modelul Sierpinski în pătratul dreapta jos.
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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.