CSC 241- Set #5 (Starting October 22nd, 1997)


Recursion

Recursion is grounded in mathematical induction and is one of our most significant problem solving tools in computer science. We will discuss mathematical induction first through an example and we will then move into a discussion about recursion.

Although, your first experience here will be in using recursion for solving problems that you have previously solved iteratively, you must not lose sight of the fact that there are many problems that have a natural recursive solution. We will discuss the classic Tower of Honoi problem as an example with a naturally recursive solution. Tower of Honoi is not easy to solve without recursion.


Mathematical Induction

It seems to make sense to talk about induction proofs in mathematics before discussing recursion. Induction proofs are often used in proving theorems in mathematics especially those in number theory.

The basic idea here is that you have a base case for the theorem that is easyly provable and your main task is to prove that assuming that the theorem holds for the case n-1, it also holds for case n (usually, we assume the nth case and prove the (n+1)th case, but it is the same idea). Think about what that says--if I can prove that the theorem holds when n is 0, for instance, a nd can also prove that if it holds for case n-1, it also holds for case n, doesn't that mean that it holds when n is 1, then when n is 2, and then when n is 3, and so on ...? neat!

Here is an example:

I hope you have all heard of the theorem that says ...

	the sum of all positive integers up to N is equal to N(N+1)/2

Let us use induction proof to prove this theorem.  

Base Case:
	Base case here is when N is 1. Note that the sum of all positive 
	numbers from 1 to 1 is 1 and that 1(1+1)/2 is also 1. Done.

Inductive Step:
	Lets assume that 1 + 2 + ... + (N-1)  == (N-1)N/2
	Now, we will show that  1 + 2 + ... + (N-1) + N == N(N+1)/2

	To prove this, we add N to each side of == in the assumed case:
	 1 + 2 + ... + (N-1) + N  == (N-1)N/2 + N  ==>
	 1 + 2 + ... + (N-1) + N  == ((N-1)N + 2N)/2  ==>
	 1 + 2 + ... + (N-1) + N  == (N2 - N + 2N)/2 ==>
	 1 + 2 + ... + (N-1) + N  == (N2 + N)/2 ==>

	 1 + 2 + ... + (N-1) + N == N(N+1)/2	Done!

Examples of Recursion

In the examples that follow, you will find two things in common. They all have one or more base cases. Base cases are those with a simple answer and return that answer, thus starting the return path from the recursive calls. You will also notice that they all state a solution in terms of a simpler or smaller version of the problem and cause a recursive call to themselves at some point. Any time you see a method that calls itself you are dealing with recursion. If you don't see a base case, however, you are simply looking at an infinite loop that will eventually crash the program.


Lets write a recursive method that adds all positive integers from 1 to N and returns that result. To make things simple, lets assume that our parameter n won't be negative.

1	public static int sum (int n)
2   //precondition: n >= 0
3   //postcondition: return value == 0 + ... + N
4	{
5	   if (n == 0)	// base case
6   	  return 0;
7	   else
8	      return n + sum(n-1); // recursive case, notice the call to sum  for n-1
9	}

Lets call this method with sum(5) and trace its execution:


L#   Comment                 Statement/Method Header       n          Return Value
1                            public int sum (5)            5
8    1st recursive call      return 5 + Sum (4);
1                            public int sum (4)            4
8    2nd recursive call      return 4 + Sum (3);
1                            public int sum (3)            3
8    3rd recursive call      return 3 + Sum (2);
1                            public int sum (2)            2
8    4th recursive call      return 2 + Sum (1);
1                            public int sum (1)            1
8    4th recursive call      return 1 + Sum (0);
1                            public int sum (0)            0
6    Base Case (1st return)  return 0;                                      0
8    2nd return              return 1 + Sum (0);                            1
8    3rd return              return 2 + Sum (1);                            3
8    4th return              return 3 + Sum (2);                            6
8    5th return              return 4 + Sum (3);                           10
8    6th return (answer)     return 5 + Sum (4);                           15

Lets write a recursive method that looks for a particular character in a string. The String Class has a method indexOf. indexOf finds the index of a character in a string. If the character is not found in the string, the method returns a -1. Lets write a similar method, however, it won't be part of the String class, so it will need a string and a character parameters. We also don't care to know where the character is within the string, so our method will be boolean.

To write this method recursively, we need the following mind set: either the character is in the first location of the string or it is somewhere in the rest of the string. So, we will need to use the charAt method to get the character in cell zero and use the substring method to get the rest of the characters in the string. here is the code:

1	public static boolean findChar (String s, char c) {
2	   if (s == null) return false;         // base case
3	   if (s.charAt(0)==c) return true;     // base case
4	   return findChar(s.substring(1));     // recursive case, call using
5	}                                       // the substring starting at cell 1

Lets assume that test_s is a String and contains "abcde" and lets trace the execution of the following call: findChar(test_s,'c')


L#   Comment                 Statement/Method Header      s       c    Return Value
1                            pub...findChar("abcde",'c')  abcde   c 
4    1st recursive call      return findChar("bcde",'c') 
1                            pub...findChar("bcde",'c')   bcde    c 
4    2nd recursive call      return findChar("cde",'c') 
1                            pub...findChar("cde",'c')    cde     c 
3    Base Case (1st return)  return true                                 true
4    2nd return              return findChar("cde",'c')                  true
4    3rd return              return findChar("bcde",'c')                 true
4    4th return (answer)     return findChar("abcde",'c')                true

Finding Fibonacci numbers make for another good example of recursion. The first two numbers in the Fibonacci sequence are 1, from there on, they are the sum of the previous two. We are assuming that n is a positive integer. Here is the code:

1   public static int fib (int n) {
2      if ((n==1)||(n==2)) return 1;  // base case
3      return fib(n-1) + fib(n-2);    // note that two separate calls are made
4   }

Lets call this method with fib(5) and trace its execution. Since each time we execute return fib... two recursive calls are made, we will show the trace in the form of a tree and omit some of the details.


                                           fib(5)
                                         {return 5}

                  fib(4)                    +                     fib(3)
                {return 3}                                      {return 2}

        fib(3)       +       fib(2)                      fib(2)      +      fib(1)
      {return 2}            {return 1}                 {return 1}         {return 1} 

   fib(2)  +  fib(1)
 {return 1} {return 1}   

Tower of honoi

To some its a never ending game, to others its a good way to test the speed of their CPU, but, to us it is a great example of recursion.

In the original Tower of Honoi, you have 64 disks in position A stacked on top of each other. The largest disk at the bottom and smallest at the top and disks sorted from large to small. The task at hand is to move all 64 disks from position A to position B using position C, without ever putting a larger disk on top of a smaller one and only moving 1 disk at a time. How long do you think that would take you to complete? Chinese priest thought that the completion of this task will bring the end of the world, it was considered an unendable task. But, that was before the age high speed computers. How many moves do you think it takes to moves all 64 disks?

The recursive algorithm is extremely simple to state, note that the larger the number associated with a disk is, the larger the disk:


if (N == 1)
   Move disk N from position A to position B
else
   Move (N-1) disks from position A to position C using B
   Move disk N from position A to position B
   Move (N-1) disks from position C to position B using A
endif

Here is a method that prints all moves needed for N disks. To realize that time complexity of this method grows exponentially as n gets larger, you can copy the program that tests this method and try it for bigger Ns. The file is test_honoi.java You can use the Save As option in the File pull-down menu of netscape to save it in your account once the file is loaded in netscape.


public static void towerOfHonoi (int N, char from, char to, char using){
   if (N == 1)
      System.out.println("Move disk "+ N + " from position " + from + " to position " + to);
   else {
      Tower_Of_Honoi (N-1,from,using,to);
      System.out.println("Move disk "+ N + " from position " + from + " to position " + to);
      Tower_Of_Honoi (N-1,using,to,from);
   }
}

Here is the output from this function when moving 3 disks from A to B using C:


Enter the number to try: 3
Move disk 1 from position A to position B
Move disk 2 from position A to position C
Move disk 1 from position B to position C
Move disk 3 from position A to position B
Move disk 1 from position C to position A
Move disk 2 from position C to position B
Move disk 1 from position A to position B
**** MOVES COMPLETED ****