Conţinutul principal
Biblioteca de informatică
Curs: Biblioteca de informatică > Unitatea 1
Lecția 6: Recursivitate- Recursivitatea
- Funcția factorial
- Provocare: factorialul iterativ
- Factorialul recursiv
- Provocare: factorial recursiv
- Proprietățile algoritmilor recursivi
- Folosirea recursivității pentru a determina dacă un cuvânt este sau nu palindrom
- Provocare: este un șir palindrom?
- Provocare: puteri recursive
- Recursie multiplă cu triunghiul lui Sierpinski
- Îmbunătățirea eficienței funcțiilor recursive
- Proiect: artă recursivă
© 2023 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie
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:
- 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:
- Desenăm modelul Sierpinski în pătratul stânga sus.
- Desenăm modelul Sierpinski în pătratul dreapta sus.
- 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ă a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.
Vrei să te alături conversației?
Nici o postare încă.