Recursion and Fractals Simulation

About this experiment

A tree is a trunk with two smaller trees on top. That one sentence is a complete program: a function that draws a branch and then calls itself twice. Recursion turns short rules into rich pictures. Watch a tree, a Sierpinski triangle and a Koch snowflake being built call by call, follow the call stack as it grows and shrinks, and count how quickly the number of calls explodes as the depth goes up.

Learning goals

Identify the base case and the recursive case of a recursive function
Trace the order in which recursive calls run and return
Explain what the call stack holds and why its depth matters
Calculate the number of calls for a given depth, such as 2^(n+1) − 1 for a binary tree
Describe self-similarity and calculate a simple fractal dimension

How to use it

1Choose the tree at depth 3 and watch the calls slowly. Which branch is drawn first: the left or the right one? Why?
2Pause while the stack is at its deepest. What does each frame on the stack represent? How many frames are there compared with the depth?
3Fill in a table of depth against calls for the tree. Find the rule and check it at depth 10.
4Change the branch angle and the length ratio. Which settings make the branches overlap?
5Switch to the Sierpinski triangle. Where in the code is the base case? How many triangles are drawn at depth 5?
6Build the Koch snowflake to depth 5. Use the readouts to explain how the perimeter can keep growing while the area stays limited.

The model

C (n) = 1 + 2 C (n - 1), C (0) = 1 \Rightarrow C (n) = 2^{n + 1} - 1

Calls made by the binary tree of depth n

N_{Sierpinski} = 3^{n}, N_{Koch} = 3 \cdot 4^{n}

Shapes drawn at the deepest level

P_{n} = P_{0} (\frac{4}{3})^{n} \to \infty, A_{n} \to \frac{8}{5} A_{0}

Koch snowflake: endless perimeter, finite area

D = \frac{lo g ( number of copies )}{lo g ( 1/ scale factor )}

Similarity dimension: Koch log 4/log 3 ≈ 1.26, Sierpinski log 3/log 2 ≈ 1.58

Assumptions

The calls run one at a time in program order, depth first, exactly as an ordinary programming language runs them.
The pseudocode passes positions and directions as parameters, so no turtle state has to be restored after a call returns.
The fractal dimension of the tree, log 2 / log(1/r), only describes the tips when the branches do not overlap.
Maximum depths are limited so that the step by step replay stays fast: 12 for the tree, 7 for the triangle and 6 for the snowflake.

Try this in class

Q1What would happen if the tree function had no base case?
Q2How many calls does the Sierpinski function make at depth 4? Explain your answer with a sum.
Q3Why does the call stack never get deeper than the recursion depth plus one, even though thousands of calls are made?
Q4Write a recursive function that computes n! and identify its base case.
Q5The coastline of Britain looks longer the shorter the ruler you measure it with. How does the Koch snowflake explain this?

Frequently asked questions

Is recursion slower than a loop?

Each call costs a little time and memory for its stack frame, so a loop is often slightly faster. But for branching structures such as trees, nested folders or parsing, recursion is much simpler to write, and any recursion can be rewritten with your own explicit stack.

What is a stack overflow?

Every unfinished call keeps a frame on the call stack. If the recursion goes too deep, for example because the base case is never reached, the stack runs out of memory and the program crashes with a stack overflow error.

Where are fractals found in nature?

Ferns, Romanesco broccoli, river networks, lightning, blood vessels and the branching airways of the lungs are all approximately self-similar over several scales, which is why recursive rules are used to generate them in computer graphics.