Goals

Understanding Recursion
- Defining Recursion
- Components of Recursion
- Head Recursion
- Tail Recursion

Resources

http://processing.org/learning/basics/functions.html

"To understand recursion, you must first understand recursion." ~ Anon

Defining Recursion

Recursion is defined as the repeated application of a recursive definition.
A recursive definition is a method who's output for a specific input is based on the output of the same method with related but different inputs.
Some examples from nature:

A section of a shell spiral is a different sized copy of the section before it
A tree branch can sprout another branch like the trunk that sprouted it
A cell divides in two, each copy has the ability to divide in two, like the first

Recursion is based on a recursive definition. It is a way to describe something in terms of itself.

The Base Case

What if the shell were to keep on spiraling, the tree branches branching, and the cells dividing? It would be chaos! There would be no end to the recursion. That is why we must always apply a base case to our recursive methods in order to get them to stop. Here are some examples of a base case.

if (size < 2) { //stop }
if (size > 2) { //continue } else { //stop }
if (num == 1) { //stop }

A base case is nothing more than an if statement which ensures the recursion will stop at some point.

Recursive Parameters and Arguments

A recursive method is defined by the parameters it has. The arguments to the parameters usually come from the previous calls to the recursive method. There is of course the initial arguments to the recursive method, and setting this up can be a bit tricky. Take a look at this example which computes the factorial of the argument in the first method call inside setup:

Head Recursion

A recursive method can choose to make the recursive method call before taking an action. This is referred to as head recursion. This means that all the recursive calls are made first, and then as the methods begin returning, the rest of the code in the method is executed. Take a look at this example:

Tail Recursion

Now if we want to do our action first and then make the recursive method calls, we would change the order. The real question is... why does nothing show up in this version?

The decision between head and tail recursion can result in slightly different effects.

void setup() {
  size(600, 600);
  background(255);
}
void mousePressed() {
  //we need to draw the first branch facing upwards
  //this is why we use the angle -PI/2
  drawBranch(mouseX, mouseY, mouseX, mouseY,
            -PI/2, (float)mouseY/height * 100);
}
void keyPressed() {
  if (key == ' ') {
    background(255);
  }
}
//we won't be using the draw method
//however it must exist so we can
//use mousePressed and keyPressed
void draw() {}
//the recursive definition of a branch
void drawBranch(float x, float y, 
                  float px, float py, 
                  float angle, float step) 
{
  //base case, we won't do anything if the
  //branch step size is less than 2
  if (step < 2) {
    return;
  } else {
    //store px and py
    px = x;
    py = y;
    //move the x,y
    x += step * cos(angle);
    y += step * sin(angle);
    //shrink the step size
    step *= 0.66;
    //store the current mouseX in the window as
    //a float between 0-1
    float xMouse = (float)mouseX/width;
    //make two recursive calls to the drawBranch method
    //notice one adds the angle, and one subtracts the angle
    drawBranch(x, y, px, py, angle + PI/4 * xMouse, step);
    drawBranch(x, y, px, py, angle - PI/4 * xMouse, step);
  }
  //we'll wait to draw our branches until after
  //we've made all the recursive method calls
  stroke(0);
  strokeWeight( max( 1, (int) step/5 ) );
  line(x, y, px, py);
}