Fractals

CS 106B: Programming Abstractions

Fall 2024, Stanford University Computer Science Department

Lecturers: Cynthia Bailey and Chris Gregg, Head CA: Jonathan Coronado

Slide 2

Announcements

• Assignment 2 is due end-of-day today (Monday)
• Assignment 3 will be released today.

Slide 3

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
• 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

Slide 4

Arms-length Recursion

Last time, we looked at the following code:

// this is the primary function 
int fasterFibonacci(int n)
{
    // this will hold our results as {n, Fib(n)}, starting with our base cases
    Map<int, int> memos = { {0, 0}, {1, 1} };
    return fasterFibonacci(n, memos);
}

// this is a recursive helper function
int fasterFibonacci(int n, Map<int, int>& memos)
{
    // if we already know the answer, just return it
    if (memos.containsKey(n)) {
        return memos[n];
    } else {
        // calculate new answer and save it for later
        int result = fasterFibonacci(n - 1, memos) + fasterFibonacci(n - 2, memos);
        memos[n] = result;      
        return result;
    }
}

What if we checked the map before doing the n - 1 and n - 2 cases? E.g.,

// this is the primary function 
int fasterFibonacci(int n)
{
    // this will hold our results as {n, Fib(n)}, starting with our base cases
    Map<int, int> memos = { {0, 0}, {1, 1} };
    return fasterFibonacci(n, memos);
}

// this is a recursive helper function
int fasterFibonacci(int n, Map<int, int>& memos)
{
    // if we already know the answer, just return it
    if (memos.containsKey(n)) {
        return memos[n];
    } else {
        int result1;
        if (memos.containsKey(n - 1)) {
            result1 = memos[n - 1];
        } else {
            result1 = fasterFibonacci(n - 1, memos);
        }
        int result2;
        if (memos.containsKey(n - 2)) {
            result2 = memos[n - 2];
        } else {
            result2 = fasterFibonacci(n - 2, memos);
        }

        memos[n] = result1 + result2;      
        return result1 + result2;
    }
}

• This is called "arms length recursion," and is an anti-pattern, and poor style.
• It is poor style because we aren't letting the base case do the work. The code without the n - 1 and n - 2 checks is cleaner, and the next calls to the function immediately return because the base case (checking the map) happens.

Slide 5

Fractals

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

Slide 6

Fractal Examples in Nature

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

Slide 7

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.
• 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.

Slide 8

The Cantor Fractal

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

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

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

Slide 9

The Cantor Fractal

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

Slide 10

How to draw a level 1 Cantor fractal

Slide 11

How to draw a level n Cantor fractal

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

Slide 12

Graphics in C++ with the Stanford library: GPoint

Slide 13

Let's code!

Slide 14

Snowflake Fractal

Slide 15

Let's break this down to a smaller part

Slide 16

Depth 1 Snowflake: A line

Slide 17

Depth 2 Snowflake: The line has a triangle break

Slide 18

Depth 3 Snowflake: In progress

Slide 19

Depth 3 Snowflake: In progress

Slide 20

Depth 3 Snowflake: Finished

Slide 21

Let's Code a Snowflake!