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

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Multiple recursion with 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:
Full 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:
Sierpinski gasket 2 by 2
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:
Sierpinski gasket 4 by 4
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.
Sierpinski gasket 8 by 8
Sierpinski gasket 16 by 16
Sierpinski gasket 32 by 32
Sierpinski gasket 64 by 64
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:
Full Sierpinski gasket
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:
    1. Draw a Sierpinski gasket in the upper left square.
    2. Draw a Sierpinski gasket in the upper right square.
    3. 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.

Want to join the conversation?

  • aqualine seed style avatar for user T T
    How would this look like in code?
    (22 votes)
    Default Khan Academy avatar avatar for user
  • winston default style avatar for user Jason Brown
    Was this section a more recent addition to the chapter? The guidelines in the project appear to be for a completely different project (recursive art). I completed the Sierpinksi Gasket but one of the evaluator's guidelines is that the project should change colour at each level of recursion, which seems pointless considering that nothing gets coloured in until the base case anyway.
    (8 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Jackson Lincoln
    Would it be possible to go farther than you showed us and go as far as you would like to, or is there at least a limit to how far you can go?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Recursion typically uses "stack memory" to hold the state of the variables before each recursive call. So every time a recursive call is made, more of stack memory is used up. With enough recursive calls, you run out of stack memory, which gives you a "stack overflow error". So, if you had infinite memory you could go on for ever, but in reality, you run out of stack memory fairly quickly.
      (3 votes)
  • mr pants teal style avatar for user bhagerty
    If found the instruction "Try commenting and uncommenting some of the recursive calls to get rotated gaskets" confusing, because you don't get rotated gaskets unless you leave exactly one call commented out and three calls active. So I would rewrite this to say one of the following: "Try commenting and uncommenting some of the recursive calls (including the one that's commented out in the code) to see what happens." Or: "Try changing which one of the four recursive calls is commented out to get gaskets rotated in different orientations."
    (2 votes)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user Mason
    How would one explain this in a presentation to 8th graders?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user jacobrodri
    this is complete confusing
    (1 vote)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user abhay.shivgounda
    Hello - what is the "main" function here? I don't understand what makes interpreter call the function "draw()" - because there is no invocation, just declaration of draw().
    (1 vote)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Roughly, it's working within the "Processing" programming environment. So processing.js, which you don't see, calls the draw function.

      Note: The exact details may be slightly different. But this is, in essence, what is going on.
      (1 vote)