Lesson: Loops and Recursion

(Lessons) (Previous: Lesson: Fractals) (Next: Lesson: Recursion Review)

Table of Contents

1. Review

In this section we have learned the two problem solving methods that are the foundation of everything we will do in computer science. Loops require you to break down a problem into a single step that is repeated many times. Recursion asks you to assume that you have a way to solve the problem for a simpler case, and figure out how to reduce a more complex case to the simpler case.

Before you start writing any code, in any computer program, you need to know exactly how your code will work. It is no good just copying random code and trying to tie it together somehow; you have to think before you do anything. This is especially true when solving a problem using loops or recursion: I need to be able to explain clearly and rigorously what my strategy is before I start writing any code, or I will be lost.

What makes this hard is that usually you are trying to go from a description of what the desired solution looks like, to a procedure for actually obtaining it. It is of course necessary to understand very clearly what the problem is asking for, but even if you know that much, you won't get anywhere until you figure out a strategy to search for the answer.

My uncle works at a company that does a lot of programming, and he says that when he interviews a condidate for a job, he can tell almost instantly whether they are a good programmer or not by how they approach a sample problem. Some people will immediately start writing down code that feels plausible, and then will see what it does, and if it doesn't work, fuss with it until it actually does what it is supposed to. Others will sit for a while and analyze the problem carefully, then write teh code correctly the first time. I'm sure you can figure out for yourself who ends up getting the job.

1.1. Analyzing looping problems

When you are using loops to solve a problem, there are several issues you need to get locked down before you start writing your code:So, for example, suppose that I am trying to solve this problem:


I think to myself:
  1. I am searching for values for these three variables. I know that c has to be an integer, less than or equal to 20. This means that b can be at most 19, and a can be at most 18. A good place to start is to loop through all possible values of a:

    for(int a = 1; a <= 18; a++) {

  2. As I do this, I need to count how many triples I find. So, I should declare a variable - int count - outside the loop to keep track of this.
  3. Next, I think about what I will do with each value of a. I say to myself, "For each value of a, I want to find every value of b for which a² + b² is a square number." Notice how I have turned my description into a procedure: I am now doing a search through possible values of b in order to find one that meets some condition.

    The phrase "every value of b" in my little description above suggests that there is another loop going on inside the one I already have. Again, the first step is thinking out how the counting will work. I know that b has to be greater than a; that makes (a + 1) a good starting point. But what is the maximum value of b? Looking back at the problem, I know that √(a² + b²) has to be less than or equal to 20. So:

    for(int b = a + 1; Math.sqrt(a * a + b * b) <= 20; b++) {

  4. Now I have to think to myself what will happen inside this inner loop. First I take a second to take stock of what I know about my variables each time through:I know how to find c as a double. It looks like this:

    double c = Math.sqrt(a * a + b * b);

    The trick is to figure out whether this is an integer. Digging into my bag of tricks, I remember that I can round off a double to an int by adding .5 and then truncating to an integer. So, perhaps I should round the square root to an integer, and then check if the equivalence is still true:

    int c = (int)(Math.sqrt(a * a + b * b) + .5);
    if(c * c == a * a + b * b) {
       System.out.println("(" + a + ", " + b + ", " + c + ")");
       count++;
    }

The whole code for this example looks like this:

public int triples() {
   int count = 0;
   for(int a = 1; a <= 18; a++) {
      for(int b = a + 1; Math.sqrt(a * a + b * b) <= 20; b++) {
         int c = (int)(Math.sqrt(a * a + b * b) + .5);
         if(c * c == a * a + b * b) {
            System.out.println("(" + a + ", " + b + ", " + c + ")");
            count++;
         }
      }
   }
   return count;
}

In general, looping problems will clearly have either a process that is repeated over and over again, or a range of numbers that you need to search through. Later on in the course, we will also see situations where you are looping through a String, as many of you did with Lindenmeyer systems, or where you are looping through a collection of objects.

1.2. Analyzing Recursion Problems

In solving a problem recursively, you take quite a different approach than you do in solving one iteratively. With a loop, you have to identify first what the smallest, repeating piece of the problem is, and then try to duplicate that over and over. In a recursive problem, you instead assume that your method solves the problem, and you write your method by trying to think of how to break down a more complicated case - usually meaning bigger parameter values - into a simpler case.

So, the process of figuring out a recursive solution to a problem looks like this:
  1. First, you have to describe exactly what it is that your method accomplishes - it moves a stack of n disks to a different tower, or it multiplies two numbers. Part of your task here is to write the signature of the method - think carefully about what information needs to go into it, and what it will give back.
  2. Next, think out how you can reduce one particular case into one or more simpler cases, and then combine the answers. So, for example, you say, "Moving n disks means moving n-1 to the extra tower, then moving the nth disk, then moving the n-1 back on top of it." You can go ahead and write in this code, which is usually very simple.
  3. At this point, you have a method that will run forever. You need to identify a base case, some point that the program will always reach, when it gets to sufficient depth, and that can be answered with a simple answer rather than a more complex one. The base case will be identified with an if statement.
Remember, the main thing that makes recursive reasoning special is that you start by describing exactly how your method works, and then, relying on the fact that it will eventually actually do that, you go about fillin in the actual code.

As an example, suppose that I have a method double f(double x) that represents some mathematical function. Here is an example of an f that is a simple cubic funcion:

double f(double x) {
   return .5 * x * x * x + 1 * x * x - 2 * x - 3;
}

A plot of this function - draw, appropriately enough, by a Turtle - is shown to the right. As you can see, I have labeled the x and y intercepts of the function.

Suppose that you wanted to write a method to locate one of the roots of this function - that is, an x value for which f(x) is 0. You would have to specify what range of x's to look in, since as you can see there are three roots. So, my method might look something like this:

// Return the x value in the given range for which f(x) = 0
public double root(double minX, double maxX)

So, for example, root(0, 4) ought to return 1.865, and root(-2, 0) ought to return -1.2111.

If I want to implement this method recursively, I think to myself: "How can I simplify the task of looking for a root in the given range?" Well, a simple way to do it would be to narrow the range. I will do this by figuring out where the function changes sign - in the first half, or the second half. Wherever that happens, I can call root() again with a reduced range just containing half of the original range:

// Return the x value in the given range for which f(x) = 0
public double root(double minX, double maxX) {
   double midX = (minX + maxX) / 2;
   if(f(maxX) * f(midX) < 0) {
      // If multiplying these two gives a negative number, they are opposite in sign.
      // So, the function crosses the axis in the first half
      return root(minX, midX);
   } else {
      // Otherwise, the function crosses the axis in the second half
      return root(midX, maxX);
   }
}

As usual, I find myself with a method that really ought to work, except that it will never terminate: it just keeps looking at smaller and smaller ranges. I need to introduce a "base case" that will end the whole process when we get to a difference that is too small to matter. A simple way to define this would be to stop when the width of my range is too small to be noticeable; if it is, say, less than .00001, then the error must be less than that.

// Return the x value in the given range for which f(x) = 0
public double root(double minX, double maxX) {
   double midX = (minX + maxX) / 2;
   if(maxX - minX < .00001) {
      return midX;
   } else if(f(maxX) * f(midX) < 0) {
      // If multiplying these two gives a negative number, they are opposite in sign.
      // So, the function crosses the axis in the first half
      return root(minX, midX);
   } else {
      // Otherwise, the function crosses the axis in the second half
      return root(midX, maxX);
   }
}

2. Exercise: sandwich()

Let us define a sandwich of size n to be a String containing the number n enclosed between two sandwiches of size n - 1. A sandwich of size 0 is an empty string. So, for example, sandwich(2) = "121", and thus sandwich(3) = "1213121".

Write both a recursive and an interative method to calculate this. Be sure that you carefully work out how each method works before you start writing code.

What would you modify if you wanted each sandwich to be enclosed in parentheses, as in "(((1)2(1))3((1)2(1)))"?

What would you modify to take the nubmers out of the above pattern, so that sandwich(3) just returns "((()())(()()))"?

Solution to sandwich()

3. Homework

Loops and Recursion (pdf) (Due: 10/24/06)

(Lessons) (Previous: Lesson: Fractals) (Next: Lesson: Recursion Review)