Recursive Fractal Generation: Live Coding the Sierpinski Triangle in p5.js

Fractals are mathematical sets that exhibit repeating patterns at every scale—a property known as self-similarity. One of the most famous and visually striking examples is the Sierpinski Triangle (also called the Sierpinski Gasket).

Implementing the Sierpinski Triangle is a classic computer science exercise. It provides a visual demonstration of divide-and-conquer recursion, spatial decomposition, and coordinate geometry. Using p5.js—a creative coding library for JavaScript—we can translate abstract recursive algorithms into dynamic visual graphics.

---

1. Geometric Foundations of the Sierpinski Triangle

The Sierpinski Triangle is formed by taking an initial bounding triangle and subdividing it recursively into smaller congruent triangles:

1. Start with an outer triangle defined by three vertices: $P_1$, $P_2$, and $P_3$.
2. Locate the midpoints of all three edges:
   • $M_1$ between $P_1$ and $P_2$ (Left edge)
   • $M_2$ between $P_2$ and $P_3$ (Bottom edge)
   • $M_3$ between $P_3$ and $P_1$ (Right edge)
3. Connecting $M_1$, $M_2$, and $M_3$ partitions the original triangle into four sub-triangles:
   • One top corner triangle: $(P_1, M_1, M_3)$
   • One bottom-left corner triangle: $(M_1, P_2, M_2)$
   • One bottom-right corner triangle: $(M_3, M_2, P_3)$
   • One central inverted triangle: $(M_1, M_2, M_3)$
4. In the classic construction, the central inverted triangle is removed (left empty), and the process recursively repeats for the three corner sub-triangles until a specified depth is reached.

                    P1
                    /\
                   /  \
                  /    \
              M1 /______\ M3
                /\      /\
               /  \    /  \
              /____\  /____\
            P2      M2      P3

---

2. Decomposition Architecture & Data Structures

To build a clean, maintainable visual program, the implementation separates geometric primitives from recursive rendering logic.

Coordinate Model

In p5.js, coordinates are represented as 2D vectors via createVector(x, y). The canvas origin (0, 0) is at the top-left corner:

• $P_1$ (Top vertex): Centered horizontally near the top: (width / 2, 0)
• $P_2$ (Bottom-left vertex): Bottom left: (0, height)
• $P_3$ (Bottom-right vertex): Bottom right: (width, height)

Data Flow Diagram

graph TD
    Init[Canvas Setup & Base Triangle] --> Root[Outer Triangle T]
    Root --> Subdivide[Find Midpoints: M1, M2, M3]
    Subdivide --> T1[T1: Top Sub-Triangle]
    Subdivide --> T2[T2: Bottom-Left Sub-Triangle]
    Subdivide --> T3[T3: Bottom-Right Sub-Triangle]
    
    T1 -->|Level < Max| Subdivide
    T2 -->|Level < Max| Subdivide
    T3 -->|Level < Max| Subdivide
    
    T1 -->|Level == Max| BaseCase[Render / Return]
    T2 -->|Level == Max| BaseCase
    T3 -->|Level == Max| BaseCase

---

3. Step-by-Step Implementation

Step 1: Defining the Triangle Class

Wrapping vertices and styling within a Triangle class encapsulates rendering behavior and simplifies recursion.

class Triangle {
  constructor(p1, p2, p3, color) {
    this.p1 = p1;
    this.p2 = p2;
    this.p3 = p3;
    // Fallback to random color if not explicitly provided
    this.color = color || getRandomColor();
  }

  draw() {
    fill(this.color);
    stroke(255);
    triangle(
      this.p1.x, this.p1.y,
      this.p2.x, this.p2.y,
      this.p3.x, this.p3.y
    );
  }
}

function getRandomColor() {
  return color(random(100, 255), random(100, 255), random(100, 255));
}

Step 2: Midpoint Computation

Calculating the midpoint between two vector coordinates is done by averaging their $x$ and $y$ components:

$\text{Midpoint}(A, B) = \left(\frac{A_x + B_x}{2}, \frac{A_y + B_y}{2}\right)$

function getMidpoint(p1, p2) {
  return createVector(
    (p1.x + p2.x) / 2,
    (p1.y + p2.y) / 2
  );
}

Step 3: Recursive Subdivision Engine

The recursive function takes a triangle, the current depth, and the target recursion depth. It computes the midpoints, constructs the three sub-triangles, draws them, and recurses.

function drawSierpinski(tri, currentLevel, maxLevel) {
  // Base Case: Stop recursion once maximum depth is reached
  if (currentLevel >= maxLevel) {
    return;
  }

  // Calculate midpoints of the three edges
  const m1 = getMidpoint(tri.p1, tri.p2); // Left edge midpoint
  const m2 = getMidpoint(tri.p2, tri.p3); // Bottom edge midpoint
  const m3 = getMidpoint(tri.p3, tri.p1); // Right edge midpoint

  // Construct the three new corner triangles
  const t1 = new Triangle(tri.p1, m1, m3); // Top
  const t2 = new Triangle(m1, tri.p2, m2); // Bottom-left
  const t3 = new Triangle(m3, m2, tri.p3); // Bottom-right

  // Render the newly formed triangles
  t1.draw();
  t2.draw();
  t3.draw();

  // Recurse into each sub-triangle
  drawSierpinski(t1, currentLevel + 1, maxLevel);
  drawSierpinski(t2, currentLevel + 1, maxLevel);
  drawSierpinski(t3, currentLevel + 1, maxLevel);
}

Step 4: Canvas Initialization

In p5.js, setup() initializes the environment and triggers the primary drawing routine.

function setup() {
  createCanvas(600, 600);
  background(20);
  noLoop(); // Fractals are static; prevent continuous redraws

  const p1 = createVector(width / 2, 20);      // Top vertex
  const p2 = createVector(20, height - 20);    // Bottom-left vertex
  const p3 = createVector(width - 20, height - 20); // Bottom-right vertex

  // Draw root bounding triangle
  const rootTriangle = new Triangle(p1, p2, p3, color(40));
  rootTriangle.draw();

  // Begin recursive subdivision (depth: 5 levels)
  const MAX_DEPTH = 5;
  drawSierpinski(rootTriangle, 0, MAX_DEPTH);
}

---

4. Complexity & Operational Trade-offs

Time Complexity

At each level $k$, every triangle branches into $3$ smaller triangles.

$\text{Total triangles rendered} = \sum_{k=0}^{\text{depth}-1} 3^k = \frac{3^{\text{depth}} - 1}{2}$

• Time Complexity: $O(3^N)$, where $N$ is the maximum recursion depth.
• At depth 1: $3^0 = 1$ base operation.
• At depth 5: $1 + 3 + 9 + 27 + 81 = 121$ sub-triangles.
• At depth 10: $29,524$ sub-triangles.

Because branching is ternary ($3^N$), pushing the depth beyond 8–10 in a client-side JavaScript canvas can trigger noticeable frame drops or call stack limits.

Space Complexity

The call stack grows linearly with the maximum recursion depth:

• Stack Depth: $O(N)$
• Heap Allocation: In this implementation, each recursive step instantiates new p5.Vector and Triangle objects. For high depths, allocating memory inside the recursive loop increases garbage collection overhead. Pre-allocating coordinates or drawing directly with triangle(...) without storing intermediate objects reduces memory churn.

---

5. Key Takeaways

• Fractal Geometry via Recursion: Complex mathematical patterns emerge from small, self-referential rules. The Sierpinski Triangle demonstrates that an infinite-perimeter, zero-area fractal can be approximated with just a few lines of recursive code.
• Importance of Base Cases: Without the conditional guard currentLevel >= maxLevel, a ternary recursive branch causes an immediate RangeError: Maximum call stack size exceeded.
• Separation of Concerns: Encapsulating geometry (p1, p2, p3), drawing primitives (Triangle.draw()), and division logic (getMidpoint()) creates clean, debuggable procedural graphics code.