Session A1: Recursion

In this laboratory session, you will investigate an alternate control mechanism for repetition: recursion. The goals of this session are to

• motivate the uses of recursion;
• compare recursion and iteration; and
• introduce a few key important functions.

Your instructor will tell you which of the proposed experiments you are to perform.

Prerequisite skills:

• Java methods
• Java's looping mechanisms: while and for loops
• Java's conditional execution statements: if and switch

Required files:

• DateTester.java, as created in prior laboratory sessions.
• RecursiveExamples.java
• RecursiveExperiments.java
• SimpleDate.java, as modified in prior laboratory sessions.
• SimpleInput.java
• SimpleOutput.java
• SplitDown.java

Discussion

As you may have noted by now, methods provide an elegant and usable mechanism for encapsulating code. By putting collections of statements in a method, we can clarify our code (a method call, in effect, gives a short summary of what the body does), simplify reuse (in that we can easily reuse methods rather than copy code), and ease updating (in that when we need to change or fix a problem in a common action, we need only update one method, rather than a large number of copies of identical or near-identical code). As methods become more and more common in your programs, you will find that you will often write methods that call other methods (that call other methods that call other methods that ...).

If a method can call other methods, can it call itself? Would we ever want a method to call itself? In some programming languages, the answer is no. In Java, it is perfectly acceptable to have a method call itself. A method that calls itself is called a recursive method.

Why recurse?

You may ask yourself, ``Why would I ever write a recursive function?'' Surprisingly (or perhaps not so surprisingly), many algorithms are naturally expressed recursively. For example, let us once again consider the problem of determining the number of days before the start of the current month. You may recall that we developed a program to answer that question when we first encountered Java's looping mechanisms. Here is another way to look at the solution:

• There are 0 days before January 1.
• Suppose we knew the number of days before the first day of month m. Then the number of days before the first of month (m+1) is the number of days before the first day of m plus the number of days in m.

The ``suppose we knew'' in that solution is somewhat misleading. Even if we didn't know the number of days before the first day of month m, it is still the case that the number of days before the first day of month (m+1) is the number of days before the first day of month m plus the number of days in month m. Alternately, the number of days before the first day of month m is the number of days before the first day of month m-1 plus the number of days in month m-1.

That is, to determine the number of days before the first day of some month, we need to determine the number of days before the first day of the prior month. We might use the daysUntilStartOfMonth that we developed in a prior lab. However, the new method we are developing, which we will call daysBeforeFirstOfMonth, should also be able to solve that problem.

Putting it all into Java code, we get the following.

  /**
   * Determine the number of days before the start of month m.
   * Returns -1 for invalid months.
   */
  public int daysBeforeFirstOfMonth(int m) {
    // Is the month invalid?
    if ((m < 1) || (m > 12)) {
      return -1;
    } // Invalid month
    // Base case: it's January.  There are no days before January 1.
    else if (m == 1) {
       return 0;
    } // January
    // Every other month
    else {
       return daysBeforeFirstOfMonth(m-1) + daysInMonth(m-1);
    } 
  } // daysBeforeFirstOfMonth(int)

As this method suggests, most recursive methods have two parts. First, there are one or more base cases that do not involve any recursion. In daysBeforeFirstOfMonth, the base cases are the test for an invalid month and the test for January. Next, there are one or more recursive cases in which the function calls itself. In daysBeforeFirstOfMonth, the recursive call is done for every valid month except January.

In Experiment A1.1 you will explore some simple recursion functions.

Mathematics and recursion

It turns out that recursion is a natural mechanism for expressing many mathematical functions. Consider the factorial function, which we may define informally as

The factorial of N, written N!, is the product of all the numbers from 1 to N.

However, this definition is somewhat vague. First of all, it is unclear what we mean by ``the numbers from 1 to N''. Is 1.5 one of the numbers between 1 and 2? In addition, it is unclear what the domain of factorial is. Can we compute the factorial of -2? Of 0? Of 1.5? It is also conceivable that ``product'' could be misunderstood.

Let's try again.

The factorial of a positive whole number N, written N!, is the product 1 * 2 * 3 * ... * N.

This definition is also vague, although in somewhat different ways than the previous definition. In particular, what the sequence is may not be obvious. It could be a sequence of positive whole numbers. It could be a sequence of positive whole numbers divisible only by themselves and 1. In addition, this definition may make us question whether it is possible to compute 2! or 1!.

Hence, most mathematicians tend to define factorial recursively. In addition, they define the factorial of 0 as 1. A definition might read

The factorial of 0, written 0!, is 1. The factorial of a positive whole number N, written N!, is N multiplied by the factorial of N-1.

Note that it is relatively easy to turn this into Java code.

  /**
   * Compute n!.
   */
  public int factorial(int n) {
    // Base case: The factorial of 0 is 1.
    if (n == 0) {
      return 1;
    } // base case
    // Recursive case: The factorial of n is n*n-1.
    else {
      return n * factorial(n-1);
    } // recursive case
  } // factorial(int)

Do we need to express factorial recursively? Certainly not. It is also possible to express factorial iteratively, using a while or for loop.

  /**
   * Compute n! iteratively.
   */
  public int fact(int n) {
    int result = 0; // The value of the factorial
    int i;          // A counter variable
    for(i = 1; i <= n; ++i) {
      result *= i;
    } // for
    return result;
  } // fact(int)

Is one method better than the other? It depends on the criteria used to define better. For example, writing clear code is important. Which method is clearer? Different people will give different answers. Some find the recursive version much clearer and the iterative version muddled. Others find the iterative version clearer and are confused by the recursive version. When comparing the two, you might also look at use of variables and note that while fact uses two variables, factorial uses none. On the other hand, fact will work (although perhaps not correctly) even when given an invalid input (such as a negative number), while factorial will run forever on negative inputs.

In Experiment A1.2 you will investigate the factorial function.

Fibonacci Numbers

Another mathematical object commonly described recursively is the Fibonacci sequence. The Fibonacci numbers (i.e., the elements of the sequence) are defined as follows:

• The first two elements of the sequence are 1 and 1.
• Every subsequent element is the sum of the previous two elements.

For example, the third element of the sequence is 2 (1+1=2), the fourth element of the sequence is 3 (1+2=3), the fifth element of the sequence is 5 (2+3=5), and the sixth element of the sequence is 8 (3+5 = 8).

The following is a recursive method that computes the Nth Fibonacci number.

  /** 
   * Compute the nth Fibonacci number.
   */
  public int fib(int n) {
    // Base case: n is 1 or 2
    if ((n == 1) || (n == 2)) {
      return 1;
    } // base case
    // Recursive case
    else {
      return fib(n-1) + fib(n-2);
    } // recursive case
  } // fib(int)

Unfortunately, it turns out that this method is relatively slow (we will explore why in the experiments). Hence, it may be more efficient to rewrite the method iteratively. How? We could use an array of the Fibonacci numbers and fill it in left to right.

  /**
   * Compute the nth Fibonacci number iteratively.
   */
  public int fibit(int n) {
    // The array of Fibonacci numbers.  fibs[i] is the ith
    // Fibonacci number.
    int[] fibs = new int[n];
    // A counter to be used in loops.
    int i;

    // Fill in the first two elements
    fibs[0] = 1;
    fibs[1] = 1;

    // Fill in the remaining elements
    for (i = 2; i < n; ++i) {
      fibs[i] = fibs[i-1] + fibs[i-2];
    } // for

    // We're done.  Return the answer.
    return fibs[n-1];
  } // fibit

In Experiment A1.3 you will investigate Fibonacci numbers.

A guessing game

Suppose we want to play the game of ``I'm thinking of a number. Can you guess which one?'' Is there a strategy that makes it easier to find the number? It depends on what kind of answers you get when you guess. If the answers are only ``No'' or ``Yes'', then you might as well guess each number in sequence. However, if the answers are ``Too small'', ``Too large'', or ``Correct'', then there is a better strategy, expressed by the following Java-like pseudocode.

  /**
   * Try to guess a number in the range [small ... large].  Only the
   * oracle knows the correct answer.
   */
  void guessNumber(int small, int large, SimpleOutput out, Oracle oracle) {
    // Make sure there are possibilities.
    if (large < small) {
      out.println("No possible answers!");
      return;
    }
    // Make a guess directly between the two.
    int guess = (small+large) / 2;
    out.println("I guess: " + guess);
    // Is it correct?
    if (oracle.isCorrect(guess)) {
      out.println("Wa hoo!  The answer is " + guess);
    }
    // Is it too small?  If so, we know it has to be in the range
    // [guess+1 ... large].
    else if (oracle.isSmall(guess)) {
      guessNumber(guess+1,large,out,oracle);
    }
    // It's not correct.  It's not too small.  It must be too large.  
    // Hence, the number must be in the range [small ... guess-1].
    else {
      guessNumber(small,guess-1,out,oracle);
    }
  } // guessNumber(int,int)

Is this a good strategy? Yes, it's surprisingly good. Note that each time, we throw away about half of the numbers left to consider (we may throw away half or we may throw away one more than half). If we had to guess a number between 1 and 100, after one step we'd be left with no more than fifty numbers (from now on, we won't write ``no more than''). After two steps we'd be left with twenty-five numbers. After three steps we'd be left with twelve numbers. After four steps we'd be left with six numbers. After five steps we'd be left with three numbers. After six steps, we'd be left with one number. In this step, we'd get the answer (unless we'd guessed the answer in an earlier step). Seven steps to find an answer in one hundred numbers if fairly good.

Suppose we had 1,000,000 numbers? How many steps would it take? 1,000,000; 500,000; 250,000; 125,000; 62,500; 31,125; 15,625; 7,812; 3,906; 1,953; 976; 488; 244; 122; 61; 30; 15; 7; 3; 1. Less than twenty steps. Not too shabby, given that we've gone from one hundred numbers to one million.

This technique is called divide and conquer. If you can split your problem in half in one step (as we were able to eliminate half the range in one step), you can often get much better solutions.

If you'd like to see how many steps it would take to guess a number in other ranges, you can use SplitDown.java. We will return to this problem in a subsequent lab on searching.

Exponentiation

Let us turn to another interesting mathematical problem, that of exponentiation, computing the value of a number raised to a power. We will limit ourselves to powers that are nonnegative whole numbers.

Here is a simple iterative method that does the necessary computation. Basically, we multiply 1.0 by x the appropriate number of times (n times when computing x to the n power).

  /**
   * Iteratively compute x^n, for n >= 0.
   */
  public double itExp(double x, double n) {
    double result = 1.0;
    int i;               // A counter
    for (i = 1; i <= n; ++i) {
      result = result * x;
    } // for
    return result;
  } // itExp(double,int)

However, if we rewrite this recursively, we can use the divide-and-conquer technique to improve the running time. In particular, we can take advantage of the fact that x^2k = (x^k)*(x^k).

  /**
   * Recursively compute x^n, for n >= 0.
   */
  public double recExp(double x, double n) {
    // Base case: n is 0, x^n is 1.
    if (n == 0) {
       return 1.0;
    } // base case
    // Recursive case: n is 2k.  Compute x^k.
    else if (n is even) {
      double tmp = recExp(x, n/2);
      return tmp*tmp;
    } // n is even
    // Recursive case: n is odd.  Compute x*x^(n-1).
    else {
      return x * recExp(x, n-1);
    } //n is odd
  } // recExp(double,int)

How do we determine if a number is even or odd? We use the modulus or remainder operator, %. a%b gives the remainder after dividing a by b. For example, 10%3 is 1 (since 10 is 3*3 + 1), 20%7 is 6 (since 20 is 2*7 + 6), and 20%6 is 2 (since 20 is 3*6 + 2).

How does the modulus operator help us? Well, we know that a number is even if its remainder when dividing by two is 0. Hence, we can change

    else if (n is even) {

to

    else if (n%2 == 0) {

Again, this provides a relatively efficient mechanism for computation. If we use the iterative exponentiation method, computing 2³² takes 32 steps. If we use the recursive method, computing 2³² takes about eight steps.

In Experiment A1.4 you will investigate the various mechanisms for exponentiation.

Experiments

Name: ________________
ID:_______________

Experiment A1.1: Simple recursive functions

Required code files:

• SimpleDate.java, as modified in the prior laboratory sessions.
• DateTester.java, as created in prior laboratory sessions.

Step 1. Add the following method to your SimpleDate class.

  /**
   * Determine the number of days before the start of month m.
   */
  public int daysBeforeFirstOfMonth(int m) {
    // Base case: it's January.  There are no days before January 1.
    if (m == 1) {
       return 0;
    } // January
    // Every other month
    else {
       return daysUntilStartOfMonth(m-1) + daysInMonth(m-1);
    } // A month that's not January 
  } // daysBeforeFirstOfMonth(int)

Note that this is slightly different than the method we developed in the discussion. In particular, it doesn't include the test for errors and it uses daysUntilStartOfMonth to compute the number of days before the start of the prior month.

Add the following lines to the main method of DateTester. If you do not already have a DateTester class, create one that includes a main method which creates a SimpleOutput object called out.

    SimpleDate helper = new SimpleDate(7, 31, 1930);
    out.print("The number of days before June is ");
    out.println(helper.daysBeforeFirstOfMonth(6));

Recompile the two classes and execute DateTester. What output do you get? Is that output correct?

Step 2. If you are confident that your daysUntilStartOfMonth method written in the laboratory session on loops is correct, add the following lines to DateTester to test our new daysBeforeFirstOfMonth method.

    int m;
    int days1;
    int days2;
    for (m = 1; m <= 12; ++m) {
      days1 = helper.daysUntilStartOfMonth(m);
      days2 = helper.daysBeforeFirstOfMonth(m);
      if (days1 != days2) {
        out.println("Error on month " + m);
        out.println("  The old algorithm computed: " + days1);
        out.println("  The new algorithm computed: " + days2);
      } // if
    } // for

Recompile the two classes and execute DateTester. What output do you get? What does that suggest?

After writing your answer, you may want to look at the notes on this step..

Step 3. Hopefully, your work in the previous step indicated that the two methods are identical. This should mean that daysBeforeFirstOfMonth can be used wherever daysUntilStartOfMonth is used. (There is a well understood adage that if two methods behave identically on all significant inputs, then one can be used in place of the other.)

In particular, we can replace the call to daysUntilStartOfMonth with a call to daysBeforeFirstOfMonth within the body of daysBeforeFirstOfMonth. Do that. Your new method body should be

    // Base case: it's January.  There are no days before January 1.
    if (m == 1) {
       return 0;
    } // January
    // Every other month
    else {
       return daysBeforeFirstOfMonth(m-1) + daysInMonth(m-1);
    } // A month that's not January 

Recompile SimpleDate. Execute DateTester. Record the output. What does this output suggest?

After writing your answer, you may want to look at the notes on this step.

Step 4. We are now ready to consider cases in which the two methods competing methods might fail. In particular, since there are only twelve months in the year, what do they do about month 13? Update the for loop to use 13 as an upper bound. Recompile and execute DateTester. Record the output. What does this output suggest?

Step 5. It may also be instructive to see what value the two methods generate for month 13. Add the following lines to your main method. Recompile and execute DateTester. Record the output. What does this output suggest?

    days1 = helper.daysUntilStartOfMonth(13);
    days2 = helper.daysBeforeFirstOfMonth(13);
    out.println(days1 + "," + days2);

Step 6. Extend the loop to test months up to month 20. You may find it convenient to print out the number of days in the month for each iteration of the loop. Recompile and execute DateTester. Record the output. What does this output suggest?

Step 7. Remove the loop from your main method. If you'd like to keep it around but not execute it, you may find it easiest to comment out the code. Put an opening slash-star comment before the loop and a closing star-slash comment after the loop. For example,

/*
    // The following lines are no longer being used,
    // since we've verified that the two methods are identical
    // on the given values.
    for (m = 1; m <= 20; ++m) {
      days1 = helper.daysUntilStartOfMonth(m);
      days2 = helper.daysBeforeFirstOfMonth(m);
      if (days1 != days2) {
        out.println("Error on month " + m);
        out.println("  The old algorithm computed: " + days1);
        out.println("  The new algorithm computed: " + days2);
      } // if
    } // for
*/

Recompile and execute DateTester to ensure that we haven't introduced any errors.

Step 8. Create a variant of daysBeforeFirstOfMonth that also takes a SimpleOutput object as a parameter. Have that method print out information about the method. Here is an example

  /**
   * Determine the number of days before the start of month m.
   * Print out information on the computation.
   */
  public int daysBeforeFirstOfMonth(int m, SimpleOutput out) {
    int days = 0;
    out.println("Computing the number of days in month " + m);
    // Base case: it's January.  There are no days before January 1.
    if (m == 1) {
       days = 0;
    } // January
    // Every other month
    else {
       days = daysBeforeFirstOfMonth(m-1,out) + 
              daysInMonth(m-1);
    } // A month that's not January 
    out.println("There are " + days + " days in month " + m);
    return days;
  } // daysBeforeFirstOfMonth(int,SimpleOutput)

Update DateTester to compute the number of days in June using daysBeforeFirstOfMonth. Recompile the two classes and execute DateTester. Record your output. What does this output suggest?

Step 9. We've tested month values that are too large. What about month values that are too small? Add the following line to DateTester.

    out.println(daysBeforeFirstOfMonth(0, out));

Recompile and and execute DateTester. What happens? What does this suggest?

After you've answered the question, you may want to look at the notes on this step.

Step 10. As the previous step suggests, when you write recursive methods, testing special cases is particularly important. In daysBeforeFirstOfMonth, we should test the special cases of months that fall before month 1 and months that fall after month 12. What value should we return in those cases? We could return a special value, such as -1. We could also thrown an exception. (Exceptions are discussed in an optional lab.)

Add the following code to the beginning of both versions of daysBeforeFirstOfMonth.

    // Check for valid month.  Return -1 for invalid months.
   
    if ((m < 1) || (m > 12)) {
      return -1;
    } // invalid month

Recompile SimpleDate and execute DateTester. What happens when the month is 6? What happens when the month is 0?

Step 11. Which of the two methods (daysBeforeFirstOfMonth and daysUntilStartOfMonth) do you prefer? Why?

Experiment A1.2: Factorial

Required file:

• RecursiveExamples.java

Step 1. Make a copy of RecursiveExamples.java. Create a new program, RecursiveExperiments.java with a main method that contains the following lines.

    SimpleOutput out = new SimpleOutput();
    RecursiveExamples helper = new RecursiveExamples();
    out.println("5! = " + helper.factorial(5));

Compile the classes and execute RecursiveExamples. Record the output. Is the output correct?

Step 2. Update the main method of RecursiveExperiments to compute the factorial of 0. Recompile and execute RecursiveExperiments. Record the output. Is the output correct?

Step 3. Update the main method of RecursiveExperiments to compute the factorial of -1. Recompile and execute RecursiveExperiments. What happens? Explain.

Step 4. Here is a new version of factorial that gives an indication of what is happening.

  /**
   * Compute n!.
   */
  public int factorial(int n, SimpleOutput out) {
    int result;
    out.println("Computing the factorial of " + n);
    // Base case: The factorial of 0 is 1.
    if (n == 0) {
      result = 1;
    } // base case
    // Recursive case: The factorial of n is n*n-1.
    else {
      result = n * factorial(n-1);
    } // recursive case
    out.println("The factorial of " + n + " is " + result);
    return result;
  } // factorial(int)

Add this method to RecursiveExamples and update RecursiveExperiments to use this method. Recompile the two classes and execute RecursiveExperiments. What happens? Explain.

Step 5. Update the two versions of factorial so that they return negative one when given a negative parameter. Summarize the changes you've made here.

Experiment A1.3: Fibonacci numbers

Required files:

• RecursiveExamples.java
• RecursiveExperiments.java

Before you begin, if you have not already done so, make a copy of RecursiveExamples.java. If you have not already created RecursiveExperiments.java, make a copy of a sample version.

Step 1. Reread the code for fib and fibit, both of which can be found in RecursiveExamples.java. Which do you prefer? Why?

Step 2. Update RecursiveExperiments to use fib and fibit to determine the values of the sixth, tenth, twentieth, and fortieth Fibonacci numbers. Enter those values here.

Step 3. It is useful to compare the two methods of computing Fibonacci numbers by counting the number of steps they execute. In the recursive method, we will count the number of recursive calls. In the iterative method, we will count the number of times the loop repeats. How do we do this? By adding a steps field to the RecursiveExamples class and updating it appropriately.

Update RecursiveExamples to include the following lines

  /**
   * A count of the number of steps used by some algorithms.
   */
  protected int steps;

  /**
   * Reset the count of steps to 0.
   */
  public void resetSteps() {
    steps = 0;
  } // resetSteps()

  /**
   * Determine the number of steps used since the last call to
   * resetSteps().
   */
  public int getSteps() {
    return steps;
  } // getSteps()

Next, add the following lines to the beginning of fib and to the beginning of the loop in fibit.

  // Update the count of steps
  ++steps;

Finally, add the following lines to the main method of RecursiveExperiments.

    helper.resetSteps();
    out.println("fib(3) = " + helper.fib(3));
    out.println("  that computation took " + 
                helper.getSteps() + " steps.");
    helper.resetSteps();
    out.println("fibit(3) = " + helper.fibit(3));
    out.println("  that computation took " + 
                helper.getSteps() + " steps.");

Recompile the two classes and execute RecursiveExperiments. Record the output.

Step 4. How many steps do you think it will take fib to compute the sixth Fibonacci number? How many steps do you think it will take fibit to compute the sixth Fibonacci number?

Step 5. Update, recompile, and execute RecursiveExperiments so that you can get precise answers to the questions of the previous step. Record the answers. What do these numbers suggest?

Step 6. Make a copy of fib and extend it to print information on the computation. Your new version should resemble

  /** 
   * Compute the nth Fibonacci number.  
   * Print notes on the computation.
   */
  public int fib(int n,
                 SimpleOutput out) {
    int result; // The value we compute
    out.println("Computing fib of " + n);
    // Base case: n is 1 or 2
    if ((n == 1) || (n == 2)) {
      result = 1;
    } // base case
    // Recursive case
    else {
      result = fib(n-1,out) + fib(n-2,out);
    } // recursive case
    out.println("Fibonacci number " + n + " is " + result);
    return result;
  } // fib(int,SimpleOutput)

Update the main method of RecursiveExperiments to compute the sixth Fibonacci number using this new version of fib. Summarize the output. What does this output suggest?

Step 7. How many times is the first Fibonacci number computed during the recursive computation of the sixth Fibonacci number?

Step 8. How many times do you think the first Fibonacci number will be computed during the recursive computation of the tenth Fibonacci number?

Step 9. Update the main method of RecursiveExperiments to answer the previous question. What answer did you get?

Step 10. In this and the next step, you'll consider a different issue relating to the two computations. You should use the original version of fib. Add the following code to the main method of RecursiveExperiments.

    out.println("fib(1) = " +
                helper.fib(1));
    out.println("fibit(1) = " +
                helper.fibit(1));

Recompile and execute RecursiveExperiments. Record and explain what happens.

Step 11. Add the following code to the main method of RecursiveExperiments.

    out.println("fib(0) = " +
                helper.fib(0));
    out.println("fibit(0) = " +
                helper.fibit(0));

Recompile and execute RecursiveExperiments. Record what happens.

After recording the results, you may want to refer to the notes on this subject.

Experiment A1.4: Exponentiation

Required files:

• RecursiveExamples.java
• RecursiveExperiments.java

Before you begin, if you have not already done so, make a copy of RecursiveExamples.java. If you have not already created RecursiveExperiments.java, make a copy of a sample version.

Step 1. Using both recExp and itExp determine the value of 2¹⁰ and 1.05²⁰. Are the answers the same or different?

Step 2. Which version of the exponentiation function do you prefer, and why?

Post-Laboratory Problems

Problem A1-A: Printing information on recursive calls, revisited

In Experiment A1.1, you created a method that printed out information on each recursive call. Unfortunately, the information was somewhat hard to read as it was all left justified. Write a recursive version of factorial that indents before recursive calls. For example, if we asked for the factorial of 5, this function would print something like

Computing the factorial of 5
  Computing the factorial of 4
    Computing the factorial of 3
      Computing the factorial of 2
        Computing the factorial of 1
          Computing the factorial of 0
          The factorial of 0 is 1
        The factorial of 1 is 1
      The factorial of 2 is 2
    The factorial of 3 is 6
  The factorial of 4 is 24
The factorial of 5 is 120

Problem A1-B: How large can a factorial be?

You may have noticed that the factorial function grows surprisingly fast. Because of this, if you try to compute the factorial of larger numbers, you may generate a number larger than the computer can represent. Determine the largest factorial our method can correctly compute.

Update factorial so that it returns negative one when one attempts to compute a factorial larger than it can compute.

Problem A1-C: Large Fibonacci numbers

You may have noticed that the Fibonacci sequence also grows surprisingly fast. Because of this, if you try to compute the nth Fibonacci number for larger values of n, you may generate a number larger than the computer can represent. Determine the largest n for which our methods correctly compute the nth Fibonacci number.

Problem A1-D: More efficient iterative computation of Fibonacci numbers

One problem with the iterative Fibonacci method is that it uses an array. If we are computing a large Fibonacci number, we may use a significant amount of memory for the array. It turns out that we don't need to use all that memory. Since each Fibonacci number is only based on the previous two Fibonacci numbers, we only need to keep track of three numbers.

Rewrite the iterative Fibonacci method so that it does not use an array. The following is some code to get you started.

  /**
   * Compute the nth Fibonacci number iteratively.
   */
  public int newfibit(int n) {
    int i;       // A counter
    int current; // The ith Fibonacci number
    int prevnum; // The (i-1)st Fibonacci number
    int nextnum; // The (i+1)st Fibonacci number

    // Initialize
    i = 1;
    current = 1; // The 1st Fibonacci number is 1
    prevnum = 0; // If fib(2) is 1, fib(1) is 1, and 
                 //   fib(2) is fib(1) + fib(0), then fib(0) is 0.
    ...
    nextnum = prevnum + current;
    ...
  } // newfibit(int)

Problem A1-E: More efficient recursive computation of the Fibonacci numbers

It is also possible to efficiently compute the nth Fibonacci number recursively. Rather than counting down from n, we will count up from 2. In each recursive call, we can pass in the two previous Fibonacci numbers. Here are a pair of method to do just that.

  /**
   * Compute the nth Fibonacci number recursively.  Return
   * -1 for n <= 0.
   */
  public int fibrec(int n) {
    // Check for invalid input
    if (n <= 0) {
       return -1;
    } // invalid input
    else {
      return fibrec(n,1,1,0);
    } // normal input
  } // fibrec(int)

  /**
   * Compute the nth Fibonacci number, given the ith and (i-1)st
   * Fibonacci numbers.
   * 
   * This does not do the validity testing that fibrec(int) does
   * because it should only be called from fibrec(int).
   */
  protected int fibrec(int n, int i, int ith, int prev) {
    // Base case: we already have the nth Fibonacci number.
    if (n == i) {
      return ith;
    } // base case
    // Recursive case: move on to the (i+1)st Fibonacci number.
    else {
      return fibrec(n, i+1, ith+prev, ith);
    } // recursive case
  } // fibrec(int,int,int,int)

Add those methods to RecursiveExamples and confirm that they work correctly. Update them to count the number of steps (method calls) used to compute the nth Fibonacci number. How many steps are required to compute the sixth Fibonacci number? The tenth?

In your own words, explain how this method works.

Problem A1-F: Understanding the Fibonacci numbers

Believe it or not, but there are reasons we study the Fibonacci numbers other than their use in illustrating recursion. By doing research in the library or elsewhere, determine other reasons that the Fibonacci numbers are valuable.

Problem A1-G: Counting steps during exponentiation

In Experiment A1.3, we counted the number of steps in two methods that computed the Fibonacci numbers. Using a similar strategy, count the number of steps in two versions of the exponentiation function. Try computing 1.05 to the tenth power, to the twentieth power, and to the fiftieth.

Problem A1-H: From recursion to iteration

We have seen that it is sometimes possible to turn recursive methods into iterative methods. (In fact, it should always be possible to turn a recursive method into an equivalent iterative method and an iterative method into an equivalent recursive method.) Rewrite the efficient recursive exponentiation method iteratively.

Notes

Experiment A1.1, Step 2. If the logic was correct for both of our methods, there should be no new output from the loop. If there is, then there is either a serious logical problem in our design or a small typo in the program (or both). Look for the latter.

Experiment A1.1, Step 3. There should be no output. If our logic was correct, the two methods should still produce identical results.

Experiment A1.1, Step 9. When we call the method with 0 as a parameter, it checks whether the month is 1. It isn't, so it calls itself with 0-1 = -1 as a parameter. Negative one isn't 1, so it calls itself with -1-1 = -2 as a parameter. This isn't 0 so ... the method keeps calling itself again and again and again. Since you should never reach 1 by repeatedly subtracting 1 from 0, the method will run forever.

Experiment A1.3, Step 4. You may have noted that fib takes significantly more steps and also more time than fibit. Why is this? Because the recursive version repeats a lot of work. For example, to compute the fifth Fibonacci number, it must compute the fourth Fibonacci number and the third Fibonacci number. To compute the fourth Fibonacci number, it must compute the third Fibonacci number and the second Fibonacci number. Hence, the third Fibonacci number is computed at least twice. The second computation should be unnecessary.

Experiment A1.3, Step 11. It is likely that the program ran forever when you tried to compute the zeroth Fibonacci number recursively. Why? Because the base case was for values of 1 and 2. If we start with a number less than 1, we will keep subtracting 1 or 2, never reaching the base cases.