Hovedinnhold
Kurs: (Informatikk > Enhet 1
Leksjon 6: Rekursive algoritmer- Rekursjon
- Fraktal funksjoner
- Utfordring: Iterative fakultet
- Rekursiv fakultet
- Utfordring: Rekursiv fakultet
- Egenskaper for rekursive algoritmer
- Å bruke rekursjon for å avgjøre om et ord er en palindrome (er ord som er det samme forlengs og baklengs)
- Utfordringen: er en linje en palindrome?
- Generere potensen av et tall
- Utfordring: Rekursive potenser
- The Sierpinski gasket
- Prosjekt: Rekursiv kunst
© 2024 Khan AcademyBrukervilkårPersonvernVarsel om informasjonskapsler
The Sierpinski gasket
So far, the examples of recursion that we've seen require you to make one recursive call each time. But sometimes you need to make multiple recursive calls. Here's a good example, a mathematical construct that is a fractal known as a Sierpinski gasket:
As you can see, it's a collection of little squares drawn in a particular pattern within a square region. Here's how to draw it. Start with the full square region, and divide it into four sections like so:
Take the three squares with an × through them—the top left, top right, and bottom right—and divide them into four sections in the same way:
Keep going. Divide every square with an × into four sections, and place an × in the top left, top right, and bottom right squares, but never the bottom left.
Once the squares get small enough, stop dividing. If you fill in each square with an × and forget about all the other squares, you get the Sierpinski gasket. Here it is once again:
To summarize, here is how to draw a Sierpinski gasket in a square:
- Determine how small the square is. If it's small enough to be a base case, then just fill in the square. You get to pick how small "small enough" is.
- Otherwise, divide the square into upper left, upper right, lower right, and lower left squares. Recursively "solve" three subproblems:
- Draw a Sierpinski gasket in the upper left square.
- Draw a Sierpinski gasket in the upper right square.
- Draw a Sierpinski gasket in the lower right square.
Notice that you need to make not just one but three recursive calls. That is why we consider drawing a Sierpinski gasket to exhibit multiple recursion.
You can choose any three of the four squares in which you recursively draw Sierpinski gaskets. The result will just come out rotated by some multiple of 90 degrees from the drawing above. (If you recursively draw Sierpinski gaskets in any other number of the squares, you don't get an interesting result.)
The program below draws a Sierpinski gasket. Try commenting and uncommenting some of the recursive calls to get rotated gaskets:
This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.
Ønsker du å delta i samtalen?
Ingen innlegg enda.