By Richard White, based on a lesson by Dom Rosato
The "Dragon Curve" is a shape formed by turning lines that can be described and drawn recursively. (See the Wikipedia entry at https://en.wikipedia.org/wiki/Dragon_curve for a more detailed explanation on the various types of related curves.) In this activity we'll be
turtle module to draw a Dragon
curveBegin by taking a strip of paper a few centimeters wide and holding it vertically in the air. This paper has no folds, no "turns" in it, and has an order of 0.
Take the strip of paper and fold the top half down to the right. Once the paper is unfolded so that the fold makes a 90-degree angle, we can see that this "order 1" dragon curve has 1 fold, to the right.
Fold the strip of paper again in half, and down to the right. Once it is opened up to create 90-degree angles again, we see that the order 2 dragon curve has three turns: one to the right, another to the right, and then one to the left.
What happens with the order 3 curve?
If you take a look at the successive fold patterns that we produced using the piece of paper, we should be able to identify the Right and Left turns for each of the given "orders" of curve.
For the zeroeth order of the dragon curve, there is a single piece of paper with no folds. Thus, the pattern is "", ie. there are no left or right turns.
For the first order dragon curve, we fold down and to the right. Hold the paper slightly open so that the fold is at a 90 degree angle, off to the right. If we follow along the edge of the paper from the bottom, when held with the folds at 90 degrees to each others there is one right turn in the paper. Thus, the pattern for the first order curve is "R" (for "right").
For the second order curve, consulting our folded paper and/or the diagram above, following up from the bottom of the paper we can see that there's a Right turn, another Right turn, and then a Left turn: "RRL."
What do you see for the third order curve? "RRLRRLL"
And if you manage to get one more fold into the piece of paper, by tracing the paper up you'll find the turns are "RRLRRLLRRRLLRLL"
There is!
One way to consider the pattern of the folds is to count how many total folds/turns there are in each order.
Order 0 = no folds
Order 1 = one fold (R)
Order 2 = three folds (RRL)
Order 3 = seven folds (RRLRRLL)
Order 4 = fifteen folds (RRLRRLLRRRLLRLL)What is the pattern in the numbers?
1 --> 3 --> 7 --> 15 --> ?
More importantly, let's look at the patterns in the directions of the folds. In particular, let's identify the middle character in each sequence of folds with parentheses.
Order 1 (R)
Order 2 R(R)L
Order 3 RRL(R)RLL
Order 4 RRLRRLL(R)RRLLRLLCan you see how the first part of each sequence of folds is related to the last part of the sequence of folds?
It may not be immediately obvious. Here it is.
The second part can be determined by taking the first part, reversing it, and substituting L for R, and R for L.
Take a moment to confirm for yourself that this is true.
There's a second pattern that's critical for us to understand. How is the first part of any RL-string related to the string of the order before it?
Take a look at Order 4, for example. The first part of Order 4 is
RRLRRLL, which is... the string from Order 3!
This insight is what leads us to considering a recursive solution: the first part of Order(n) is just the result from Order(n - 1), and so on, all the way down the line.
So how do we get the string for curve(n)?
curve(n) will be the result of
curve(n - 1)RR and L letters interchanged.Time to start coding!
We'd like to be able to create a string of R and L characters that will describe a dragon curve as described above. And we've determined that recursion will be part of it. Consider the base case first.
def curve(n):
if n = 0:
return "" # there are no turns
else:
result = ""
# figure out first, middle, and last parts, and use recursion
return resultOkay, let's do the easy parts first.
def curve(n):
if n = 0:
return "" # there are no turns
else:
result = ""
first_part = curve(n - 1) # recursive call!
middle = "R"
last_part = ... # first part reversed and letter-switched
result = first_part + middle + last_part
return resultThat's not too bad. We just have to figure out how to get the last part calculated.
Let's write a tester to see if we're getting the correct results.
/usr/bin/env python3
"""dragon_curve.py
"""
def curve(n):
if n = 0:
return "" # there are no turns
else:
result = ""
first_part = curve(n - 1) # recursive call!
middle = "R"
last_part = ""
first_part_reversed = first_part[::-1]
for letter in first_part_reversed
if letter == "R":
last_part += "L"
else:
last_part += "R"
result = first_part + middle + last_part
return result
def main():
print(curve(0), "Expected: \"\"")
print(curve(1), "Expected: R")
print(curve(2), "Expected: RRL")
print(curve(3), "Expected: RRLRRLL")
main()turtle to draw a Dragon curveThe last step in this exercise is to actually draw a dragon curve.
Python turtle module can be imported to draw a Dragon curve
as shown below.
def draw(turns,length):
win = turtle.Screen()
t = turtle.Turtle()
t.speed(0) # go as fast as possible
t.left(90) # orient turtle towards top of screen
# Now go through the turns and follow their directions
for turn in turns:
t.forward(length - 4)
if turn == "L":
t.left(45)
t.forward(4**0.5)
t.left(45)
else:
t.right(45)
t.forward(4**0.5)
t.right(45)
win.exitonclick() # keeps the window from closing when program is doneYou can also use Processing:
/**
DragonCurve.java
A recursive function that draws a Dragon Curve in
Processing.
@author Richard White
@version 2026-03-10
*/
// instance variables
int WIDTH = 1000;
int HEIGHT = 800;
int x = (int) WIDTH / 2;
int y = (int) HEIGHT / 2;
int direction = 0; // "North". Could also be 1, 2, or 3
int len = 3;
int order = 13;
void setup()
{
size(1000, 800);
background(255);
}
/**
* curve is a recursive function to produce the letter sequence
* for folding
*/
String curve(int n)
{
// n is the order of the curve
if (n == 0)
return "";
else
{
String firstPart = curve(n - 1);
String middle = "R";
// compose the lastPart
String lastPart = "";
for (int i = firstPart.length() - 1; i >= 0; i--)
{
if (firstPart.substring(i, i+1).equals("L"))
lastPart += "R";
else
lastPart += "L";
}
return firstPart + middle + lastPart;
}
}
void draw()
{
direction = 0; // "North". Could also be 1, 2, or 3
// Get the R-L string sequence for the given order
String pattern = curve(order);
println(pattern);
// draw pattern as lines in Processing
int startX = x;
int startY = y;
y -= len; // negative is upwards!
line(startX, startY, x, y); // Order 0 line
for (int i = 0; i < pattern.length(); i++)
{
// Save x and y as starting points for next line segment
startX = x;
startY = y;
// Get the next turn direction
String turn = pattern.substring(i, i+1);
if (turn.equals("L")) { direction = (direction - 1 + 4) % 4; }
else { direction = (direction + 1) % 4; }
// Modify x,y coordinates depending on which direction we turned
if (direction == 0) { y -= len; }
else if (direction == 1) { x += len; }
else if (direction == 2) { y += len; }
else { x -= len; }
// Draw the line resulting from the turn
line(startX, startY, x, y);
}
noLoop();
}