Recursion With Sierpinski’s TriangleJake ShamsBlockedUnblockFollowFollowingMay 3Recursion is a programming technique that involves creating functions that recall themselves.
Most problems that can be solved with looping can also be solved with recursion.
A popular demonstration of recursion is Sierpinski’s Triangle.
This image below shows a fifth order Sierpinski’s Triangle.
With recursion we know that there must be a base case.
Generally this occurs when n == 0 or n == 1.
In this example a first order Sierpinski’s Triangle is simply just a single triangle.
We can create a function to draw a triangle for us called draw_triangle.
The only parameter we’ll need is the length of each side which we will call length.
We will be using python’s built in turtle module to help up with this.
Turtle has a bunch of cool methods to draw with but we’ll only be using a few of the basic ones.
import turtle # imports turtlepen = turtle.
Turtle() #creates an instance of turtle called penpen.
fd() # pen will move forwardspen.
bk() # pen will move backwardspen.
lt(angle) # turns left default 90pen.
rt(angle) # turns right default 90pen.
pu() # pen uppen.
pd() # pen downpen.
setheading(angle).
# sets the direction (180 is left)pen.
speed(n) # sets the draw speed, (1–10)Turtle is a super cool and fun module that I strongly recommend you take a look at if you haven’t already.
24.
1.
turtle – Turtle graphics – Python 3.
3.
7 documentationThe procedural interface provides functions which are derived from the methods of the classes and .
They have the same…docs.
python.
orgWith our newfound knowledge of turtle we can now write our first draw triangle function.
def draw_triangle(length): pen.
setheading(180) # set the direction of the pen to left for i in range(3): # draw 3 sides pen.
rt(120) # rotate the pen 120 degrees clockwise pen.
fd(length) # draw side # pen will end facing left (180)When we run this function it should produce an equilateral triangle.
Great!.We’ve built our first turtle function.
Now let’s get to the task at hand, solving Sierpinski’s Triangle with recursion.
In order to master recursion we must first find out how to think recursively.
Before we begin to write our function let’s plan how we’d execute it.
At this point you could be confident that you know the solution after looking at the images and you’re ready to build your function.
You may also be looking at the big picture with no clue how to approach the problem.
The process we’re about to use is one that I use in all my programming and one that can be applied to all iterative or recursive problems.
Sierpinski’s Triangle should be able to work for any non-negative integer, so let’s begin with an order 1 triangle.
We’ve already created a draw_triangle function and that will serve as our base case!.Our draw_triangle function is simple.
It takes in a one parameter, length and creates an equilateral triangle with sides length size.
Next let’s find a way to use our draw_triangle function to draw three triangles.
This might get a bit tricky when we have to find out where to start and end our pen.
To fix this we’re going to plan the order.
We’ll first draw the bottom left triangle, then the top, then the bottom right.
def sierpinski_order_two(length): draw_triangle(length) # draw triangle ONE pen.
rt(120) # angle towards peak pen.
fd(length) # move towards peak draw_triangle(length) # draw triangle TWO pen.
lt(120) # angle towards right base of ONE pen.
fd(length) # move towards right base of ONE draw_triangle(length) # draw triangle THREE pen.
fd(length) # move to startWhen we look at the code we draw triangle ONE, then we move to the peak of triangle ONE and draw triangle TWO, next we move to the right base of triangle ONE and draw triangle THREE, then we move back to the left base of triangle one to ensure we end in the same place we started.
Our output should looks something like this:Great!.Now that we’ve done order two we should pretty much be able to apply what we’ve done to anything greater!.But before we move on let’s turn our order_two function to a recursive function that can only handle values 1 or 2.
To do this we have to identify our base case which is n = 1, which is also our draw_triangle function.
What we can also identify when we look at order two is that every time we call draw_triangle, we’re calling our base case which is also 2 -1 so instead we can just call the same function on n — 1.
Let’s modify our previous function a bit.
The new code could look something like this.
def sierpinski_order_two_recursive(n, length): if n == 1: draw_triangle(length) else: # this is just like calling draw_triangle() sierpinski_order_two_recursive(n — 1, length) pen.
rt(120) pen.
fd(length) sierpinski_order_two_recursive(n -1, length) pen.
lt(120) pen.
fd(length) sierpinski_order_two_recursive(n — 1, length) pen.
fd(length)And when we run it with 2 we should get something like this:What about 1?Sweet it’s working!.Hmm… maybe it’ll even work for 3.
It looks good, like it could pass as nice artwork, but something doesn’t seem quite right.
The triangle is drawing over itself.
This brings us to our last step which can sometimes take the longest, debugging.
The start and ending positions are right but if you run the code and watch closely you might notice that the pen moves along the edge at the end only the length of the input, but on the 3rd order it has to move twice as much as it did from 1 to 2.
So maybe the value of the movement’s in between triangles has to be (n — 1) * length.
Let’s modify our code and test it for n = 3.
def sierpinksi_order_three_recursive(n, length): if n == 1: draw_triangle(length) else: sierpinksi_order_three_recursive(n — 1, length) pen.
rt(120) pen.
fd(length * (n — 1)) sierpinksi_order_three_recursive(n -1, length) pen.
lt(120) pen.
fd(length * (n — 1)) sierpinksi_order_three_recursive(n — 1, length) pen.
fd(length * (n — 1))And to test it:It works for 3.
How about 4?.Have we solved the mystery yet?Not quite, but we’re getting really close.
If we go back to the original image we can examine the length of each side based on the order and try to find a pattern.
Order 1: length = 1Order 2: length = 2Order 3: length = 4Order 4: length = 8Based on this pattern we can see that n gets bigger exponentially, doubling every time.
We can compose a function that looks like this to get f(n).
f(n) = 2^(n-1).
But we also have to keep in mind that when we move, we have to move the side length of n — 1.
So we have to change our function to 2^(n-2).
Let’s implement this, try it out, and pray that it will be the last modification we have to make.
def sierpinski_order_n_recursive(n , length): if n == 1: draw_triangle(length) else: sierpinski_order_n_recursive(n — 1, length) pen.
rt(120) pen.
fd(length * 2 ** (n — 2)) sierpinski_order_n_recursive(n -1, length) pen.
lt(120) pen.
fd(length * 2 ** (n — 2)) sierpinski_order_n_recursive(n — 1, length) pen.
fd(length * 2 ** (n — 2))Here’s our code, lets test it with order 4:It works!.Hooray!.It works for 5 too!Woo!.We’ve solved Sierpinski’s Triangle.
Now we can show our friends the cool artwork we can create with python.
Here’s an order 8 triangle.
SOOO PRETTY!.. More details