Fractals

CS 106B: Programming Abstractions

Fall 2025, Stanford University Computer Science Department

Lecturer: Chris Gregg, Head CA: Yasmine Alonso

$An impressive fractal, demonstrating how a very few basic parts to an image can be beautiful$

Code for today:
- Cantor.zip
- Snowflake.zip

Observations about recursion

The base case represents the simplest possible instance of the problem you are solving.
- Example: How many people are behind you, including you? Answer? 1, it’s just me!
- Example: What is x^n? Answer: x^0 = 1
- Solve the Towers of Hanoi Answer: 1 ring is easy!
The recursive case represents how you can break down the problem into smaller instances of the same problem.
- Example: How many people are behind you, including you? Answer? 1 + the number behind me
- Example: What is x^n? Answer: x * x^(n-1)
- Solve the Towers of Hanoi Answer: N-1 disks to aux, 1 disk to target, N-1 disks to target

Fractals

A fractal is a recurring graphical pattern. Smaller instances of the same shape or pattern occur within the pattern itself.

$An image showing many fractals. The patterns are incredible -- they repeate again and again in each image, getting (in general) smaller each time. One image is of a programatically-generated tree with the main trunk branching off to smaller copies of itself, each with its own smaller copies, as well. Another example is the Sierpinski triangle, with three triangles encompassed inside a larger triangle. Each smaller triangle is itself made of three smaller triangles, and this keeps going to infinity.$

Fractal Examples in Nature

$Images of a broccoli-like plant, a fern, a snow-covered mountain, and a coastline -- all examples of natural fractals$

Many natural phenomena generate fractal patterns:
- earthquake fault lines
- animal color patterns
- clouds
- mountain ranges
- snowflakes
- crystals
- coastlines
- DNA

The Cantor Fractal

We can create many fractals programmatically, and because fractals are self-similar, we can do so recursively!
The first fractal we will code is called the “Cantor” fractal, named after the late-19th century German mathematician Georg Cantor.

$An image of an Egyptian architectural column, with a Cantor fractor built into the column$ $An image of a tattoo of the Cantor fractal on someone's arm$

The Cantor fractal is a set of lines (indeed, a “Cantor Set” of lines) where there is one main line, and below that there are two other lines, each 1/3rd of the width of the original line, one on theleft, and one on the right (with a 1/3 separation of white space between them)
Below each of the other lines is an identical situation: two 1/3rd lines.
This repeats until the lines are no longer visible.

The Cantor Fractal

$An image of the cantor fractal using just line segments$

In text, a 4-level Cantor fractal would look like this:

---------------------------
---------         ---------
---   ---         ---   ---
- -   - -         - -   - -

Parts of a cantor set image … are Cantor set images!

The Cantor Fractal

$An image of a six-level cantor fractal using just line segments, showing that the left third of the diagram under the original line is a Cantor set, and so is the right third of the diagram under the original line$

The Cantor fractal above has six levels.
Every individual line segment is its own 1-level Cantor fractal

How to draw a level 1 Cantor fractal

A single line, going across the whole screen

How to draw a level `n` Cantor fractal

A single line, going across the whole screen. Underneath, on the left, is a space where it says 'draw a cantor of size n-1', and on the right, it says 'draw a cantor of size n-1'

Draw a line from start to finish.
Underneath, on the left third, draw a Cantor of size n - 1.
Underneath, on the right third, draw a Cantor of size n - 1.

Graphics in C++ with the Stanford library: `GPoint`

An image showing an x/y axis with the origin in the top left. There is a single point labeled 'GPoint a', and some code that says, GWindow w; GPoint a(100, 100); cout << a.getX() << endl;

An image showing an x/y axis with the origin in the top left. There are now two points labeled 'GPoint a' and 'GPoint b', and some code that says, GWindow w; GPoint a(100, 100); GPoint b(20, 20); w.drawLione(a, b);

Let’s code!

$The Cantor fractal and the Qt Logo$

Snowflake Fractal

$A 'snowflake' fractal which is made up of lines and triangles. It has the apperance of a snowflake with six 'sides' of the snowflake, with each side made up of an infinite number of smaller line/triangle segments. See below on how we are going to draw it$