CIS 121 April 13, 2000

Recall that advising is almost over.

The ACM Banquet is April 22nd on the Battleship. Tickets are $25. For tickets talk to Dr. Langan or go to the ACM office, CSCB 105.

ACM Elections are Monday.

Yesterday we began to talk about the concept of recursion. This is a very important and powerful concept and today you will get a chance to experiment with its power. As the old saying goes, in order for you to understand recursion you must first understand recursion.

The important thing to consider when dealing with recursion is that there must be a way for the recursion to stop.

A very natural example of recursion is the mathematical factorial function.

Recall that n! is defined to be the product of all positive integers less than or equal to itself.

For example, 
2! = 2*1 = 2,
3! = 3*2*1 = 6,
4! = 4*3*2*1 = 24,
5! = 5*4*3*2*1 = 120
Notice that this function grows very fast, in fact it grows much faster than an exponential function.

We can implement this function very simply with a for loop. 
public class Fact {
   int n;
   int product;

   public Fact(int n) {
      this.n = n;
      product = 1;
   }

   public String toString() {
      for (int i=1;i<=n;i++)
         product *= i;
      return(n + "! = " + product);
   }

   public static void main(String[] args) {
      Fact myFact;

      myFact = new Fact(2);
      System.out.println(myFact);
      myFact = new Fact(3);
      System.out.println(myFact);
      myFact = new Fact(4);
      System.out.println(myFact);
      myFact = new Fact(5);
      System.out.println(myFact);

   }
}
You may download this Source Code to experiment with it.

The output of this program is the following. 

2! = 2
3! = 6
4! = 24
5! = 120
The factorial function can be defined in another way. Let n be a positive integer.

1) 1! = 1, and
2) n! = n*(n-1)! if n > 1.


It is clear that this definition produces the same results as the previous definition. 

2! = 2*1! = 2*1 = 2,
3! = 3*2! = 3*2 = 6,
4! = 4*3! = 4*6 = 24,
5! = 5*4! = 5*24 = 120
The second definition of n! is a recursive definition. Therefore the factorial of a positive integer can be computed recursively. Let us consider how this would work.

Recall that a method is recursive if it calls itself.

Consider a conversation between yourself and a method called factorial.

You: factorial, what is the value of 5!?

factorial: The value of 5! is 5 times the value of 4!.

You: factorial, what then is the value of 4!?

factorial: The value of 4! is 4 times the value of 3!.

You: factorial, we seem to be going in circles. What is the value of 3!?

factorial: Hey, I'm just doing what I'm told. The value of 3! is 3 times the value of 2!.

You: factorial, I'm really getting angry! What is the value of 2!?

factorial: Hey, don't blame me! The value of 2! is 2 times the value of 1!.

You: factorial, this is it! You better give me an answer! What is 1!?

factorial: Well, actually the value of 1! is 1.

You: Finally! So the value of 1! is 1.

factorial: That is correct.

factorial: Since the value of 2! is 2 times the value of 1!, and 1! is 1, 2! = 2.

You: Hey, cool!

factorial: Since the value of 3! is 3 times the value of 2!, and 2! is 2, 3! = 6.

You: Now we're getting somewhere!

factorial: Since the value of 4! is 4 times the value of 3!, and 3! is 6, 4! = 24.

You: Ok, now I get what you're doing! factorial: Since the value of 5! is 5 times the value of 4!, and 4! is 24, 5! = 120.

You: Thank you, factorial.

factorial: You're welcome.

Let us implement the recursive definition of n!. 
public class Factorial {
   private int n;
   private int product;

   public Factorial(int n) {
      this.n = n;
   }

   public int factorial(int num) {
      if (num == 1)
         return(1);
      else 
         return(num*factorial(num-1));
   }

   public String toString() {
      return(String.valueOf(factorial(n)));
   }

   public static void main(String[] args) {
      Factorial myFactorial;

      myFactorial = new Factorial(2);
      System.out.println(myFactorial);
      myFactorial = new Factorial(3);
      System.out.println(myFactorial);
      myFactorial = new Factorial(4);
      System.out.println(myFactorial);
      myFactorial = new Factorial(5);
      System.out.println(myFactorial);
   }
}
You may download the Source Code.

Notice the important method here is factorial.

Within this method, we carry out the important parts of the above conversation. When we make a call to this method and send it a positive integer greater than 1, the method calls itself and sends 1 less than the value. This continues until the integer sent to the method is 1.

Another important mathematical concept that is well-suited to recursion is the Fibonacci Sequence.

The Fibonacci Sequence, Fn, is defined as follows.
1) F0 = 1
2) F1 = 1
3) If n > 1, then Fn = Fn-1 + Fn-2


Study the example of the recursive method to evaluate the factorial of a number and try to write a recursive method to evaluate elements of the Fibonacci Sequence.