CIS 121 April 17, 2000

Let us review the concept of recursion.

Recall that a very powerful feature of programming languages is recursion, the ability of a method to call itself. However, to understand recursion, one must first understand recursion.

There are three features of a well-formed recursive method.
  1. It calls itself (directly or indirectly).
  2. It has exit criteria by which it does something without making the recursive call.
  3. It works with a "smaller" problem or value each time that it is called so that it can make progress towards the exit criteria!
We looked at the following examples.

Factorial

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.

The Fibonacci Sequence

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
We can easily implement an array to give n terms in the Fibonacci Sequence. 

public class Fibonacci {
   private int number;
   private int[] sequence;

   public Fibonacci(int n) {
      number = n;
      sequence = new int[n+1];
   }

   public void fibonacci() {
      sequence[0]=1;
      sequence[1]=1;
      for (int i=2;i<=number;i++) {
         sequence[i] = sequence[i-1] + sequence[i-2];
      }
      for (int i=0;i<=number;i++)
         System.out.println(sequence[i]);
   }

   public static void main(String[] args) {
      Fibonacci myFibonacci = new Fibonacci(5);

      myFibonacci.fibonacci();
   }
}
You may download the Source Code.

It is also natural to display the terms in this sequence using recursion since the sequence has a recursive definition. 
public class FibonacciSequence {
   int number;

   public FibonacciSequence(int n) {
      number = n;
   }

   public int fibonacci(int num) {
      if ((num==0) || (num==1))
         return(1);
      else
         return(fibonacci(num-1) + fibonacci(num-2));
   }

   public void displaySequence() {
      for (int i=0;i<=number;i++)
         System.out.println(String.valueOf(fibonacci(i)));
   }

   public static void main(String[] args) {
      FibonacciSequence myFibonacciSequence = new FibonacciSequence(5);

      myFibonacciSequence.displaySequence();
   }
}
You may download the Source Code.

Power

We can calculate the integer power of an integer using methods we have already used. Here is an example of a program to find the integer power of an integer. 
public class Power {
   int number;
   int exponent;
   int power;

   public Power(int n,int exponent) {
      number = n;
      this.exponent = exponent;
   }

   public String toString() {
      int power = number;

      for (int i=1;i<=exponent-1;i++)
         power *= number;

      return(String.valueOf(power));
   }

   public static void main(String[] args) {
      Power myPower = new Power(5,2);

      System.out.println(myPower);
   }
}
You may download the Source Code.

We can also implement it recursively. 
public class RecursivePower {
   int number;
   int exponent;
   int power;

   public RecursivePower(int n,int exponent) {
      number = n;
      this.exponent = exponent;
   }

   public int power(int exp) {
      if (exp==1)
         return(number);
      else
         return(number*power(exp-1));
   }

   public String toString() {
      return(String.valueOf(power(exponent)));
   }

   public static void main(String[] args) {
      RecursivePower myRecursivePower = new RecursivePower(5,2);

      System.out.println(myRecursivePower);
   }
}
You may download the Source Code.

Writing a String backwards

We can also recursively write a string backwards. 
public class WriteBackwards {
   String inputString;

   public WriteBackwards(String s) {
      inputString = s;
   }

   public void writeBackwards(String s,int index) {
      if (index>=0) {
         System.out.println(s.charAt(index));
         writeBackwards(s,index-1);
      }
   }

   public void display() {
      writeBackwards(inputString,inputString.length()-1);
   }

   public static void main(String[] args) {
      WriteBackwards myWriteBackwards = new WriteBackwards("galois");

      myWriteBackwards.display();
   }
}
You may download the Source Code.

Make sure that you are able to reproduce the above peices of code. You will be required to produce any of these recursive methods on the exam. Do not worry about the regular approach. Make sure you remember how each recursive method works.

Complexity of Algorithms, A Measure of Efficiency

An important aspect of developing algorithms is how efficient that algorithm is. That is, even though are many different ways of solving a problem correctly, not all of these methods require the same amount of time. Developing more efficient algorithms to solve various problems is a task that many computer scientists undertake.

Definition: Suppose f and g are functions from N to N+, that is the domain of the functions is the nonnegative integers, and the range of the functions is the positive integers. Then f = O(g), read f is big O of g, if and only if there exists a positive real number c and a positive integer M such that f(x) <= g(x) for all x >= M.

Theorem: If f = O(g), and g = O(h), then f = O(h).

Proof: Since f = O(g), there exists c1 > 0 and M1 > 0 such that f(x) <= c1g(x) for all x >= M1.

Since g = O(h), there exists c2 >= 0 and M2 > 0 such that g(x) <= c2h(x) for all x >= M2.

Let M = max{M1,M2}. If x >= M, then f(x) <= c1g(x) <= c1c2h(x).

Therefore, by definition, f = O(h).

Theorem: If f = O(cg), where c is a positive constant, then f = O(g).

Proof: Since f = O(cg), there exists c1 > 0 and M1 > 0 such that if x >= M1, then f(x) <= c1cg(x).

Therefore, by definition, f = O(g).

Recall that if a and b are bases of logarithms, then loga n and logb n are related by a constant multiple. Therefore when we talk about O(loga N) or O(logb N), we may omit the base.

The reason for stating these two theorems is to show that O is not a relationship unique to two functions. O is similar to an ordering. It establishes an upper bound on how long an algorithm will take to complete. However, there are infinitely many upper bounds for any function. In real variable mathematics, there is a key concept known as completeness. When dealing with one real variable, this concept takes the following form.

The Completeness Axiom: Every nonempty set of real numbers bounded above has a least upper bound.

When we speak of the complexity of an algorithm what we are searching for is something similar to a least upper bound.

O(1)

An operation which takes constant time to complete such as adding two elements in an array.

O(log N) 
public class BinarySearch {
   int[] array;

   public BinarySearch(int[] array) {
      this.array = array;
   }

   public int binary(int key,int first,int last) {
      if (first > last) 
         return(array.length);
      else {
         int index = (first+last)/2;
         if (array[index]==key)
            return(index);
         else if (array[index]>key) 
            return(binary(key,first,index-1));
         else
            return(binary(key,index+1,last));
      }
   }

   public int search(int key) {
      return(binary(key,0,array.length-1));
   }

   public static void main(String[] args) {
      int[] array = {5,7,10,13,18,20,21};

      BinarySearch myBinarySearch = new BinarySearch(array);

      System.out.println(myBinarySearch.search(5));
      System.out.println(myBinarySearch.search(21));
   }
}   

0
6
  • BinarySearch.java Notice here how the complexit is O(log N).

    We assume the array is sorted. Each time the bineary method is executed, we are halving the length of the original portion of the array in which we were searching. Therefore, the lengths of the portion of the array in which we are searching in the binary method is 

    N N/2 N/4 ... 1
    What we need to determine is how many steps it will take on average to find the key we are looking for. If we take the logarithms of these lengths, then we can easily see how many steps it will take. 
    log2N log2N-1 ... 0
    Therefore, it will take log2N+1 steps on average to find what we are looking for so the algorithm is O(log N).

    O(N) 
    public class LinearSearch {
   int[] array;

   public LinearSearch(int[] array) {
      this.array = array;
   }

   public int search(int key) {
      int index = array.length;
      
      for (int i=0;i<=array.length-1;i++)
         if (array[i]==key)
            index=i;

      return(index);
   }

   public static void main(String[] args) {
      int[] array = {5,7,10,13,18,20,21};

      LinearSearch myLinearSearch = new LinearSearch(array);

      System.out.println(myLinearSearch.search(5));
      System.out.println(myLinearSearch.search(21));
   }
}   

    0
6
  • LinearSearch.java

    O(N log N) 
    public class QuickSort {
   int[] array;

   public QuickSort(int[] array) {
      this.array = array;
   }

   public void swap(int i,int j) {
      int temporary = array[i];

      array[i] = array[j];
      array[j] = temporary;
   }

   public int partition(int first,int last) {
      int pivot = array[first];
      int lo = first;
      int hi = last;

      while (lo <= hi) {
         while ((lo <= last) && (array[lo] <= pivot)) lo++;

         while (array[hi] > pivot) hi--;

         if (lo < hi) {
            swap(lo,hi);
            lo++;
            hi--;
         }
      }
   
      swap(first,hi);
      return hi;
   }

   public void quicksort(int first,int last) {
      int pivotIndex;

      if (first < last) {
         pivotIndex = partition(first,last);

         quicksort(first,pivotIndex-1);
         quicksort(pivotIndex+1,last);
      }
   }

   public void sort() {
      quicksort(0,array.length-1);
   }

   public String toString() {
      String output = "";

      for (int i=0;i<=array.length-1;i++) {
         output += String.valueOf(array[i]);
         output += "\t";
      }

      return(output);
   }

   public static void main(String[] args) {
      int[] array = {18,7,21,5,13,10,20};

      QuickSort myQuickSort = new QuickSort(array);

      System.out.println(myQuickSort);

      myQuickSort.sort();

      System.out.println(myQuickSort);
   }
}

    18	7	21	5	13	10	20	
5	7	10	13	18	20	21
    To examine the complexity, consider the best case scenario: at each stage we split the remaining array into equal parts.

    Let N = 2m. Then the total number of comparisons will be 
    2m + 2(2m-1) + 22(2m-2) + ...
+ 2m-12 = 2Mm = N log2N.
  • QuickSort.java

    O(N2) 
    public class BubbleSort {
   int[] array;

   public BubbleSort(int[] array) {
      this.array = array;
   }

   public void swap(int i,int j) {
      int temporary = array[i];

      array[i] = array[j];
      array[j] = temporary;
   }

   public void sort() {
      int i;
      int j;

      for (i=0;i<=array.length-1;i++)
         for (j=i+1;j<=array.length-1;j++)
            if (array[j]<array[i])
               swap(i,j);

   }

   public String toString() {
      String output = "";

      for (int i=0;i<=array.length-1;i++) {
         output += String.valueOf(array[i]);
         output += "\t";
      }

      return(output);
   }

   public static void main(String[] args) {
      int[] array = {18,7,21,5,13,10,20};

      BubbleSort myBubbleSort = new BubbleSort(array);

      System.out.println(myBubbleSort);

      myBubbleSort.sort();
   
      System.out.println(myBubbleSort);
   }
}

    18	7	21	5	13	10	20	
5	7	10	13	18	20	21
  • BubbleSort.java