# 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).

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`?

(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
``````

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!