Case Study: Fractals — Infinite Complexity from Simple Recursion

The Big Idea

A fractal is a geometric shape that looks the same (or similar) at every scale. Zoom in on part of a fractal, and you see the same pattern repeated — smaller, but structurally identical. This self-similarity is recursion made visible. Every fractal can be generated by a recursive algorithm: apply a simple rule, then apply the same rule to the result, then apply the same rule to that result, and so on.

Fractals aren't just mathematical curiosities. They appear everywhere in nature — coastlines, tree branches, blood vessels, snowflakes, mountain ranges, broccoli. They're used in computer graphics, antenna design, data compression, and even music composition.

In this case study, you'll implement two classic fractals — the Koch snowflake and the Sierpinski triangle — using Python's turtle graphics module. Both are built from the same recursive principle: take a shape, break it into smaller copies of itself, and repeat.

The Koch Snowflake

The Rule

The Koch curve starts with a straight line segment and applies one rule recursively:

1. Divide the line into three equal parts.
2. Replace the middle third with two sides of an equilateral triangle (pointing outward).
3. Apply the same rule to each of the four resulting segments.

After one iteration, a straight line becomes a line with a bump. After two iterations, each segment of that bumpy line gets its own bump. After infinite iterations, you get the Koch curve — a line of infinite length contained in a finite area.

A Koch snowflake applies this process to all three sides of an equilateral triangle.

The Code

"""Koch snowflake using turtle graphics and recursion."""
import turtle


def koch_curve(t, length, depth):
    """Draw a Koch curve segment recursively.

    Args:
        t: A turtle object.
        length: The length of the current segment.
        depth: Recursion depth (0 = straight line).
    """
    if depth == 0:
        # Base case: draw a straight line
        t.forward(length)
    else:
        # Recursive case: replace line with four sub-segments
        segment = length / 3
        koch_curve(t, segment, depth - 1)   # First third
        t.left(60)
        koch_curve(t, segment, depth - 1)   # Left side of triangle
        t.right(120)
        koch_curve(t, segment, depth - 1)   # Right side of triangle
        t.left(60)
        koch_curve(t, segment, depth - 1)   # Last third


def koch_snowflake(t, length, depth):
    """Draw a complete Koch snowflake (three Koch curves)."""
    for _ in range(3):
        koch_curve(t, length, depth)
        t.right(120)


def main():
    screen = turtle.Screen()
    screen.title("Koch Snowflake — Recursion Depth Demo")
    screen.setup(800, 600)
    screen.bgcolor("white")

    t = turtle.Turtle()
    t.speed(0)           # Fastest drawing speed
    t.pensize(1)

    # Draw snowflakes at depths 0 through 4
    positions = [(-350, 200), (-100, 200), (150, 200), (-225, -100), (75, -100)]
    sizes = [100, 100, 100, 150, 150]

    for i, (x, y) in enumerate(positions):
        if i >= 5:
            break
        t.penup()
        t.goto(x, y)
        t.pendown()
        t.color("navy")
        koch_snowflake(t, sizes[i], i)
        # Label the depth
        t.penup()
        t.goto(x + sizes[i] // 3, y - sizes[i] - 20)
        t.write(f"depth = {i}", font=("Arial", 10, "normal"))

    screen.exitonclick()


if __name__ == "__main__":
    main()

How Recursion Works Here

The koch_curve function is the heart of the fractal:

• Base case (depth == 0): Draw a straight line. No further subdivision.
• Recursive case: Instead of drawing one line, draw four smaller Koch curves — each one-third the length of the original — with turns between them that create the triangular bump.

At depth 1, one line becomes 4 segments. At depth 2, each of those 4 becomes 4, giving 16. At depth 3, you have 64 segments. At depth d, you have 4^d segments. The total length grows by a factor of 4/3 at each level (four segments each one-third the original length), which means the Koch curve's length is infinite at infinite depth — yet it fits inside a bounded area.

Counting the Recursive Calls

Each increase in depth multiplies the visual complexity by 4 — but the code stays the same. That's the power of recursion.

The Sierpinski Triangle

The Rule

The Sierpinski triangle starts with a filled equilateral triangle and applies one rule:

1. Find the midpoints of the three sides.
2. Remove the triangle formed by connecting those midpoints (the center triangle).
3. Apply the same rule to each of the three remaining corner triangles.

The Code

"""Sierpinski triangle using turtle graphics and recursion."""
import turtle


def draw_triangle(t, vertices, color):
    """Draw and fill a triangle given three vertices."""
    t.fillcolor(color)
    t.penup()
    t.goto(vertices[0])
    t.pendown()
    t.begin_fill()
    t.goto(vertices[1])
    t.goto(vertices[2])
    t.goto(vertices[0])
    t.end_fill()


def midpoint(p1, p2):
    """Return the midpoint of two points."""
    return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)


def sierpinski(t, vertices, depth):
    """Draw a Sierpinski triangle recursively.

    Args:
        t: A turtle object.
        vertices: A list of three (x, y) tuples.
        depth: Recursion depth (0 = single filled triangle).
    """
    colors = ["navy", "royalblue", "steelblue", "cornflowerblue",
              "lightskyblue", "lightblue", "powderblue", "aliceblue"]
    color = colors[min(depth, len(colors) - 1)]

    draw_triangle(t, vertices, color)

    if depth > 0:
        # Find midpoints
        mid_01 = midpoint(vertices[0], vertices[1])
        mid_12 = midpoint(vertices[1], vertices[2])
        mid_02 = midpoint(vertices[0], vertices[2])

        # Recurse on three corner triangles
        sierpinski(t, [vertices[0], mid_01, mid_02], depth - 1)
        sierpinski(t, [mid_01, vertices[1], mid_12], depth - 1)
        sierpinski(t, [mid_02, mid_12, vertices[2]], depth - 1)


def main():
    screen = turtle.Screen()
    screen.title("Sierpinski Triangle — Depth 5")
    screen.setup(700, 650)
    screen.bgcolor("white")

    t = turtle.Turtle()
    t.speed(0)
    t.hideturtle()

    # Define the outer triangle vertices
    top = (0, 250)
    bottom_left = (-300, -200)
    bottom_right = (300, -200)

    sierpinski(t, [top, bottom_left, bottom_right], depth=5)

    screen.exitonclick()


if __name__ == "__main__":
    main()

The Recursive Structure

The Sierpinski triangle is a textbook example of tree recursion — each call spawns three recursive calls:

• Base case (depth == 0): Draw a single filled triangle. Done.
• Recursive case: Draw the full triangle, then recurse on the three corner sub-triangles, each half the size of the original.

At depth 0, you draw 1 triangle. At depth 1, you draw 1 + 3 = 4 triangles. At depth 2, you draw 1 + 3 + 9 = 13. At depth d, you draw (3^(d+1) - 1) / 2 triangles. The removed center triangles create the characteristic hole pattern.

Why Fractals Matter in CS

Fractals demonstrate several fundamental CS concepts:

1. Recursion as a natural modeling tool. The code doesn't contain explicit descriptions of complex shapes — it contains a simple rule applied recursively. Complex behavior emerges from simple rules.

2. Self-similarity and divide-and-conquer. Fractals are the visual embodiment of the divide-and-conquer strategy from Chapter 17. Break the problem into smaller identical sub-problems, solve each recursively, and combine the results.

3. Exponential growth. A small increase in recursion depth creates a huge increase in computation. Understanding this growth is essential for choosing appropriate depth limits in real applications.

4. Real-world applications. Fractal geometry is used in: - Computer graphics: Generating realistic terrain, clouds, and vegetation in games and movies - Data compression: Fractal image compression exploits self-similarity - Antenna design: Fractal antennas can receive multiple frequencies in a compact size - Network analysis: Internet traffic patterns exhibit fractal-like self-similarity

Discussion Questions

1. The Koch snowflake has infinite perimeter but finite area. How is this possible? What does this tell you about the relationship between complexity and containment?

2. Both fractals use the same recursive structure: base case + self-similar recursive calls. Compare the Koch curve (4 recursive calls per step) with the Sierpinski triangle (3 recursive calls per step). How does the number of recursive calls affect the growth rate?

3. Try running the Koch snowflake code at depth 8 or higher. What happens to the drawing speed? At what depth does the visual difference become imperceptible? What does this suggest about choosing recursion depth in practice?

4. Broccoli, romanesco cauliflower, and fern leaves all exhibit fractal-like self-similarity. Pick one and describe the "recursive rule" that generates its structure. What is the "base case" in the biological version?

Mini-Project

Implement one of the following fractal patterns recursively:

1. The Cantor Set: Start with a line. Remove the middle third. Repeat on each remaining segment. (1D fractal — simpler than Koch.)

2. A Fractal Tree: Start with a trunk. At the top, branch into two shorter segments at angles. Each branch repeats the same process. Add randomness to the angles and lengths for a more natural look.

3. The Hilbert Curve: A space-filling curve that visits every point in a grid. Research the recursive rule and implement it with turtle graphics. This one is challenging but deeply satisfying.

For any of these, experiment with recursion depth and observe how the complexity grows. Record the number of recursive calls at each depth and verify that it matches the theoretical growth rate.