4.1.2 Dragon Curve

Overview

The Heighway dragon curve is what you get when you fold a paper strip in half repeatedly, always in the same direction, then unfold each crease to exactly 90°. NASA physicist John Heighway first investigated it in 1966, and Martin Gardner popularised it in his Scientific American column the next year [1]. What makes it irresistible: the entire curve, no matter how complex, is encoded as a string of Ls and Rs built by one short recursive rule. Render the string with turtle graphics — move forward, turn left or right — and a self-similar dragon emerges that never crosses itself and tiles the plane.

This lesson sits at the conceptual end of Module 04. Where 4.1.1 used recursion to place pixels, 4.1.2 uses recursion to construct a sequence of instructions and only then renders it. That separation — generation rule vs. interpretation — is the same architectural move you will see again in Mandelbrot iteration (4.1.3) and L-systems (4.3.1).

Learning objectives

1. Apply the recursive rule “$D_n$ = previous sequence + $R$ + reversed-and-inverted previous sequence” to build the dragon sequence.
2. Render an L/R turn sequence on a NumPy canvas using a turtle-graphics interpreter.
3. Predict the sequence length for any depth using the formula 2 to the power (n+1), minus 1.
4. Recognise the dragon curve as a separation of generation (the recursive string) from interpretation (the turtle walk) — the same pattern that drives L-systems.

Quick start — see the dragon emerge

import numpy as np
from PIL import Image

LEFT, UP, RIGHT, DOWN = range(4)

def turn_left(d):  return (d + 3) % 4
def turn_right(d): return (d + 1) % 4

def generate_dragon_sequence(initial_turn, depth):
    if depth == 0:
        return initial_turn
    previous = generate_dragon_sequence(initial_turn, depth - 1)
    inverted = ''.join('L' if c == 'R' else 'R' for c in previous[::-1])
    return previous + 'R' + inverted

# Depth 10 → 2047 turn instructions
sequence = generate_dragon_sequence('R', 10)
print(f"Sequence length: {len(sequence)}")

Core concepts

Concept 1 — Paper-folding as recursion

Fold a paper strip in half once. Unfold it so the crease opens to 90°: one right turn. Fold it twice in the same direction, then unfold each crease to 90°: the sequence is R R L — two right turns then one left turn [2]. The number of creases doubles with every fold, and the pattern is exactly the dragon curve at that depth.

The construction rule that captures this is recursive: take the previous depth’s sequence, append a single R (the brand-new middle fold), then append the reversed and inverted previous sequence. “Inverted” means swap every L with R and vice versa — this captures the fact that, after the new fold, the second half of the paper now points in the opposite direction:

$D_0 = R$, and at depth $n$, $D_n$ is the previous depth’s sequence, then R, then the previous depth’s sequence reversed and inverted.

Concept 2 — Generating the sequence

The recursive construction translates directly to two short Python functions:

def invert_sequence(s):
    """Swap every L for R and vice versa."""
    return ''.join('L' if c == 'R' else 'R' for c in s)

def generate_dragon_sequence(initial_turn, depth):
    if depth == 0:
        return initial_turn
    previous = generate_dragon_sequence(initial_turn, depth - 1)
    second_half = invert_sequence(previous[::-1])
    return previous + 'R' + second_half

Trace the first few iterations by hand:

The bolded middle R is the brand-new fold introduced at each depth — every other character was either inherited from the previous row or is a reversed-inverted copy of it.

Concept 3 — Turtle interpretation

The sequence tells you how to turn. To actually draw anything, an imaginary “turtle” walks across the canvas:

• Forward — move one step in the current direction, drawing pixels along the way.
• L — turn 90° counter-clockwise.
• R — turn 90° clockwise.

Directions are integers 0..3 so rotation is a (d ± 1) % 4 operation. Forward motion is a slice assignment along the matching axis — canvas[y, x:x+s] for a rightward step, and so on:

def move_forward(canvas, position, step_size, direction, color):
    x, y = position
    if direction == RIGHT:
        canvas[y, x:x + step_size] = color
        return (x + step_size, y)
    elif direction == LEFT:
        canvas[y, x - step_size:x] = color
        return (x - step_size, y)
    elif direction == UP:
        canvas[y - step_size:y, x] = color
        return (x, y - step_size)
    elif direction == DOWN:
        canvas[y:y + step_size, x] = color
        return (x, y + step_size)

def draw_dragon(canvas, sequence, start, step, direction, color):
    pos = start
    for turn in sequence:
        pos = move_forward(canvas, pos, step, direction, color)
        direction = turn_right(direction) if turn == 'R' else turn_left(direction)
    move_forward(canvas, pos, step, direction, color)

Exercises

Three exercises in Execute → Modify → Create order: run the depth-10 dragon, sweep parameters, then re-implement the recursive sequence generator from scratch.

MODIFY II.

Sweep depth, colour, and direction

Edit your copy of dragon_curve.py to produce three variants. Only change the marked parameters.

Goals

1. Depth comparison. Render the same dragon at depths 4, 7, and 10 side-by-side. Keep step_size = 3 constant so you can see the silhouette converging.
2. Fire dragon. Replace the light-blue colour (100, 180, 255) with a warm orange-red such as (255, 110, 40).
3. Rotated dragon. Change start_direction from UP to RIGHT. Predict what happens, then verify.

Goal 1 — what to expect

The depth-4 dragon is a recognisable 31-segment zigzag with its silhouette barely emerging. By depth 7 the dragon shape is unmistakable; by depth 10 the boundary is dense with fine detail. None of the silhouettes drift away from a common bounding box — that is the stability of the recursive construction.

Goal 2 — what to expect

Just a recoloured curve. The dragon shape is decided entirely by the L/R sequence; colour is a render decision applied uniformly to every segment. You could also pass color as a tuple that depends on segment index to get a hue gradient along the dragon’s body.

Goal 3 — what to expect

The entire dragon rotates 90° clockwise. Starting direction is a global rotation: it applies to every segment uniformly, so the shape is preserved and only the orientation changes. You may need to re-tune start_position to keep the curve inside the canvas.

CREATE III.

Re-code the recursive generator

Implement the dragon sequence generator from scratch. The turtle/render code is provided; you fill in the recursion.

python · exercise3_starter.py Copy

def invert_sequence(sequence):
    """Swap all L's and R's."""
    # TODO 1: return a string with every L replaced by R and every R by L
    pass

def generate_dragon_sequence(initial_turn, depth):
    """Build the dragon curve sequence recursively."""
    if depth == 0:
        # TODO 2: return the base case
        pass
    # TODO 3: get the previous depth's sequence (recursive call)
    previous = None
    # TODO 4: build the second half — reverse, then invert
    second_half = None
    # TODO 5: combine: previous + 'R' (the new fold) + second_half
    return None

# Self-test
test = generate_dragon_sequence('R', 3)
assert test == 'RRLRRLLRRRLRLLL', f"Got {test!r}"
print("All good — depth 3 sequence matches the expected dragon string.")

Hint 1 — invert_sequence

return ''.join('L' if c == 'R' else 'R' for c in sequence)

A list comprehension that walks the string character by character, swapping each.

Hint 2 — base and recursive cases

• Base case — depth == 0 returns the single character initial_turn. Without this the recursion never bottoms out.
• Recursive case — call generate_dragon_sequence(initial_turn, depth - 1) to get the previous sequence, then build previous + 'R' + invert_sequence(previous[::-1]). The [::-1] reverses, invert_sequence swaps L/R, and the central 'R' is the new fold introduced at this depth.

Complete solution

python · exercise3_solution.py Copy

def invert_sequence(sequence):
    return ''.join('L' if c == 'R' else 'R' for c in sequence)

def generate_dragon_sequence(initial_turn, depth):
    if depth == 0:
        return initial_turn
    previous = generate_dragon_sequence(initial_turn, depth - 1)
    second_half = invert_sequence(previous[::-1])
    return previous + 'R' + second_half

assert generate_dragon_sequence('R', 3) == 'RRLRRLLRRRLRLLL'

Make it your own

• Twin dragons. Draw two dragons from the same start position, one facing UP and one facing DOWN, each a different colour. They interlock without overlapping — the twin-dragon tiling Knuth analysed [2].

• Animated depth sweep. Loop over depths 1..12 and save each as a frame. Pillow’s Image.save(..., save_all=True, append_images=...) writes the result as an animated GIF.

• Vector output. Replace move_forward with a Pillow ImageDraw.line() call (or SVG output) for a smooth, resolution-independent dragon you can print or laser-cut.

Downloads

Summary

Common pitfalls to avoid

• Forgetting the base case. Without if depth == 0: return initial_turn, the recursion never terminates and Python raises RecursionError.
• Reversing without inverting (or vice versa). Both operations are needed on the second half. Drop either one and the curve loses its self-similar shape and starts crossing itself.
• Off-canvas drawing. Depth 12 at step_size = 3 exceeds an 800-pixel canvas. Either reduce step_size, increase the canvas, or tune start_position.
• Confusing axis conventions. move_forward uses (x, y) but NumPy indexes canvas[y, x]. Mixing these up swaps your dragon’s orientation.

References