Unit 11: Recursion

11.0. Overview

Visual recursion on a box of hot chocolate mix

Recursion is an important topic in computer science, probably the most important topic that doesn't get covered well in most introductory computer science courses. That's partly because it can be a little confusing at first, and maybe because the concept of recursion—drilling down deeper and deeper into the memory of the computer, with the possibility of never getting out alive—is a little scary, at least existentially.

Using recursion and "thinking recursively" is an important skill in computer science, and we're going to spend a good part of our time in this course doing just that: using recursion and thinking recursively.

Let's get started!

1. Recursion: Definition & Examples
2. Visual Recursion
3. More Difficult Recursion

11.1. Recursion

Ummmm.... yeah. So what does that mean?

Let's take a look at a specific example.

11.1.1. Simple recursion

Take a moment to analyze this Blastoff.java program.

/**
 * This program uses a static method to demonstrate 
 * recursive calls.
 */
 
public class Blastoff 
{
    
    /**
     * This recursive method follows the 2 rules of recursion:
     * 1. Have a "base case" for which you STOP recursing.
     * 2. Have the method call itself with a parameter that has changed
     */
    public static void countdown(int n)
    {
        if (n == 0)       // BASE CASE
        {
            System.out.println("Blastoff!");
            return;
        }
        else
        {
            System.out.println(n);
            countdown(n - 1);       // RECURSIVE CALL
            return;
        }
    }
    
    public static void main(String[] args) 
    {
        countdown(5);
    }
}

Here's another tool that you can use to visualize Java code execution: Java Visualizer.

11.1.2. Simple looping with recursion

Here's a simple loop that we can write recursively. Given an initial value start and an end value stop, this recursive loop counts from start to stop - 1:

public class RecursiveLoop
{
    public static void loop(int start, int stop)
    {
        if (start == stop)
        {    
            return;     // BASE CASE
        }
        else
        {
            System.out.println(start);
            loop(start + 1, stop);      // RECURSIVE CALL
        }
        return;
    }
    
    public static void main(String[] args)
    {
        loop(0, 10);
    }
}

11.1.3. Summing values in a loop, versus recursively

If we want to write a function to add the values from 1 through n using a loop, it's not too difficult:

public static int sumValues(int n)
{
    sum = 0;
    for (int i = 0; i <= n; i++)
    {
        sum += i;
    }
    return sum
}

If you System.out.println(sumValues(10)); this code runs just fine, and is what you'd ordinarily write to accomplish something like this.

We can also write a recursive version of this function, however, a version in which the function calls itself. One of the keys to doing this is think about what's happening when we add those numbers. If I want to add the numbers from 1 to 10, I can think about that sum as being 10 + the sum of all the lower numbers 1 through 9.

I might write it like this: The sum of numbers 1-10 = 10 + the sum of numbers 1-9.

What is the sum of the numbers 1-9, though? Isn't that just 9 + the sum of numbers 1-8?

Likewise, The sum of numbers 1-8 = 8 + the sum of numbers 1-7. There's a pattern emerging here.

Take a look at this function:

public static int sumValues(int n)
{
    return n + sumValues(n - 1);
}

That single line of code in this function returns a value that includes n + the sum of the numbers lower than n. When the sum() function calls itself, that's the recursive part of this function.

It's a clever way of looping that is actually much simpler and cleaner than the loop_sum written above. It might even be easier to conceptualize, at least if you're comfortable with the concept of recursion.

I ran into a problem when I actually tried to run this code, however:

java.lang.StackOverflowError
	at RecursiveSum.sumValues(RecursiveSum.java:19)
	at RecursiveSum.sumValues(RecursiveSum.java:19)
	at RecursiveSum.sumValues(RecursiveSum.java:19)
	at RecursiveSum.sumValues(RecursiveSum.java:19)
	at RecursiveSum.sumValues(RecursiveSum.java:19)

The reason this function ran into trouble is that it never identified a way for it to stop calling itself. At some point, we need the function to be able to tell itself that it shouldn't call itself anymore.

How do I know when I'm done adding the numbers from n on down? Once n gets down to the value 1, I shouldn't call the function recursively again. I just want to send back the value of 1.

public static int sumValues(int n)
{
    if (n == 0)
        return 0;
    else
        return n + sumValues(n - 1);
}

This program works correctly.

Make sure you understand exactly what's happening here.

1. We define a function which, as part of its description, calls itself in a slightly modified form.
2. We call the function ( sumValues(10) for example) with a specific value, which will be identified as n during the that call.
3. When the function calls itself again with the value n - 1, all of the values for that first function call are kept in memory, and the new function call creates a new "state" in memory with the new values (n - 1 for n, etc.).
4. This process continues, which each new function call generating a new instance of itself in memory until the limiting condition is met.
5. The return instruction exits from the current state, and the program returns to processing the previous state of the function.
6. This process of calling functions and returning from their states continues until the very first function call returns a value. At that point the recursive process has completed.

11.1.4. Factorial recursion

Summing the values from 1 to n is a nice simple introduction to recursion. Now try this.

public static long fact(long n)
{
    if (n == 1) return 1;
    else return n * fact(n - 1);
}

public static void main(String[] args)
{
    System.out.println(fact(20));
}

11.1.5. Accidental recursion

Based on what you know about recursion to this point, take a look at the problem below.

public static void playGame()
{
    // code to play game of blackjack
    // more code
    
    System.out.println("Play again (y/n)? ");
    String continue = in.next();
    if continue.equals("y")
    {
        playGame()
    }
}

11.1.6. Fibonacci recursion

You almost certainly know the Fibonacci sequence, which begins with the values 0 and 1. (There are other ways of defining the Fibonacci sequence, but this is the one we'll use here.) Each successive value in the series is based on the sum of the previous two values.

The Fibonacci series is a great example to think about recursively, and it's easily coded.

11.2. Visual Recursion

There are obvious "visual recursions" like the hot chocolate can above, or a series of nested Russian dolls, with each doll of size n containing a smaller doll of size n - 1, down to some final size.

There are other visual recursions as well. Here's one.

Coastline

Show/hide "coastline"

 

It's possible to draw our own graphical recursions, of course.

11.2.1. The Processing application and the Turtle class

The Processing application you can download at at processing.org. For our study here, we're first going to write a Turtle class that we can use in our Processing application.

The idea of a "Turtle" that can draw graphics was developed by Seymour Papert and others in the 1960s. Papert envisioned technology as a means of inspiring whole new ways of learning, and his book Mindstorms, published in 1980, outlined many of those ideas. (The book's title was subsequently used as the name of a robotics system developed by Lego.)

Rather than using a mechanical turtle as developed by Papert, we're going to use a virtual turtle that moves across the computer screen. This computer has a "tail" that can be "down," in which case it will leave a trace across the computer screen, or "up," in which case it will move without leaving a trail.

A summary of this virtual Turtle's methods is given here.

Writing a class in Processing is slightly different from writing it in straight Java. Do the following assignment to make sure you've got a working Turtle class before proceeding.

A Processing program and the PTurtle class

Using the Processing library, write a main program called TurtleTester that creates a Turtle object and has it draw a square.

The Turtle class is called PTurtle, for Processing Turtle.

The PTurtle class itself is written in a separate class (a separate tab in the Processing environment). Remember that the main() part of a Processing package with its setup() and draw() methods has to be in the first tab, with other classes as needed in additional tabs to the right.

Show/hide PTurtle class

/**
 * Defines a Turtle class that can be used in the 
 * Processing environment. Based on code from Jamie Matthews, 
 * http://j4mie.org/blog/simple-turtle-for-processing/
 */

class PTurtle 
{
  
    // instance variables
    float x, y;         // Current position of the turtle
    float angle;        // Current heading of the turtle
                        // 0 = positive x-axis
    boolean penDown;    // The state of the pen
  
    /**
     * Constructs a Turtle object
     * @param x the initial x-coordinate of the Turtle
     * @param y the initial y-coordinate of the Turtle
     */
    PTurtle (float x, float y) 
    {
        this.x = x;
        this.y = y;
        angle = 0;    // ie, pointing along the positive x-axis
        penDown = true;
    }
  
    /**
     * Moves the turtle forward by the specified distance
     * @param distance the distance to move forward
     */
    void forward (float distance) 
    {
        float newX = x + cos(radians(angle)) * distance;
        float newY = y + sin(radians(angle)) * distance;
    
        // If the pen is down, draw a line to the new position
        if (penDown) line(x, y, newX, newY);
    
        // Update position
        x = newX;
        y = newY;
    }
  
    /**
     * Moves the turtle back by the specified distance
     * @param distance the distance to move backward
     */
    void back (float distance) 
    {
        forward(-distance);
    }
  
    /**
     * Moves the turtle directly to a new x,y location
     * @param newX the new x-coordinate
     * @param newY the new y-coordinate
     */
    void moveTo(float newX, float newY)
    {
        x = newX;
        y = newY;
    }

    /**
     * Turns the turtle to the left by the given angle.
     * @param angle the number of degrees to rotate left
     */
    void left (float angle) 
    {
        this.angle -= angle;
    }
  
    /**
     * Turns the turtle to the right by the given angle.
     * @param angle the number of degrees to rotate right
     */
    void right (float angle) 
    {
        this.angle += angle;
    }
  
    /**
     * Lifts the pen up so that the tail won't draw
     */
    void penUp() 
    {
        penDown = false;
    }
  
    /**
     * Sets the pen up so that the tail will draw
     */
    void penDown() 
    {
      penDown = true;
    }
}

11.2.2. RecursiveSpiral

Take a look at the this RecursiveSpiral.pde and see if you can anticipate what will be drawn before the code executes.

// declares instance variables for the main()
// Just a Turtle object

PTurtle t;      

// Sets up the graphical window's size, background color,
// and initializes the turtle to a position in the
// lower-left corner of the screen.

void setup()   // initializes the screen and turtle
{
  size(700, 700);
  background(#ffffff);
  t = new PTurtle(0, 0);
  t.penUp();
  t.moveTo(50, height - 50);
  t.penDown();
}

// A recursive function that will be called by the main
// (draw) loop.

void drawAndTurn(PTurtle t, float lineLength)
{
  if (lineLength <= 0)
    return;
  else
  {
    t.forward(lineLength);
    t.left(90);
    drawAndTurn(t, lineLength - 3);
  }
}

// The main draw() loop. Ordinarily, this would be run 
// over and over, but here, with a noLoop at the end, it
// only runs once.

void draw()
{
  drawAndTurn(t, 600);
  noLoop();
}

11.2.3. Recursive Trees

The recursive tree is based on a branch, which produces branches, each of which produce branches...

Each branch is a little shorter than the one before it.

11.2.3.1. Improvements to the RecursiveTree

The Turtle class that we've written so far has some capabilities, but the trees that we can create don't look very tree-like. There are two modifications that we can make to PTurtle that will give us a lot more power.

Now that we've got expanded capabilities in PTurtle, we can expand RecursiveTree.

11.3. More Difficult Recursion

We'll have the chance to explore some more complex recursion a little later on in this course. For now, let's take a look at two standard applications of recursion: solving the "Towers of Hanoi" puzzle and navigating a maze.

11.3.1. The Towers of Hanoi

The Towers of Hanoi is a classic problem which we'll demonstrate in class.

This problem lends itself quite nicely to a recursive solution: each move, you're moving a disk from a source tower to another tower.

Consider what happens if we have Tower A with two disks on it and we're trying to get them all over to Tower C. The general strategy: move all the top disks to B, then move A to C, then move all the disks from B to C.

We'd use the exact same strategy with three disks...

But how do we code that?

11.3.2. Navigating a Maze

Coming soon!