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.
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!
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 // Base cases
3 if (s == null || s.length()==0) return false; // if an empty list
4 if (s.charAt(0)==c) return true; // is it the 1st char
5 if (s.length()==1) return false; // if no more chars
6 // recursive step
7 return findChar(s.substring(1),c); //look for character in the rest
8 }
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'
7 1st recursive call return findChar("bcde",'c')
1 pub...findChar("bcde",'c') "bcde" 'c'
7 2nd recursive call return findChar("cde",'c')
1 pub...findChar("cde",'c') "cde" 'c'
4 Base Case (1st return) return true true
7 2nd return return findChar("cde",'c') true
7 3rd return (answer) return findChar("bcde",'c') true
Now, lets write a hybrid between our findChar above and the indexOf method for strings. This IndexOf method
will be recursive and would take the string s and character c as parameters.
This method will return -1 of the string the character is not found, otherwise,
it will return the index location of the character.
1 public static int IndexOf (String s, char c) {
2 // Base cases
3 if (s == null || s.length()==0) return -1; // if an empty list
4 if (s.charAt(0)==c) return 0; // is it the 1st char
5 if (s.length()==1) return -1; // if no more chars
6 // recursive step
7 //look for character in the rest
8 int locationInSubstring=IndexOf(s.substring(1),c);
9 return locationInSubstring == -1 ? -1 : locationInSubstring+1;
10 }
Lets assume that test_s is a String and contains "abcde" and lets
trace the execution of the following call: IndexOf(test_s,'c')
L# Comment Statement/Method Header s c Return Value
1 pub...IndexOf("abcde",'c') "abcde" 'c'
8 1st recursive call lo...g=IndexOf("bcde",'c')
1 pub...IndexOf("bcde",'c') "bcde" 'c'
8 2nd recursive call lo...g=IndexOf("cde",'c')
1 pub...IndexOf("cde",'c') "cde" 'c'
4 Base Case (1st return) return 0 0
8 locationInSubstring=0 lo...g=IndexOf("cde",'c')
9 2nd return return locationI... 1
8 locationInSubstring=1 lo...g=IndexOf("bcde",'c')
9 3rd return (answer) return locationI... 2
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}
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 ****