A Gentle Graphical Introduction to Recursion

These are notes from an in-class exercise on recursion I did in a First Year Seminar. The basic idea is an old one: to draw a tree recursively.

(This particular exercise is directly inspired by a talk Dan Garcia gave at a recent SIGCSE about part of their CS 10 (CS Principles) class, The Beauty and Joy of Computing.)

Recursion and fractals

Many things can be expressed “recursively” that is, partly or wholly in terms of themselves. This is usually where your CS teacher immediately brings up factorial. BUT I WILL MANFULLY RESTRAIN MYSELF!

Instead, I’ll point out two things to get us started:

First, that recursion is a beautiful, simple (though maybe not easy) way to think about computation. The dual of the Turing machine is the lambda calculus, and it’s elegantly powered by recursion.

Second, that recursion is all around us in nature, in the form of fractals, which when used colloquially means “things that are similar to themselves over extended, but finite, scales.” (Show some examples from Wikipedia.)

We’re going to explore the concept of recursion graphically today, rather than with factorials and Fibonacci and the like. Well, I will probably do a little bit of factorial stuff at the end, but only because I’m contractually required.

Getting started

So, we’re going to learn to draw beautiful trees that look like this (slides).

But we’ll start with something simpler).

The important thing to see is that this tree is self-similar; in other words, it’s fractal: each part contains smaller versions of itself. (on board)

We’re going to draw this in Processing. But first, some preliminaries.

Setting up processing

Processing lets you do pretty arbitrary things (it’s Java, after all). We’re going to tame the complexity somewhat by doing “turtle graphics” aka “pen graphics.” In other words, we’re going to draw everything in terms of pen. The pen has three pieces of state: X, Y, and direction. This is similar to a turtle with a pen attached crawling around on a piece of paper, or my hand on the board, sorta.

float penX;
float penY;
float penDirection;

OK. So far, so nothing. Let’s set up the sketching area:

void setup() {
  size(600, 600);
  penX = width / 2;
  penY = height / 2;
  background(255);
  noLoop();
}

Line by line, what’s happening here?

size(600, 600); creates a viewable (x, y) rectangle to draw on – it’s the sketch, in Processing lingo. The x coordinates increase left to right, and the y coordinates increase top to bottom. This is the opposite of algebra y-axes! But it is common in graphics.

penX = width / 2; and the following line center the pen on the x/y coordinates.

background(255); sets the entire background to white. If you pass a value on the range 0…255 as a color, Processing interprets it as a shade of grey (0 = black, 255 = white).

noLoop(); tells Processing that once we start to draw, call draw() only one time; otherwise (by default) it is called repeatedly in an endless loop.

Now, let’s teach processing how to move the pen:

void move(float amount) {
  float newX = penX + sin(radians(penDirection)) * amount;
  float newY = penY - cos(radians(penDirection)) * amount;
  
  line(penX, penY, newX, newY);
  
  penX = newX;
  penY = newY;
}

This is a three-step process. First we have to compute where we’re going, on the basis of where we are. We use trig to figure out how far away in the x and y directions we need to go (remember, y is flipped, hence the minus). We draw a line from the pen’s current location to its new location. Then we update the pen’s location.

Let’s test it out in a draw() method:

void(draw) {
    move(50);
}

OK, that works. What about if we want to turn?

void turn(float degrees) {
  penDirection += degrees;
}

void(draw) {
    move(50);
    turn(90);
    move(50);
    turn(90);
    move(50);
    turn(90);
    move(50);
    turn(90);
}

Great. How about a random walk?

void draw() {
  turn(random(360));
  stroke(random(255), random(255), random(255)); // random pen color each time, RGB when you pass three values
  move(random(20));
}

And how about we use the mouse to turn it on and off?

void mousePressed() {
  loop();
}

void mouseReleased() {
  noLoop();
}

OK, now we’re cooking!

Drawing a tree

So, back to our drawing: notice that each tree is made up of smaller trees. We’re going to write a tree method that draws a tree? It’ll start with a move() call to draw the trunk, then it will turn left, draw the smaller tree, turn right, draw the smaller true, and go back to where it started.

In other words, It’ll start with a move() call to draw the trunk, then it will turn left, draw the smaller tree using tree(), and so on.

“Hey dawg, I heard you liked trees inside of your trees, so can you show me how I can use tree() inside of tree() to draw a tree?” That’s today’s magic.

No recursion here

First write tree1. All it does is draw the trunk by moving forward size and then backward size:

void tree1(float size) {
  move(size);
  move(-size);
}

Make sure it works:

void draw() {
    tree1(100);
}

Maybe also move the root of the tree down a bit:

// in setup()
penY = height * 0.9

Now, let’s draw a two-level tree.

void tree2a(float size) {
  move(size);
  turn(-15);
  move(size * 0.75);
  move(-size * 0.75);
  turn(30);
  move(size * 0.75);
  move(-size * 0.75);
  turn(-15);
  move(-size);
}

At this rate, it’s gonna take a lot of code to draw a beautiful tree. Don’t worry, though, we’ll get better.

Does everyone understand what’s happening above? (Trace through on board.)

More levels

OK, let’s simplify a bit. Do you see that tree2a contains tree1 if you stop and squint at it a bit? Let’s rewrite it to use tree1:

void tree2(float size) {
  move(size);
  turn(-15);
  tree1(size * 0.75);
  turn(30);
  tree1(size * 0.75);
  turn(-15);
  move(-size);
}

Now, I want you to write a tree3 that uses tree2. It should not use tree1. (Hint: it looks almost exactly like tree2; copy/paste and change three characters).

void tree3(float size) {
  move(size);
  turn(-15);
  tree2(size * 0.75);
  turn(30);
  tree2(size * 0.75);
  turn(-15);
  move(-size);
}

How would tree4 look? Exactly the same, except it would call tree3. So, here’s the big idea: we can write a tree method that uses itself to draw a tree, so long as it knows how many levels it’s expected to draw.

A Recursive tree

tree will need a levels parameter in addition to size:

void tree(int levels, float size) {
    move(size);
    turn(-15);
    tree(levels - 1, size * 0.75);
    turn(30);
    tree(levels - 1, size * 0.75);
    turn(-15);
    move(-size);
}

What happens when we run this in our draw() method?

As Processing helpfully explains, there’s a problem with our recursion. Let’s think about what’s going on. (on board, trace operation with levels = 2)

The problem is that the methods we wrote before aren’t all exactly the same: tree1 in particular just drew a trunk, and no branches. So, we need a special case to handle this:

void tree(int levels, float size) {
  if (levels == 1) {
    move(size);
    move(-size);
  }
  else {
    move(size);
    turn(-15);
    tree(levels - 1, size * 0.75);
    turn(30);
    tree(levels - 1, size * 0.75);
    turn(-15);
    move(-size);
  }

And now it works. Let’s try a larger levels for a prettier tree. (show 9)

This general code pattern, with a simple base case that doesn’t call the method itself, and a less simple case that does call itself, is typical of recursive code. Let’s break it down:

void tree(int levels, float size) {
  // the base case; a problem so simple we know how to handle it
  // completely
  if (levels == 1) {
    move(size);
    move(-size);
  }
  // the recursive case
  // do a small part here, and delegate the rest to somebody else
  else {
    // draw the trunk
    move(size);
    // position the pen for the left sub-tree
    turn(-15);
    // delegate drawing the left sub-tree to someone else
    tree(levels - 1, size * 0.75);
    // re-position for the right sub-tree
    turn(30);
    // delegate drawing the right sub-tree to someone else
    tree(levels - 1, size * 0.75);
    // re-position to go back to the start
    turn(-15);
    // retrace our steps back to where we started
    move(-size);
  }

Notice that in the recursive case, we are always making progress toward the base case – here, levels is guaranteed to be decremented by one each time the method calls itself, so we’re guaranteed (mostly) to hit levels == 1 and stop. If we don’t do this, the method calls itself indefinitely, and we end up with a StackOverflow (at least in Java).

What would happen if we started with levels < 1?

Sometimes a recursive program is more elegant if you have a smaller base case. What would a “zero level” tree mean? Can you rewrite the program to have a base case where levels == 0?

Some questions

(slides)

An exercise

Try to draw a more “beautiful” tree. Two things that might help:

strokeWeight(5);

makes the stroke (the ink left by the pen) five pixels wide instead of one.

And you can change the color by red green blue components. Google has a nice color picker to help.

stroke(75, 160, 15); // kinda greenish

Other comments on recursion

Of course we can define factorial recursively, too. And write in in Java. And probably you can trivially transform it to its iterative form. There’s a deeper truth here, that all recursive algorithms have an iterative equivalent (and vice versa), though the problem of designing the algorithm might yield more easily to one or other. For example, how would you draw a tree of arbitrary depth iteratively? For the supernerds: without a stack?

And, some other languages make use of recursion and recursive definitions much more natural than Java. For example, here’s a snippet of OCaml to computes the factorial:

let rec factorial = function 
  | 0 -> 1
  | x -> x * factorial (x - 1)
;;

print_int (factorial 10)

It’s like a direct transcription of the mathematical description!