Recursion and fractals (advanced)

Here you will learn

• what recursion is
• how recursion can be used to draw fractals

Recursion in programming means functions that call themselves. With this technique, we can draw exciting geometric patterns, so-called fractals.

An important detail when functions call themselves is that there is a stop condition. Otherwise, the function would call itself indefinitely.

A different star

Earlier in the course, we drew a five-pointed star. Now that we have learned both repetitions and functions, we can simplify the code.

def star(side):
    for i in range(5):
        forward(side)
        right(144)

star(250)
      

Now we will turn the function star into a recursive function that calls itself. In each point, a new smaller star will be drawn, and in the smaller stars, a small star will in turn be in each point. And so on to a depth we specify.

To be able to write a stop condition, we will use if n == 0: return which means "if n is equal to 0, exit the function". In each recursive step, n will decrease by one. Therefore, the function will stop calling itself when n is equal to 0. You can read more about the if statement here.

Study the example below carefully. Try to understand exactly what is happening. Recursion is not easy to understand at first!

def star(side, n):
    if n == 0:
        return
    for i in range(5):
        forward(side)
        star(side/3, n-1)
        right(144)

star(150, 3)
      

In the example above, the line star(side/3, n-1) is the important part. It means that a new star is drawn with a side one-third as large and with a depth that is one lower. With star(150, 3), the side is initially 150 and the depth is 3. After a side is drawn, star(50, 2) will be called, that is, draw a star with side 50 and depth 2. In the next step, the depth is 1 and then a simple star is drawn. At depth 0, nothing is drawn anymore because of the stop condition.

Koch's snowflake

Koch's snowflake is one of the first described fractals and was created by the Swedish mathematician Helge von Koch in 1904. Now we will see how we can draw it with the help of recursion. The algorithm below describes how the snowflake is drawn.

1. Start with a straight line.
2. Divide the line into three equal parts.
3. Replace the middle part with two parts that form a peak upwards.
4. Repeat for all lines.

# Click on test to see the illustration.

  

To draw the fractal, we can start by drawing the basic pattern in a function. Then we can replace each line with a recursive call.

def snowflake(side):
    forward(side)
    left(60) #the angle is 60 degrees in an equilateral triangle
    forward(side)
    right(120)
    forward(side)
    left(60)
    forward(side)
  

Now we will replace forward(side) with snowflake(side/3,n-1). Instead of drawing a line, we make a new pattern where the line would have been. The new pattern is only one-third as large. The stop condition when n = 1 is simply to draw the line. This is the base case as you can see in step 1 of the algorithm.

def snowflake(side,n):
    if n == 1: #stop condition
        forward(side)
        return

    snowflake(side/3,n-1) #instead of forward(100)
    left(60)
    snowflake(side/3,n-1) #instead of forward(100)
    right(120)
    snowflake(side/3,n-1) #instead of forward(100)
    left(60) 
    snowflake(side/3,n-1) #instead of forward(100)