Case Study 2: Drawing Fractals with Recursion — Sierpinski Triangle and Koch Snowflake

Fractals: Recursion Made Visible

A fractal is a geometric shape that exhibits self-similarity — each part of the shape looks like a smaller copy of the whole. This is recursion made visible. Fractals are not abstract mathematical curiosities: they appear in coastlines, snowflakes, blood vessels, tree branches, lightning bolts, and the structure of the universe itself.

In this case study, we use recursion to generate two famous fractals: the Sierpinski triangle and the Koch snowflake. These programs produce visual output that makes the recursive structure unmistakably clear.

The Sierpinski Triangle

The Construction Rule

Start with a filled equilateral triangle. Find the midpoints of its three sides and connect them, forming four smaller triangles. Remove the center triangle. Now repeat the process for each of the three remaining triangles. Continue to any desired depth.

Depth 0:     Depth 1:      Depth 2:
   /\           /\            /\
  /  \         /  \          /  \
 /    \       /----\        /----\
/______\     /\    /\      /\  /\/\
             /  \  /  \    /--\/--\/\
            /____\/____\  /\  /\/\  /\
                          /--\/--\/--\

The Recursive Insight

Drawing a Sierpinski triangle of depth N means: - Base case (depth 0): Draw a filled triangle (or simply mark the three vertices). - Recursive case: Compute the midpoints of the triangle's three sides, then draw three Sierpinski triangles of depth N − 1 at the top, bottom-left, and bottom-right sub-triangles.

ASCII Implementation

Since we are working in a text console, we use a character grid:

program SierpinskiTriangle;

const
  MAX_DEPTH = 5;
  WIDTH = 64;   { 2^(MAX_DEPTH + 1) }
  HEIGHT = 32;  { 2^MAX_DEPTH }

var
  Grid: array[0..HEIGHT - 1, 0..WIDTH - 1] of Char;

procedure InitGrid;
var
  R, C: Integer;
begin
  for R := 0 to HEIGHT - 1 do
    for C := 0 to WIDTH - 1 do
      Grid[R, C] := ' ';
end;

procedure DrawSierpinski(Row, Col, Size, Depth: Integer);
var
  Half: Integer;
  R, C: Integer;
begin
  if Depth = 0 then begin
    { Base case: draw a small triangle }
    for R := 0 to Size - 1 do
      for C := -R to R do
        if (Row + R < HEIGHT) and (Col + C >= 0) and (Col + C < WIDTH) then
          Grid[Row + R, Col + C] := '*';
  end
  else begin
    Half := Size div 2;
    { Top sub-triangle }
    DrawSierpinski(Row, Col, Half, Depth - 1);
    { Bottom-left sub-triangle }
    DrawSierpinski(Row + Half, Col - Half, Half, Depth - 1);
    { Bottom-right sub-triangle }
    DrawSierpinski(Row + Half, Col + Half, Half, Depth - 1);
  end;
end;

procedure PrintGrid;
var
  R, C: Integer;
begin
  for R := 0 to HEIGHT - 1 do begin
    for C := 0 to WIDTH - 1 do
      Write(Grid[R, C]);
    WriteLn;
  end;
end;

begin
  WriteLn('Sierpinski Triangle (Depth ', MAX_DEPTH, ')');
  WriteLn;
  InitGrid;
  DrawSierpinski(0, WIDTH div 2, HEIGHT, MAX_DEPTH);
  PrintGrid;
end.

Analysis

• Recursion depth: Exactly the depth parameter (5 in our example).
• Number of triangles drawn: 3^depth (3, 9, 27, 81, 243 for depths 1–5).
• Self-similarity: Zoom into any corner of a depth-5 Sierpinski triangle and you see a depth-4 Sierpinski triangle. This is the fractal property.

The Koch Snowflake

The Construction Rule

Start with an equilateral triangle. For each line segment: 1. Divide it into three equal parts. 2. Replace the middle third with two sides of a smaller equilateral triangle (pointing outward). 3. Repeat for each resulting line segment.

After one iteration, each side has 4 segments. After two, 16. After N iterations, each original side has 4ᴺ segments.

The Recursive Insight

Drawing a Koch curve of depth N between two points means: - Base case (depth 0): Draw a straight line from point A to point B. - Recursive case: Compute three intermediate points that divide the line into thirds and add the triangular bump, then draw four Koch curves of depth N − 1.

ASCII Implementation

For the Koch snowflake, we use a coordinate-based approach and render to a character grid:

program KochSnowflake;

uses
  Math;

const
  GRID_SIZE = 80;
  DEPTH = 4;

var
  Grid: array[0..GRID_SIZE - 1, 0..GRID_SIZE - 1] of Char;

procedure InitGrid;
var
  R, C: Integer;
begin
  for R := 0 to GRID_SIZE - 1 do
    for C := 0 to GRID_SIZE - 1 do
      Grid[R, C] := ' ';
end;

procedure PlotPoint(X, Y: Real);
var
  IX, IY: Integer;
begin
  IX := Round(X);
  IY := Round(Y);
  if (IX >= 0) and (IX < GRID_SIZE) and
     (IY >= 0) and (IY < GRID_SIZE) then
    Grid[IY, IX] := '*';
end;

procedure DrawLine(X1, Y1, X2, Y2: Real);
var
  Steps, I: Integer;
  DX, DY: Real;
begin
  Steps := Round(Sqrt(Sqr(X2 - X1) + Sqr(Y2 - Y1)) * 2);
  if Steps = 0 then Steps := 1;
  DX := (X2 - X1) / Steps;
  DY := (Y2 - Y1) / Steps;
  for I := 0 to Steps do
    PlotPoint(X1 + I * DX, Y1 + I * DY);
end;

procedure KochCurve(X1, Y1, X2, Y2: Real; Level: Integer);
var
  DX, DY: Real;
  X3, Y3, X4, Y4, X5, Y5: Real;
begin
  if Level = 0 then
    DrawLine(X1, Y1, X2, Y2)
  else begin
    DX := X2 - X1;
    DY := Y2 - Y1;

    { One-third point }
    X3 := X1 + DX / 3;
    Y3 := Y1 + DY / 3;

    { Two-thirds point }
    X4 := X1 + 2 * DX / 3;
    Y4 := Y1 + 2 * DY / 3;

    { Peak of the equilateral bump }
    X5 := (X3 + X4) / 2 - (Y4 - Y3) * Sqrt(3) / 2;
    Y5 := (Y3 + Y4) / 2 + (X4 - X3) * Sqrt(3) / 2;

    { Four recursive Koch curves }
    KochCurve(X1, Y1, X3, Y3, Level - 1);
    KochCurve(X3, Y3, X5, Y5, Level - 1);
    KochCurve(X5, Y5, X4, Y4, Level - 1);
    KochCurve(X4, Y4, X2, Y2, Level - 1);
  end;
end;

procedure PrintGrid;
var
  R, C: Integer;
begin
  for R := 0 to GRID_SIZE - 1 do begin
    for C := 0 to GRID_SIZE - 1 do
      Write(Grid[R, C]);
    WriteLn;
  end;
end;

var
  CX, CY, Radius: Real;
  X1, Y1, X2, Y2, X3, Y3: Real;

begin
  WriteLn('Koch Snowflake (Depth ', DEPTH, ')');
  WriteLn;

  InitGrid;

  { Define the three vertices of the initial equilateral triangle }
  CX := GRID_SIZE / 2;
  CY := GRID_SIZE / 2;
  Radius := GRID_SIZE * 0.4;

  X1 := CX;
  Y1 := CY - Radius;
  X2 := CX - Radius * Sqrt(3) / 2;
  Y2 := CY + Radius / 2;
  X3 := CX + Radius * Sqrt(3) / 2;
  Y3 := CY + Radius / 2;

  { Draw three Koch curves forming the snowflake }
  KochCurve(X1, Y1, X2, Y2, DEPTH);
  KochCurve(X2, Y2, X3, Y3, DEPTH);
  KochCurve(X3, Y3, X1, Y1, DEPTH);

  PrintGrid;
end.

Mathematical Properties of the Koch Snowflake

The Koch snowflake has a fascinating property: its perimeter is infinite, but its area is finite.

• After N iterations: Each side has 4ᴺ segments, each of length (1/3)ᴺ of the original. Total perimeter = 3 × (4/3)ᴺ × original side length. Since 4/3 > 1, this grows without bound.
• Area: The snowflake's area converges to 8/5 of the original triangle's area — a finite limit.

This means the Koch snowflake is a shape with infinite boundary but finite interior — a genuinely mind-bending property that emerges naturally from recursion.

Comparing the Two Fractals

Why Fractals Matter for Programmers

Fractals are not just mathematical art. They teach three critical lessons about recursion:

1. Self-similarity is the essence of recursion. Fractals make this visible in a way that factorial and Fibonacci cannot.

2. Small recursive rules create complex emergent behavior. The Koch curve's construction rule is trivially simple, yet it produces a shape of infinite complexity. Many real-world systems — markets, ecosystems, weather — exhibit this property.

3. Recursion depth controls resolution. Depth 1 gives a crude approximation; depth 5 gives fine detail. This is analogous to the precision tradeoff in many algorithms — more recursion means more accuracy but more work.

Discussion Questions

1. The Sierpinski triangle removes area at each step, eventually approaching zero area. The Koch snowflake adds perimeter at each step, eventually approaching infinite perimeter. Both are generated by simple recursive rules. What does this tell us about the relationship between local simplicity and global complexity?

2. If you increase the Sierpinski triangle depth from 5 to 6, how many more base-case triangles are drawn? How does this relate to the concept of exponential growth?

3. Real snowflakes exhibit Koch-like fractal branching. Why might nature "use" fractal structures? (Hint: think about surface area vs. volume.)

4. Could you generate these fractals iteratively? What data structures would you need? Compare the complexity of the iterative approach to the recursive one.

Key Takeaways

• Fractals are geometric manifestations of recursion: each part resembles the whole.
• The Sierpinski triangle and Koch snowflake can each be generated with fewer than 30 lines of recursive logic.
• Fractal generation demonstrates that recursion depth controls the level of detail.
• Simple recursive rules can produce shapes with surprising mathematical properties (infinite perimeter, zero area).
• Fractals appear throughout nature and computer graphics, making recursive thinking a practical skill, not just a theoretical one.