COMP1406/1006  Design and Implementation of Computer Applications  Winter 2006 
5 Recursion 
Here are the individual topics found in this set of notes (click on one to go there):
5.1 What is Recursion ? 
So, recursion is all about:
In fact, its actually easier than this sounds. Most of the time, we simply take the original problem and break/bite off a small piece that we can work with. We simply keep biting off the small pieces of the problem, solve them, and then merge the results. 
It is important to remember
the following very important facts about the subproblems:

In fact, when writing the code, we usually start with the base cases
since they are the ones that we know how to handle. For
example, if we think of our "real world" examples mentioned earlier,
here are the base cases:

Tips for Designing
Recursive Methods:

5.2 Recursion With
Primitives 
5! = 5*4*3*2*1
4! = 4*3*2*1
3! = 3*2*1
2! = 2*1
1! = 1
0! = 1
The operation is defined nonrecursively as follows:
1
if N = 1
N! =
N x (N1) x (N2) x ... 3 x 2 x
1 if N > 1
We can easily write a factorial()
method that takes an integer and
computes the factorial using loops.
// A
nonrecursive method for computing the factorial
public static int factorial(int
num) {
int result
= 1;
for (int
i=2; i<=num; i++)
result *= i;
return result;
}
So how do we write the code ? Its
easy. You start with the base case. Then use
the formula to break down the problem:
public static int
factorial(int
n) {
if
(n == 1) // BASE CASE
return
1;
return n * factorial(n  1);
// RECURSIVE STEP
}
Wow! That's a simpler solution than
the nonrecursive version. Did you notice how the method
actually calls itself ?
Recursive methods actually work just like your "normal everyday" methods. There is nothing tricky. In essence, each time a message is sent, a new "copy" of the method runs on a new copy of the parameters. The local variables of one method invocation are not visible to another invocation.
Consider tracing the recursive execution of "2 factorial":
Commandline arguments:
public class FactorialTest {Did you notice how we can check the length of the args array to ensure that there is at least one argument ? We then accessed that argument by accessing the String array args at its first position (which is the first parameter, which was the number 5 we entered). Be aware though that the value comes in as a String, so we have to parse it into the desired type.public static int factorial(int n) {
if (n == 1) // BASE CASE
return 1;
return n * factorial(n  1); // RECURSIVE STEP
}public static void main(String[] args) {
//First check to see that there is at least one command line argument
if (args.length == 0) {
System.out.println("Usage: FactorialTest anInteger");
System.exit(1);
}
int theInteger = Integer.parseInt(args[0]);if (theInteger < 0) {
System.out.println("Factorial of a negative int is not defined");
System.exit(1);
}
else
System.out.println("Factorial of " + theInteger + " is " + factorial(theInteger));
}
}
Consider a
second recursion example that computes
how much money per month a person would have to pay to pay back a
mortgage on his/her home. Consider the following notation:

5.3 Recursion With
Objects (NonDestructive) 
As you may
know, strings in JAVA are not mutatable
(that is, you cannot actually modify a string once it is
made). We
will look at a method that takes a string and then returns a new string
which has the same characters as the original, but in reverse order: public static
String reverse(String
s) { 
We start by considering the base case. What strings are
the easiest ones to solve this problem for ? Well, a string
with 1 or 0 characters is easy, since there is no reversing to
do. So there you have it. Those are the base
cases:
if (s.length()
== 1)
return s;
if (s.length()
== 0)
return s;
We can simplify this to one line:
if (s.length() <= 1) return s;
Now, how do we express the problem recursively ?
Remember ... think of a smaller problem of the same type. A
smaller problem would be a smaller string. So what if we
take a piece of the string and then solve for the smaller string
? That is the way we should approach it. What
piece should we take off ? Perhaps the first
character. We can use:
to get the smaller string which is the original without the first
character.
OK. Now what do we do ? Remember, we need to
express the solution to original problem in terms of the smaller
problem. So we should be thinking the following question:
"If I have the reverse of the smaller string, how can I use that to
determine the reverse of the whole string ?". Lets look at
an example:
"STRING" reversed is "GNIRTS". If we use consider the
shorter string "TRING" and reverse it to "GNIRT", then how can we use
this reversed shorter string "GNIRT" to obtain the solution "GNIRTS" to
the original problem ? You can see that all we have to do
is append the "S" to the smaller string solution "GNIRT" to get the
complete solution "GNIRTS". So,
Now we should know how to write the code:
public static String reverse(String s) {
if
(s.length() <= 1) return s;
return reverse(s.substring(1,
s.length())) + s.charAt(0);
}
As you can see the solution is quite simple ... after we see the solution of course
;).
public class ReverseTest {
public
static String reverse(String s) {
if
(s.length()
<= 1) return s;
return reverse(s.substring(1, s.length())) +
s.charAt(0);
}
Example (Palindromes):
Consider the simple problem of
determining
whether or not a String is a palindrome. A palindrome is
a String which reads the same forwards
as backwards:
How do we write a method using a for loop to detect whether or not a String is a palindrome ? Well ... how do we do it without a computer ? 
Here is how we may write code to do this:
public static boolean isPalindrome(String s) {Now what about solving this recursively ?
for (int i=0; i<=(s.length()1)/2; i++) {
if (s.charAt(i) != s.charAt(s.length()  i  1))
return false;
}
return true;
}
We must be able to express the palindrome problem in terms of
smaller
palindrome problems.
Here is the recursive formulation of the problem:
For example, in our palindrome problem, when only 1 character remains in the String, or in the case where the String is empty, we don't need to divide any further and so these are the base cases for our problem. Often, the base cases also correspond similarly with errorchecking (e.g., like checking for an empty string first). So ... the base case is used to "stop" the recursive process.
Here are some palindrome examples that show when the base case is reached.
isPalindrome("level")
> isPalindrome("eve")
> isPalindrome("v")
> true
isPalindrome("poop") > isPalindrome("oo") > isPalindrome("") > true
isPalindrome("abcdba") >
isPalindrome("bcdb") >
isPalindrome("cd") > false
So how do we write the code for this problem recursively ? Think of the stopping conditions and write pseudo code:
public class StringUtilities {Here is another way to write it:public static boolean isPalindrome(String s) {
//BASE CASE (1 or 0 character cases combined together here)
if (s.length() <= 1)
return true;//BASE CASE (first and last characters do not match)
if (s.charAt(0) != s.charAt(s.length()  1) )
return false;
//RECURSIVE STEP (check if middle portion is a palindrome)
return isPalindrome(s.substring(1, (s.length()  1)));
}
}
public static boolean isPalindrome(String s) {Now we must write a test application. Here is some testing code written in a different class:
return ((s.length() <= 1) 
((s.charAt(0) == s.charAt(s.length()  1)) &&
(isPalindrome(s.substring(1, (s.length()  1))))));
}
if
(StringUtilities.isPalindrome(input))
System.out.println(input + " is a palindrome ");
else
System.out.println(input + " is NOT a palindrome
" );
}
}
5.4 Recursion With Objects (Destructive) 
In the case where the object is temporarily destroyed during the computation and then restored at the end, this is considered to be NonDestructive. For instance, we may temporarily remove the jelly beans from the jar to count them and then put them back in when done. From the outsiders point of view, the jar arrangement has not been destroyed. We do realize however that the order of the jelly beans has been altered. If the order was important, then this process is considered destructive, as we are destroying the ordering.
Another approach that is common is to take the
original object, make a copy and then write a destructive
method on the copy. This is kind of like "cheating" but it does
solve the problem, of course
with the added running time overhead of copying the original object
beforehand. This often leads to the need to write more than one
method (i.e., use helper methods) to solve the problem. We will
see later
that this brings up the notion of indirect recursion.
The notion of writing destructive or nondestructive methods is not
something specific to recursion. In fact, you have already
written some destructive AND nondestructive methods in
COMP1405/1005.
Example (Summing Elements in an ArrayList)
Assume that we have an
ArrayList of Integer
objects. Consider writing a function that sums the integers
in the ArrayList: public static int
sum(ArrayList<Integer>
anArrayList) {
int sum=0; for(Integer x: anArrayList) sum += x; return sum; } 
As you can see, we simply go through the elements one by one and
compute the total:
What about doing it recursively ? How
do we define the problem recursively ?
We can do this as follows:
Nevertheless, let us examine how this is done. First, we consider the recursion by finding the simple base cases:
public static int
sum(ArrayList<Integer>
arrayList) { //RECURSIVE STEP 
But wait. Think about what happens as we empty elements from the ArrayList and head towards the base case. Do we really need that second base case ? The answer is NO since one more step of the recursive case will bring us to the first base case. Hence, we can simplify the code by removing the second base case:
public static int sum(ArrayList<Integer>
arrayList) {
if
(arrayList.isEmpty()) return
0;
Integer
element =
arrayList.get(0);
arrayList.remove(element);
return
element.intValue() + sum(arrayList);
}
This hardly seems more efficient than the nonrecursive version!! As mentioned before, some problems are not meant to be done recursively. We are simply examining them recursively for practice in order to help us understand recursion.
In some cases, the recursive solution is simpler. Consider summing Integer objects that are in a Stack:
public static int sum(Stack<Integer> s) {Is this destructive ? Yes!
int sum=0;
while(!s.isEmpty())
sum += s.pop();
return sum;
}
Here is the code:
public static int sum(Stack<Integer>
s) {
if (s.isEmpty())
return 0;
return
s.pop() + sum(s);
}
It is roughly the same amount of
code.
But now, what if we wanted to write these methods nondestructively ?
We need to put the items back onto the Stack so that
the Stack is restored.
Here is the nonrecursive, nondestructive version:
public static int sum(Stack<Integer> s) {Notice that we had to write code to keep track of the items that we removed so that we could put them back later. We used another Stack to keep this information, but we could have used any kind of collection.
int sum=0;
Stack<Integer> tempStack = new Stack<Integer>();
while(!s.isEmpty()) {
Integer item = s.pop();
sum += item;
tempStack.push(item); // Keep backup of popped items
}
//Restore the original Stack
while(!tempStack.isEmpty()) {
s.push(tempStack.pop());
}
return sum;
}
Now what about the nondestructive recursive version ?
public static int sum(Stack<Integer>
s) {
if (s.isEmpty())
return 0;
Integer element =
s.pop(); // temporarily
destroy stack
int answer =
element + sum(s); // get recursive sum
s.push(element);
// restore after the recursion
return answer;
}
Hey! It is much simpler. We don't need extra
variables. We simply restore the popped item on the way
back from the recursion. This is an example of temporarily
destroying the object in order to get
an answer and then "undo"ing the destroying on the way back from the
recursion. It is considered a nondestructive method.
So we can see that the recursive solution is more elegant.
Example (Counting):
Consider
counting the elements in some kind of
collection. Perhaps we want to only count elements that satisfy
some condition. In this example, we count the odd integers in an
ArrayList. We
will do it first destructively, and then
alter our code to make it nondestructive. Destructively, we can simply take off one element from the ArrayList each time through the recursion. We simply look at the number that we take out and add one to the total each time it is found to be odd. 
Here is the destructive version inside a text
class:
int result = 0; if (element%2 == 0) result = countOdd(nums); else result = 1 + countOdd(nums); // Add the element back to the collection before returning nums.add(0, element); return result; 
5.5 Direct vs. Indirect Recursion 
We use the term "indirect"
recursion to describe a method
which itself is not recursive, but which calls a directly recursive
method to
compute its solution. The isPalindrome() method
that we
wrote is considered directly recursive as it calls itself
recursively.
Example (Summing Integers in an Array) Let us look again at the example of summing integers, but this time using an array of ints. We cannot remove from the array as we did with the ArrayLists and Stacks in the previous section of the notes. We must take a different, nondestructive, approach. How would we do this nonrecursively ? public static int
sum(int[]
theArray) { 
How can we do this recursively ? At each step of the recursion, we will need to know which number we are adding, so we will also need an index. Where do we put this index ? It MUST be a parameter to the method so that this position needs to be carried through the recursive iterations:
private static int sum(int[] theArray, int n) {
//BASE
CASE: sum(theArray,0) = a[0]
if (n == 0) return
theArray[0];
//RECURSIVE
STEP: sum(theArray,n) = theArray[n] + sum(theArray,n1)
return
(theArray[n] + sum(theArray,n1));
}
Notice that this method adds the elements in reverse order. That is different from the nonrecursive method. It is more natural this way since we continually reduce the value of n until we reach the base case of n == 0. Note that we did not do any error checking. What if n is greater than the array length ?
We do have one annoying problem now ... we have
to
supply an additional parameter.
To avoid this problem, we will make another method
that will be called by the user in place of this one. This new
method
will provide the parameter for us:
public static int sum(int[] theArray) {
return (sum(theArray,
theArray.length  1);
}
Can we have these two methods with the same name ? Yes ... since they have a different signature (i.e., parameter list). Recall that this is known as overloading.
Now to test it we merely call this new method. In fact, we should make the original method private. This technique of making a kind of "wrapper" for the recursive method is known as indirect recursion. The first method is directly recursive but this second one is called indirectly recursive since it does not call itself, but does call a recursive method. This second method is commonly called a helper method.
It should be a simple task for you to take the ArrayList method that we wrote earlier and make it nondestructive. Make sure you can do this. Here is the code altogether:
//Example of summing elements of Arrays
and Arr using recursive and
overloaded
sum methods.
import java.io.*;
import java.util.*;
public class SumTest
{
//This destructive method
returns the sum of a vector of Integers
public static
int sum(ArrayList<Integer> arrayList) {
//BASE CASE
if (arrayList.isEmpty()) return 0;
//RECURSIVE STEP
Integer element =
arrayList.get(0);
arrayList.remove(element);
return (element.intValue() +
sum(arrayList));
}
//This is a helper
method
private static int sum(int[]
theArray, int n) {
if (n == 0) return
theArray[0];
return
(theArray[n] + sum(theArray,n1));
}
//This method returns
the sum of an array of Integers .
public static int sum(int[] anArray) {
return (sum(anArray,
anArray.length1));
}
public static void main(String[] args) throws IOException {
int MAX = 100,
i=0, count=0, temp=0;
int[] a = new
int[MAX];
ArrayList<Integer>
arrayList = new ArrayList<Integer>();
System.out.println("Enter the first integer (0 to end, Max=100):");
//Add
first number to array and vector
temp = new Scanner(System.in).nextInt();
a[i] = temp;
arrayList.add(new
Integer(temp));
//read
numbers into array and vector
while ((a[i] !=
0) && (i < MAX)) {
i++;
count++;
System.out.println("Enter another integer (0 to
end):");
temp = new Scanner(System.in).nextInt();
a[i]
= temp;
arrayList.add(new Integer(temp));
}
System.out.println("Here are the results:");
System.out.println("Array Sum = " + sum(a));
System.out.println("ArrayList Sum = " + sum(arrayList));
}
}
Example
(Reversing a
StringBuffer): Consider our earlier example in which we reversed the characters of a String. We could replace the String with a StringBuffer and then change our method so that the actual characters of the original StringBuffer would be reversed. This would be considered a destructive method since it modifies the original object parameters. Take notice of the method overloading and the use of a private helper method. 
Our strategy will be to swap the first and last characters of the StringBuffer and then move inwards on the StringBuffer the same way we iterated through the String in our palindrome example. To do this, we will not shrink the StringBuffer each time. Instead, we will keep track of where we are by using indices as we traverse recursively. We will write the following method which will reverse the characters of the given StringBuffer within the indices specified by i and j:
//RECURSIVE
STEP
char temp =
s.charAt(leftIndex);
s.setCharAt(leftIndex,
s.charAt(rightIndex));
s.setCharAt(rightIndex,
temp);
reverseBetween(s, leftIndex+1, rightIndex1);
}
//Reverse the contents
of
StringBuffer s
public static void reverse(StringBuffer s) {
if (s.length()
> 1)
reverseBetween(s, 0, s.length()1);
}
//Reverse the contents
of
StringBuffer s
public static void reverse(StringBuffer s) { ...
}
private
static void reverseBetween(StringBuffer
s, int leftIndex, int rightIndex)
{ ... }
public static void main(String[] args) {
//First
check to see that there is at least one command line argument
if (args.length
== 0) {
System.out.println("Usage: DReverseTest
aString");
System.exit(1);
}
StringBuffer input = new
StringBuffer(args[0]);
System.out.println("string buffer's initial contents: " + input);
reverse(input); //Notice that we call the public method
System.out.println("string buffer's final contents: "
+ input);
}
}
5.6 Some More Examples 
Example
(Averaging):
Consider finding the average of a set of Integers that are stored in an ArrayList. One approach is to use the sum method just mentioned and merely divide by the number of elements: public
static double avg(ArrayList<Integer>
v) { 
What about the base cases ?
avg(A, 0) = 0Now we can easily write the code:
avg(A, 1) = A_{1}
avg(A, n) = [((n1) * avg(A, n1) + A_{n} ] / n
import java.io.*;
import java.util.*;
public class AvgTest
{
//This method returns the
average of a n Integers in the given vector .
private static double avg(ArrayList<Integer>
a, int n) {
//BASE
CASES:
if (n > a.size()) return 1;
if (n == 0) return
0;
Integer last = a.get(a.size()  1);
if (n == 1) return
last;
//RECURSIVE
STEP
a.remove(last);
return (((n1) *
avg(a, n1) +
last)/n);
}
//This method returns
the average of an ArrayList of Integers
public static double avg(ArrayList<Integer> a) {
return (avg(a, a.size()));
}
Do we really need this extra index ? Can we rewrite this method using direct recursion ? Well the index of n represents the size of the array, which changes as the recursion progresses. So we have to be careful:
private static double avg(ArrayList<Integer> a) {Notice the use of the size variable to that when the ArrayList size changes due to the recursion, this local variable stays constant. We can rearrange the order of the calculations in the expression if we want to eliminate this extra size variable. We just have to make sure that the size is used BEFORE the recursive call:
if (a.isEmpty()) return 0;Integer last = a.get(a.size()  1);
if (a.size() == 1)
return last;a.remove(last);
int size = a.size();
return (size * avg(a) + last)/(size+1);
}
private static double avg(ArrayList<Integer> a) {Of course, we can play games like this all day long :). We can actually eliminate the 2nd base case, since it is handled by the recursive call:
if (vec.isEmpty()) return 0;Integer last = a.get(a.size()  1);
if (a.size() == 1)
return last;vec.remove(last);
return (1/(a.size()+1.0))*(a.size() * avg(a) + last);
}
private static double avg(ArrayList<Integer> a) {Also, we can get rid of the last variable by rearranging the expression again:
if (a.isEmpty()) return 0;Integer last = a.get(a.size()  1);
a.remove(last);
return (1/(a.size()+1.0))*(a.size() * avg(a) + last);
}
private static double avg(ArrayList<Integer> a) {But WHY would you write such a complicated looking expression ??? It is better to leave the last variable as it was for ease of reading the code.
if (a.isEmpty()) return 0;
return (1.0/(a.size()))*(a.remove(0) + a.size() * avg(a));
}
Example
(Selecting):
Now, what if we wanted to not just count
the odd
integers in an ArrayList, but
to gather and return them (i.e., select them)
? That is, make a new ArrayList
that will contain all of the odd
integers from the original
ArrayList. Can we do this with direct recursion ? Perhaps
we
should
make a helper method. We can take the approach that is common to
everyday life. Get a blank list ready, and write down all
the odd integers in it. In terms of coding, we can prepare
the blank "list" as an initially empty ArrayList passed in as a
parameter. We can then add to this list as we go through
the recursion. Hence we will need to pass this list along when we
do the recursive calls. 
public class SelectTest {
//This destructive method returns the odd Integers in
an ArrayList
public static
ArrayList<Integer>
selectOdd(ArrayList<Integer> a) {
return
(selectOdd(a,
new ArrayList<Integer>()));
}
//This is the helper method that does all of the work
public static
ArrayList<Integer> selectOdd(ArrayList<Integer> a, ArrayList<Integer>
result) {
//BASE CASE:
if (a.isEmpty()) return result;
//RECURSIVE STEP
Integer element = a.get(0);
a.remove(element);
if (element%2 != 0)
result.add(element);
return selectOdd(a,
result);
}
public static void main(String[] args) {
int input
= 0;
ArrayList<Integer> nums = new ArrayList<Integer>();
do {
System.out.println("Enter integers one at a time (0 to
end):");
if ((input
= new Scanner(System.in).nextInt())
!= 0)
nums.add(input);
} while (input != 0);
ArrayList<Integer> result = selectOdd(nums);
System.out.println("Here
are the odd
integers:");
for (int i=0; i<result.size(); i++) {
System.out.println(result.get(i));
}
}
}
Can you write this method using direct recursion (i.e., no additional parameters) ?
public static
ArrayList<Integer> selectOdd(ArrayList<Integer>
a) {
if (a.isEmpty())
return
new ArrayList<Integer>();
Integer element = a.get(0);
a.remove(element);
result = selectOdd(a);
if (element%2 != 0)
result.add(element);
return result;
}
Do the odd numbers come back in the same order as before ? Think about it.
What about making it nondestructive now:
public static
ArrayList<Integer> selectOdd(ArrayList<Integer>
a) {
if (a.isEmpty()) return new ArrayList<Integer>();
Integer element = a.get(0); //remove from end now
a.remove(element);
result = selectOdd(a);
a.add(element); //restore after
recursive
call by adding to end
if (element%2 != 0)
result.add(element);
return result;
}
Example
(Choosing k items from N):
Denote the number of ways of choosing k items out of N by
C(N,k). We can
determine what
this number is by doing an experiment and counting.
That is, C(N,k) =
C(N1,k1) + C(N1,k)

//Computing C(n,k) example. (use:
java ChooseTest n k)
public class ChooseTest {
//returns C(n,k)
public static int choose(int n, int k) {
//BASE CASES:
if (n == k) return
1; //C(n,n) = 1
if (k == 0) return
1; //C(n,0) = 1
if (k > n) return
0; //C(n,k) = 0
//RECURSIVE
CASES: C(N,k) = C(N1,k1) + C(N1,k)
return (choose(n1,k1) + choose(n1,k));
}
public static void main(String[] args) {
//First
check to see that there is at least one command line argument
if (args.length
< 2) {
System.out.println("Usage: ChooseTest n k");
System.exit(1);
}
int n =
Integer.parseInt(args[0]);
int k =
Integer.parseInt(args[1]);
System.out.println("C(" + n + "," +
k + ")= " + choose(n,k));
}
}
Example
(Counting boxes
within boxes):
Consider the following scenario. You wrap up your friends graduation gift in a box...but to be funny, you decide to wrap that box in a box and that one in yet another box. Also, to fool him/her you throw additional wrapped boxes inside the main box. The boxeswithinboxes scenario is recursive. Consider this problem now. We have boxes that are completely contained within other boxes and we would like to count how many boxes are completely contained within any given box. Here is an example where the outer box has 29 internal boxes:

Assume that there are some classes that implement the following Box interface:
public interface Box
{
public ArrayList<Box> internalBoxes(); //Returns
the boxes within the receiver box
public boolean isEmpty();
//Return whether or not there are any boxes
within
the receiver box
public void
addBox(Box
aBox); //Add the given
box to the receiver
public void
removeBox(Box
aBox); //Remove the given box from the
receiver
}
Now we have no idea how the boxes are stored or maintained.
All
we know is how to use the interface.
How can we write a recursive method to find the total number of boxes
with a given box ?
int count = 0;
ArrayList<Box> innerBoxes =
aBox.internalBoxes();
// Go through each
internal box and get count
// their internal boxes
recursively
for (Box b: innerBoxes) {
count += countBoxes(b);
}
// Return the count of
all internal boxes' boxes plus the number
// of internal boxes at
this level of the recursion
return (count + innerBoxes.size());
}
=
Here is the code:
Box anInnerBox =
aBox.internalBoxes().get(0);
aBox.removeBox(anInnerBox);
return (countBoxes(aBox)
+ countBoxes(anInnerBox)
+ 1);
}
Example
(Height of a Tree):
Consider a class called BinaryTree that keeps a collection of nodes. The topmost node is the root of the tree. Each node stores an item of some kind and keeps pointers to a left and right child. The children are themselves trees and are considered subtrees of the original tree. If a node has no left or right child, then null is stored there. A node with no children at all is considered a leaf. 
A basic implementation of a binary tree may look like this:
public class TreeNode {
private TreeNode rightChild,
leftChild;
private Object
item; // set to whatever the node
represents
public TreeNode(Object
anObject) {
this(anObject, null,
null);
}
public TreeNode(Object
anObject, TreeNode aLeftChild, TreeNode aRightChild) {
item = anObject;
rightChild = aRightChild;
leftChild = aLeftChild;
}
public final TreeNode rightChild() {
return
rightChild;
}
public final TreeNode leftChild() {
return leftChild;
}
public final void setRightChild(TreeNode child) {
rightChild = child;
}
public final void setLeftChild(TreeNode child) {
leftChild = child;
}
}
Notice that we called the class TreeNode. In fact, every node in the tree is a tree itself. It is actually a recursive data structure.
Here is an example of how to build the tree above:
public static void main(String
args[]) {
TreeNode root;
root = new TreeNode("A",
new TreeNode("B",
new TreeNode("D"),
new TreeNode("E",
new TreeNode("H"),
new TreeNode("I"))),
new TreeNode("C",
new TreeNode("F"),
new TreeNode("G",
new TreeNode("J"),
null)));
}
The height of a tree is the number
of nodes encountered along the longest path from (but not including)
the root to a leaf of the tree.
The tree above has a height of 3. Can you
write a recursive method that determines the height of a binary tree ?
5.7 Efficiency with Recursion 
1 if n = 0fib(n) = 1 if n = 1fib(n1) + fib(n2) if n > 1
Notice in the above computation some problems (e.g. fibonacci(2) ) are being solved more than once, even though we presumably know the answer after doing it the first time. The following iterative solution avoids this. (It can also be avoided with a properly formulated recursive solution)
public int finonacci(int n) {
if (n < 0)
return
1;
int first = 1;
int second = 1;
int third = 1;
for (i=2;
i<=n; i++) {
third = first + second; //compute new value
first = second; second = third; //shift the
others
to the right
}
return third;
}
Try designing an efficient recursive Fibonacci method. You may
use indirect recursion.
Here are some points to remember about efficiency:
5.8 Practice Questions 
Try writing recursive methods for the following problems:
A good exercise would be to build a SortedCollection class from scratch and use a binary search to implement its contains(Object) method (such as is implemented for class Vector).
The task is to move the disks from peg A to peg B using peg C as an intermediary (if necessary).
Move (1 disk from A to B using C) => JUST DO IT
Move (2 disks from A to B
using
C) =>
Move 1 A disk to C
Move 1 A disk to B
Move 1 C disk to B
Move (3 disks from A to B
using
C) =>
Move 2 A disks to C using B (use previous step)
Move 1 A disk to B
Move 2 C disk to B using A
...
Move (n disks from A to B
using
C) =>
Move n1 A disks to C using B
Move 1 A disk to B
Move n1 C disk to B using A
Implement a TowersOfHanoi application
which
will allow the user to specify some number of disks on one peg and then
select which other peg they should be moved to. The application
must them go
about moving the disks over following the rules above. This is a
good
application to animate on a graphical user interface.