Lab 9
Page 2

Introduction to Recursion

What is Recursion?
Object-Oriented Recursion

What is Recursion?

Recursion refers to a self-referential way of defining things. A recursive definition of a series of items is one which defines each member of the series in terms of the previous members. For instance, the following is a recursive definition: for each number S(i) in a series, that number is equal to the previous number S(i-1) times 2 -- that is, S(i) = S(i-1)*2. Each recursive definition, must have at least one base case, i.e. at least one case where the definition is not in terms of previous members. In our example, we might have S(0)=1.

In computer programming, when we talk about recursion we are usually describing a section of code (such as an object method) which, as part of its operation, calls itself. For instance, a very simple recursive method would be the following:

public int f(int x)
{
  int val;
  val = f(x);
  return val;
}

Of course, this method would not be a very smart thing to write -- it would never finish running! In order to calculate val, f needs to know what the value of f(x) is... but to do that, it needs to know how to calculate val!

However, some recursive functions do make sense. For instance, if we change f slightly, we could come up with the following method:

public int f(int x)
{
  int val;
  if (x <= 1)
    {
      val = 1;
    }
  else
    {
      val = x * f(x-1);
    }

  return val;
}

In this function, each time f gets called there are two possibilities; if the value passed to f this time was greater that one, f returns the value of x * f(x - 1). Otherwise, it simply returns the value 1.

So, if you call the method f somewhere in your program by saying final_val = f(4), the computer would be able to reason through the following:

final_val = f(4) Because 4 > 1, f(4) = 4 * f(3) Because 3 > 1, f(3) = 3 * f(2) Because 2 > 1, f(2) = 2 * f(1) Because 1 <= 1, f(1) = 1 Therefore f(2) = 2 * 1 = 2 Therefore f(3) = 3 * 2 = 6 Therefore f(4) = 4 * 6 = 24 Therefore final_val = f(4) = 24.

This is just the factorial function x!, defined as a recursion. Other examples of recursions you may have seen include the Towers of Hanoi puzzle (to move a stack of n disks, you first move a stack of n-1 disks, etc.), Quicksort (to quicksort a list, put the pivot in its final spot, and then quicksort the left side and quicksort the right), and printing the nodes of a binary search tree in order (to print a tree, first print the left subtree, then print this node, then print the right subtree).

Object-Oriented Recursion

Most likely the examples of recursion you have seen so far had nothing to do with objects. The idea is the same, but the way of thinking about it may be slightly different. In this lab you are going to use recursion to draw a picture. This picture starts out as a single H object that draws itself in the middle of the screen. But, as a part of drawing itself this H creates and draws 4 smaller copies of itself. These copies each create 4 smaller H's, and so on. Finally the recursion stops at some point when the H's are so small that making 4 smaller ones would not make sense.

The H's all create smaller replicas of themselves, just like f(4) creates a new smaller call to f(3) above. Also the H's stop recursively creating smaller H's when they become sufficiently small, just as f(1) does not generate a recursive call to f(0).

1 | 2 | 3 | 4 | 5