Recursion
Recursion is the method of defining a function in terms of itself. If a function calls itself within the function itself, the function is called a recursive function.
The concept of Recursion was first introduced in the LOGO chapter and Math Applications chapter.
This page draws several interesting shapes using the turtle module and recursion. One of these shapes is fractals.
Before we explain what fractals are, let us define what self-similarity is.
What is Self-similarity
Self-similarity in shapes occurs when shapes are similar to each other at all scales (magnification). A shape is considered to be self-similar if a zoomed-in portion of a small part of the shape looks similar (not identical) to the whole shape of which the small portion is part of. Also, if you zoom-out the whole shape, it will be similar (not identical) to every small portion of the shape. This property is called self-similarity.
Self-similarity occurs in nature such as leaves, branches of trees, snowflakes, spirals of pinecones, broccoli, etc.
What are Fractals?
A fractal is a geometric shape in which each part of that shape is approximately a reduced-size copy of the whole shape. Every part of the fractal, regardless of how zoomed-in (magnified using a magnifying glass), or zoomed-out, looks very similar to the whole image, meaning that every part of the Fractal pattern appears similar at all levels of magnification. Putting it another way, fractals are patterns that are self-similar across different scales (magnifications).
Fractals Are Self-similar Patterns
Fractals consist of self-similar versions of themselves at smaller scales, which themselves consist of smaller self-similar versions of themselves, and so on.
The fractal algorithm starts at a desired dimension and uses recursion to reduce the dimension by a desired factor at each step of the recursion loop.
The first recursion step is denoted by depth = 1. The second recursion step corresponds to depth = 2, and so on. We can continue the recursion to any depth we desire (forever if we like). Typically, most programmers will stop at depth = 3 or 4.
To summarize, a fractal is a never-ending pattern, which is based on a recurring pattern that repeats itself indefinitely at progressively smaller scales.
Fractals are created by repeating a function over and over in an ongoing feedback loop using recursion. We introduced the concept of recursion on the LOGO Recursion page and Math Applications page.
Find out more about fractals at the links below:
<a href=”https://fractalfoundation.org/“>
<a href=”http://en.wikipedia.org/wiki/Fractal“>
In this chapter, we will make interesting fractals using recursion. We will develop programs for the following two fractals:
- Koch Patterns
- Sierpiński’s Triangle
Koch Curve
One of the earliest fractal curves was described by the Swedish mathematician Niels Fabian Helge von Koch in the year 1904. This fractal curve is named Koch curve after his name. The Koch curves allow numerous variations. Many artists have used Koch Curves to create interesting shapes and art.
More information on Koch Curves is at the link below.
<a href=”https://fractalfoundation.org/resources/fractivities/koch-curve/“>
Koch Snowflake
The Koch Snowflake is an example of a figure that is self-similar, meaning it looks the same on any scale (magnification).
The simplest way to explain how to draw a snowflake is to start with a straight line. Let us use a line of length 300 pixels.
Step 1:
The first step is to divide the line into three equal parts, each of length 100 pixels (see step 0). Using the middle segment as a base, we draw an equilateral triangle, whose side is 100 pixels as shown in step 1). Then, the base of the triangle is removed, leaving us with the first iteration of the Koch Curve. See step 1 (cont.) This image corresponds to what is called depth = 1. Now there are four straight lines, each of length 100 pixels.
Step 2:
Step 2 repeats the same operation on each of the four lines by dividing them into three equal segments and drawing an equilateral triangle on the middle segment of each of the four lines, and removing the base of each of the four triangles. This is shown Koch pattern in step 2 (depth = 2). We can do the same operation on the shape and come up with a Koch pattern of depth = 3. This can be continued indefinitely to get more complex Koch patterns.
How to Draw Koch Snowflake by Hand
The process described in Step 1 and step 2 can be continued indefinitely to get smaller and smaller lines.
Start with an Equilateral Triangle
If instead of a straight line, we start with an equilateral triangle and do the same operation described above to each of the three sides of the equilateral triangle, we get the Koch curve of depth = 1. The operation can be continued on each of the resulting lines to get more complex Koch patterns.
So, let us start with an equilateral triangle. First, we divide each side of the triangle into three equal parts. In the middle part, we form an equilateral triangle that juts out from the original triangle at 60 degrees. This new triangle has sides that are one-third the size of the triangle side we started with. Then, we remove the base of this new small triangle. Thus, the original side of the triangle has been replaced by four smaller lengths each being one-third the size of the original side length.
Cuntinuing the Process…..
We do the same process to the other two sides of the triangle we started with. This operation produces a Koch curve of depth = 1. Since each side of the original triangle has been replaced by four smaller lengths, we have 12 sides in the Koch curve of depth = 1. If we repeat the same process on each of the 12 lines, we will get a Koch curve of depth = 2. This process can be continued indefinitely to get ever more complex Koch curves.
The Koch Curve Program Using Recursion
The program below uses Python turtle module functions to draw a Koch fractal curve. The program uses the recursive function to loop through the code.
The code executes the operation on the lines described above. The lines get divided into three equal segments in each iteration of the recursive loop. Each segment’s length is one-third the length of the previous iteration of the loop.
PROGRAM EXAMPLE: KOCH CURVE SNOWFLAKE
Program Name: turtle_recursion_snowflake_final.py
###### KOCH CURVE PROGRAM EXAMPLE ######
###### DRAW KOCH SNOWFLAKE ######
import turtle
screen = turtle.Screen() # Create the screen.
screen.setup(480, 480) # Set Window size.
###### TURTLE SHAPE, SPEED, PEN SIZE, COLOR ######
TTL = turtle.Turtle()
TTL.speed(10) #Set the turtle's speed. 1 is slow, 10 is fast; 0 is fastest.
TTL.color("red") #Set the turtle's color.
TTL.pensize(2) #Set width of turtle drawing pen.
TTL.shape("turtle")
###### SET TURTLE STARTING POSITION ######
TTL.penup() # Do not let the turtle draw while moving to position (-160, 110).
TTL.setposition(-170,110)
TTL.pendown() # Enable the turtle to draw.
###### VARIABLES ######
# Variable 'length' is the length of side of starting equilateral triangle.
# Variable 'length' is divided by variable 'lengthDivisor' at each recursion iteration.
# Variable 'recursionLevel' is the depth of the Koch Curve.
###### KochFractal FUNCTION DEFINITION ######
# Draw a Koch fractal of 'recursionLevel' and
# 'length'. #1
def KochFractal(TTL, recursionLevel, length, lengthDivisor):
if recursionLevel == 0: # recursionLevel = 0 is fractal base case.
TTL.forward(length) # This will draw an equilateral triangle.
else:
length = length / lengthDivisor
# Call 'KochFractal' function inside the function itself - Recursion.
# Draw Koch pattern of one-third 'length' and decrement 'recursionLevel'.
KochFractal(TTL, recursionLevel-1, length, lengthDivisor)
TTL.left(60) #Turn turtle left by 60 degrees.
KochFractal(TTL, recursionLevel-1, length, lengthDivisor)
TTL.right(120) #Turn turtle right by 120 degrees.
KochFractal(TTL, recursionLevel-1, length, lengthDivisor)
TTL.left(60) #Turn turtle left by 60 degrees.
KochFractal(TTL, recursionLevel-1, length, lengthDivisor)
###### INITIALIZE KOCH FRACTAL recursionLevel AND length ######
# Initialize variable 'length', the length of side of equvilateral triangle.
length = 360
# Equvilateral triangle length = 360 pixels. #2
###### CALL KochFractal FUNCTION ######
# KochFractal function draws Koch fractal for one side of the triangle.
# Call KochFractal function for the first side of the triangle.
KochFractal(TTL, 3, length, 3) #3
TTL.right(120) #Turn turtle right by 120 degrees.
# Call KochFractal function for the second side of the triangle.
KochFractal(TTL, 3, length, 3) #4
TTL.right(120) #Turn turtle right by 120 degrees.
# Call KochFractal function for the third side of the triangle.
KochFractal(TTL, 3, length, 3) #5
screen.exitonclick() # Exit
The following program’s output.
Detailed Line-by-line Explanation of the Program:
1) def KochFractal(TTL, recursionLevel, length, lengthDivisor):
Step 1) defines a function called KochFractal() with parameters turtle name = TTL, recursion level, length of the side of the triangle, and lengthDivisor (division factor at each iteration of recursive loop,.)
2) length = 360
Step 2) initializes the variable ‘”ength”, which is the length of the side of an equilateral triangle. The variable “length” is initialized to 360 pixels
3) KochFractal(TTL, 3, length, 3)
TTL.right(120) #Turn the turtle right by 120 degrees.
Step 3) calls the function KochFractal for the first side of the triangle with arguments recursionLevel = 3, lengthDivisor = 3. “length “is defined to be 360 in step 2). It then turns the turtle right by 120 degrees.
4) KochFractal(TTL, 3, length, 3)
TTL.right(120) #Turn turtle right by 120 degrees.
Step 4) calls the function KochFractal for the second side of the triangle. Then turns the turtle right by 120 degrees.
5) KochFractal(TTL, 3, length, 3)
Step 5) calls the KochFractal function for the third side of the triangle.
Recursion Fractal Tree
The previous section used the Python turtle module to draw Koch Snowflake using recursive technique. In this section, we will use the turtle module and recursion to draw a tree. Notice the self-similarity in each branch of the tree.
The example below uses a program flow that is very similar to the Koch Snowflake program.
PROGRAM EXAMPLE: TURTLE RECURSION TREE FRACTAL
Program Name: turtle_recursion_tree_final.py
Credits: Adapted from
https://towardsdatascience.com/creating-fractals-with-python-d2b663786da6
###### RECURSION EXAMPLE TO DRAW A TREE ######
# Credits: Modified from https://towardsdatascience.com/creating-fractals-with-python-d2b663786da6
#
import turtle
screen = turtle.Screen() # Create the screen.
screen.setup(320, 320) # Set Window size.
###### TURTLE SHAPE, SPEED, PEN SIZE, COLOR ######
TTL = turtle.Turtle()
TTL.speed(0) #Set the turtle's speed. 1 is slow, 10 is fast; 0 is fastest.
TTL.color("brown") #Set the turtle's color.
TTL.pensize(1) #Set width of turtle drawing pen.
###### SET TURTLE STARTING POSITION ######
TTL.penup() # Do not let the turtle draw while moving to position (0, 110).
TTL.setposition(0, -100)
TTL.pendown() # Enable the turtle to draw.
TTL.hideturtle()
TTL.setheading(90)
###### VARIABLES ######
# Variable 'branchLength' is the starting length of tree brach.
# Variable 'branchReduction' subtracts from 'branchLength' in
# each recursion iteration.
# Variable 'recursionLevel' is the recursion iteration number.
###### DEFINE treeFractal FUNCTION ######
# Draw a fractal with recursion level, tree branch length,
# branch length reduction for each iteration, and
# the angle by which the branch turns each iteration.
def treeFractal(TTL, recursionLevel, branchLength, branchReduction, angle):
if recursionLevel == 0:
TTL.fd(0)
else:
branchLength = branchLength - branchReduction
TTL.forward(branchLength)
TTL.left(angle)
treeFractal(TTL, recursionLevel-1, branchLength, branchReduction, angle)
TTL.right(angle * 2)
treeFractal(TTL, recursionLevel-1, branchLength, branchReduction, angle)
TTL.left(angle)
TTL.backward(branchLength)
# Call treeFractal function with the following parameters.
# Recursion Level = 7; Branch length = 50.
# Branch reduction each recursion iteration = 5.
# Turn left of right angle by 25 degrees.
treeFractal(TTL, 7, 45, 5, 25)
screen.exitonclick() # Exit screen
The following is the program output.
Sierpiński Triangle Using Recursion
The Sierpiński triangle is a self-similar fractal. It consists of an equilateral triangle from which smaller equilateral triangles (self-similar triangles) are removed recursively at each recursion loop. This process can be continued indefinitely with ever-decreasing smaller triangles removed from the previous recursion step’s larger triangles.
The Sierpiński triangle fractal was first introduced in 1915 by Wacław Sierpiński. See Enrichment: Fractal at the end of this chapter for Sierpiński’s contributions to fractals.
Sierpiński Triangle Algorithm
The algorithm to draw Sierpiński triangle is the following:
- Start with an equilateral triangle.
- Locate the mid-point of the three sides of the triangle.
- Connect the three midpoints. This will result in a smaller equilateral triangle in the middle that looks inverted as compared to the original triangle. Now, we have four triangles – one in the middle and three at each of the vertices of the triangle we started with.
- Remove the middle triangle.
- Next, repeat the same step for each of the three triangles at the vertices of the original triangle
- We can continue this process indefinitely to get ever-decreasing smaller-sized triangles.
The following program is based on the above algorithm.
Credits: Adapted from:
PROGRAM EXAMPLE: SIERPINSKI TRIANGLE FRACTAL
Program name: turtle_recursion_Sierpinski_final.py
# Sierpinski Triangle
import turtle
screen = turtle.Screen() # Create the screen.
screen.setup(320, 320) # Set Window size.
###### TURTLE SHAPE, SPEED, PEN SIZE, COLOR ######
TTL = turtle.Turtle()
TTL.speed(1) #Set the turtle's speed. 1 is slow, 10 is fast; 0 is fastest.
TTL.color("red") #Set the turtle's color.
TTL.pensize(1) #Set width of turtle drawing pen.
###### SET TURTLE STARTING POSITION ######
TTL.penup() # Do not let the turtle draw while moving to position (0, 110).
TTL.setposition(-100, -100)
TTL.pendown() # Enable the turtle to draw.
###### VARIABLES ######
# Variable 'length' is the starting length of Sierpinski triangle.
# Variable 'angle' is the turn angle of the turtle.
# Variable 'recursionLevel' is the recursion iteration number.
###### DEFINE SierpinskiTriangle FUNCTION ######
# Draw a fractal with triangle length, recursion level, and
# the angle by which the turtle turns.
def SierpinskiTriangle(TTL, length, recursionLevel, angle):
if recursionLevel == 1: # Draw triangle.
for i in range(3):
TTL.fd(length)
TTL.left(120)
else:
SierpinskiTriangle(TTL, length/2, recursionLevel-1, angle)
TTL.fd(length/2)
SierpinskiTriangle(TTL, length/2, recursionLevel-1, angle)
TTL.bk(length/2)
TTL.left(angle)
TTL.fd(length/2)
TTL.right(angle)
SierpinskiTriangle(TTL, length/2, recursionLevel-1, angle)
TTL.left(angle)
TTL.bk(length/2)
TTL.right(angle)
# Call SierpinskiTriangle function with triangle length = 200,
# recursion levels = 2, and turtle turn angle = 60 degrees.
SierpinskiTriangle(TTL, 200,3, 60)
screen.exitonclick() # Exit screen
The following is the program output.
