We'll say that a "pair" in a string is two instances of a char separated by a char. So

"AxA" the A's make a pair. Pair's can overlap, so "AxAxA" contains 3 pairs -- 2 for A and

1 for x. Recursively compute the number of pairs in the given string.

Question 4: Whats the base case for this problem?

Question 5: How many recursive cases are there for this problem? Explain.

Write your algorithm in Java. Create a main program to ask for the initial string and

make the first call to your method.