TwiddleLab / Code / Recursion: Functions That Call Themselves

Drawing Fractals

Lesson 7 of 11 · 7 min · Free, no account needed

What you will learn

• A fractal is a shape made of smaller copies of itself: a tree is a trunk with two smaller trees on top.
• The recursion depth is how many levels of copies you draw. Depth 0 is the base case: one stick.
• A tree of depth d has 2^d tips: one more level doubles them.
• The Koch curve turns every stick into 4 sticks a third as long, so each level multiplies its length by 4/3.

Start the lesson

How the lesson goes

1. Ferns, broccoli, lightning. Why do so many things look like smaller copies of themselves?

   This fern was drawn by a program. Zoom into one of its side leaves.

2. A tree is a trunk with two smaller trees on top.

   Drag the depth up to 3 and count the tips.

3. This tree has depth 3 and 8 tips. How many tips at depth 6?

   Every tip of the depth-5 tree gets two branches at depth 6. So tips go 1, 2, 4, 8, 16, 32, 64: 2^depth.

4. Fractals and recursion depth.

   A fractal is a shape built from smaller copies of itself. Code draws it with recursion: draw a piece, then call yourself, smaller.

   The recursion depth is how many levels deep the calls go. Depth 0 is the base case: draw one stick and stop.

   Doubling at each level is why fractals get detailed so fast: depth 10 already has 1024 tips.

5. Design your own tree.

   Change the angle between branches and how much each one shrinks.

6. Watch the code draw your tree.

   The pen follows tree(depth, length). Notice which branches come first.

   tree(4) can't draw its right branch until tree(3) on the left has finished everything, and that one waits for tree(2), and so on. So the pen climbs to the far left tip first.

7. Build the Koch rule: one stick becomes four.

   Four equal sticks, a third as long: flat, up to a peak, down, flat. Then the rule runs on every stick.

8. The first stick has length 1. How long is the Koch curve after 3 levels?

   Each level: 4 sticks, each a third as long. Within 0.08 counts.

   Each stick becomes 4 sticks of a third the length: 4/3 of the old length. Three levels: (4/3)^3 = 64/27, about 2.37. That's a geometric sequence.

9. Tip targets: grow your tree to exactly 32 tips, then 128.

   Set the depth and press Grow it. Fewest tries wins.

Previous lesson: Towers of Hanoi · Next lesson: Divide and Conquer · Part of the course: Recursion: Functions That Call Themselves

Lessons are interactive and need JavaScript. Turn it on to play them.