Creative Coding · Session c19

Recursion

A function that calls itself, and a tree that grows from it.

Look at a fern leaf, a horse's mane braid, or a real tree. A branch splits into smaller branches, and each of those splits into even smaller ones. Every small branch looks like a tiny copy of the whole tree. In geometry, shapes that are the same but at a different size are called similar. Code can draw them with a trick called recursion: a function that calls itself to do a smaller version of its own job. Last session binary search kept shrinking its problem (100, 50, 25 ...). Recursion is the same habit written as a function.

Every recursive function needs two things

A base case: a simple situation where the function just stops and answers directly. Without it, nothing ever ends.
A recursive call on something smaller: the function calls itself with a problem that is closer to the base case (for example n - 1).

Step 1: a countdown

This function prints a countdown. Read it slowly: it contains a call to countdown inside countdown.

function countdown(n) {
  if (n === 0) {            // base case: stop here
    console.log('Go!');
    return;
  }
  console.log(n);
  countdown(n - 1);         // the function calls itself, with a smaller number
}

countdown(3);

Here is exactly what the computer does. Each call waits for the call below it to finish. This pile of waiting calls is called the call stack.

Picture the call stack for countdown(3)

countdown(3) n is 3, not 0. Print 3. Call countdown(2).

countdown(2) Print 2. Call countdown(1).

countdown(1) Print 1. Call countdown(0).

countdown(0) Base case! Print Go! and return. No more calls.

Then each call finishes in turn (1, then 2, then 3). Nothing is left to do after the recursive call, so the output is:

3 2 1 Go!

That is 4 calls in total: one for each of 3, 2, 1, and one for 0.

What if there is no base case? (paper only, do not run this)

Imagine we forgot the base case:

function countdown(n) {
  console.log(n);
  countdown(n - 1);
}

On paper: countdown(3) prints 3 and calls countdown(2). That prints 2 and calls countdown(1), then 0, then -1, then -2, and nothing ever says stop. Every call is still waiting, so the stack grows taller and taller. After roughly ten thousand calls the browser gives up and shows a red error: RangeError: Maximum call stack size exceeded. So the base case is not decoration. It is the part that makes the function finish. (We will never run this version. The tree below has a safety limit of 8 levels.)

Step 2: the tree

A tree is perfect for recursion. Drawing a tree of depth d means: draw one branch, then at its tip draw two smaller trees of depth d - 1, one leaning left and one leaning right. The base case is depth 0: draw nothing.

Picture how the tree grows

depth 1
1 branch

depth 2
3 branches

depth 3
7 branches

Each new level has twice as many branches as the one before: 1, 2, 4, 8 ... (the powers of 2 from c17). Adding them up, a tree of depth n has 2ⁿ minus 1 branches: 1, 3, 7, 15, 31, 63, 127, 255. Depth 8 has 255 branches.

The geometry link: every branch is a copy of its parent shrunk by the same scale factor, 0.7. A trunk of 62 pixels has children of about 43 pixels, then about 30 pixels. The angles never change, only the size, so every sub-tree is similar to the whole tree.

Live sketch: tap to grow the tree

Tap the picture to add one level of depth (after 8 it goes back to 1). Use the buttons to go deeper or shallower, and drag the slider to change the angle between branches. Watch the branch count double.

let depth = 4;
let angleSlider;

function setup() {
  createCanvas(420, 300);
  angleSlider = createSlider(0.2, 1.2, 0.5, 0.01);
}

function draw() {
  background('#ecfeff');
  text('depth ' + depth, 15, 25);
  translate(width / 2, height - 10);   // start at the bottom middle
  branch(62, depth);
}

function branch(len, d) {
  if (d === 0) return;                 // base case: no more branches
  let angle = angleSlider.value();
  strokeWeight(d);
  stroke(d === 1 ? '#16a34a' : '#7c4a21');
  line(0, 0, 0, -len);                 // draw this branch
  translate(0, -len);                  // move to its tip
  push();
  rotate(angle);
  branch(len * 0.7, d - 1);            // a smaller copy, leaning right
  pop();
  push();
  rotate(-angle);
  branch(len * 0.7, d - 1);            // a smaller copy, leaning left
  pop();
}

function mousePressed() {
  if (mouseX < 0 || mouseX > width || mouseY < 0 || mouseY > height) return;
  depth = depth % 8 + 1;               // tap: one level deeper, back to 1 after 8
}

Why does this work?

branch calls itself twice, so the number of calls doubles at every level. That is why a depth-8 tree has 255 branches but needs very little code.
Each call passes d - 1, so d counts down toward 0, just like the countdown. At d === 0 the base case returns and that part of the tree stops growing.
translate moves the starting point to the branch tip. push() and pop() save and restore the position, so after drawing the right branch, the left one starts again from the same tip.

Quick check

How many calls does countdown(5) make in total, including the base case? What does the base case of branch do?

Answer: 6 calls (for 5, 4, 3, 2, 1 and 0). The base case of branch is d === 0: it returns at once, so nothing is drawn and no more calls start.

Challenges: run, predict, fix, create

Copy the tree code into your p5 editor to try these. Keep the depth at 8 or below.

Modify. Change the scale factor 0.7 to 0.5, then to 0.85. Describe each tree in one sentence. Which factor makes the tree look like a bushy bush, and why do the branches overlap?
Predict. Here is a different function. Write what countup(3) prints before you run it. Then run it in your editor and compare. What changed compared to countdown, and why?
function countup(n) { if (n === 0) return; countup(n - 1); console.log(n); } countup(3);
Predict a count. Without using the sketch, say how many branches a depth-6 tree has. Then check your answer by tapping to depth 6 in the live sketch.
Bug hunt. A friend's tree leans hard to one side, like a windblown bush, and never looks symmetrical. The branch part looks like this. Find the one-character fix.
push(); rotate(angle); branch(len * 0.7, d - 1); pop(); push(); rotate(angle); branch(len * 0.7, d - 1); pop();
Create. Add blossoms: when d === 1, draw a pink circle (about 8 pixels wide) at the tip of the branch. Remember that after translate(0, -len) the tip is at (0, 0).
Create. Add a third branch that goes straight on (rotate(0), scaled by 0.7, with d - 1). Predict how many branches a depth-3 tree now has, then check by counting. Keep the depth at 6 or lower, because this tree grows much faster.

Check your predictions (after you have tried)

0.5 gives a thin, sparse tree with short twigs. 0.85 gives a dense bushy tree because the small branches are almost as long as their parents, so they overlap.
countup(3) prints 1 2 3. The print happens after the recursive call, so the deepest call finishes first: countup(0) returns, then 1 prints, then 2, then 3.
2⁶ minus 1 = 63 branches.
Both sides use rotate(angle). The second one must be rotate(-angle), a minus sign, so it leans the other way.
Add if (d === 1) { fill('#ec4899'); circle(0, 0, 8); } after the translate line.
Depth 1: 1, depth 2: 1 + 3 = 4, depth 3: 1 + 3 + 9 = 13 branches. Each level triples instead of doubles.

Next session → c20: Prompting (basic)
You now own the whole toolkit: variables, loops, functions, arrays, objects (c16), sorting and searching (c18) and recursion (c19). That makes you ready to judge code, including code an AI writes. Next you will learn to ask an AI for exactly the code you want, and to check what it gives back.

Recursion

Step 1: a countdown

Step 2: the tree

Live sketch: tap to grow the tree

Why does this work?

Ask your tutor