/* RecursiveMethods.java          Authors: Koffman & Wolz
 * Class methods in Figures 9.1-9.20
 */
import javax.swing.JOptionPane;
import java.util.Vector;

public class RecursiveMethods {

//   class methods
//   Figure 9.1
//   precondition : m and n are defined and n > 0.
//   postcondition: Returns m raised to the power n.
public static int power(int m, int n) {
	if (n <= 1)
		return m;                     // stopping case
	else
		return m * power(m, n-1);     // recursive step
}

//   	Figure 9.4
//	precondition : m and n are defined and both are > 0.
//	postcondition: Returns greatest common divisor of m & n.
public static int gcd(int m, int n) {
	if (m < n)
		return gcd(n, m);
	else if (m % n == 0)
		return n;
	else
		return gcd(n, m % n);
}

//   	Figure 9.5
//	precondition : n is defined and n > 0.
//	postcondition: Returns the nth Fibonacci number.
public static int fibonacci(int n) {
	if (n <= 2)
		return 1;
	else
		return fibonacci(n-2) + fibonacci(n-1);
}

//	Figure 9.6
// 	postcondition: displays characters in reverse
// 	  of the order in which they are entered.
public static void reverse() {
     	String nextStr =
       	JOptionPane.showInputDialog("Next character or *");
	char next = nextStr.charAt(0);
     	if (next != '*') {
		reverse();
		System.out.print(next);
	}
}

//	Figure 9.9
//	precondition : Array x is defined and n >= 1.
//	postcondition: Returns sum of first n elements of x.
public static int findSum(int[] x, int n) {
	if (n <= 1)
		return x[0];
	else
		return x[n-1] + findSum(x, n-1);
}

//	Figure 9.11
//	precondition: target, n, and array x are defined & n >= 0.
//	postcondition: Returns position of the last occurrence
//      of target in elements x[0] through x[n-1] 
//	  if target is found; otherwise, returns -1.
public static int search(int[] x, int target, int n) {
	if (n == 0)
		return -1;         // target not in empty array
	else if (x[n-1] == target)
		return n-1;        // found! - return location.
	else  //Search rest of array.
		return search(x, target, n-1);
}

//	Figure 9.13
//	precondition: target, n, and array x are defined & n >= 0.
//	postcondition: Returns position of the last occurrence
//      of target in elements x[0] through x[n-1] 
//	  if target is found; otherwise, returns -1.
public static int searchIt (int[] x, int target, int n) {
	for (int i = n-1; i >= 0; i--)      
		if (x[i] == target)
			return i;    // found! - return location.

	// assert: All elements examined & target not found.
	return -1;
}

//	Figure 9.14
//	precondition : Arrays x & y are defined and n > 0.
//	postcondition: Returns true if arrays x & y are equal;
//      otherwise, returns false.
public static boolean isEqual (int[] x, int[] y, int n) {
	if (x.length != y.length)
		return false;          // array sizes unequal
	else if (n == 1)
		return (x[0] == y[0]); // Compare 1-element arrays.
	else if (x[n-1] != y[n-1])
		return false;          // Found an unequal pair.
	else  // Compare rest of arrays.
		return isEqual(x, y, n-1); 
}

//	Figure 9.15
//	precondition: target, n, & vector v are defined & n >= 0.
//	postcondition: Returns position of its last occurrence
//      if target is found in vector v; otherwise, returns -1.
public static int searchVec(Vector v, Object target, int n) {
	if (n == 0)
		return -1;
	else if (v.elementAt(n-1).equals(target))
		return n-1;        // Found! - return location.
	else  // Search rest of vector.
		return searchVec(v, target, n-1);		                                  
}

//	Figure 9.16
//	precondition: target & string s are defined.
//	postcondition: Returns position of its last occurrence
//      if target is located in string s; otherwise, returns -1.
public static int searchStr(String s, char target) {
	int posLast = s.length() - 1; // index of last character

	if (posLast == -1)
		return -1;           // Empty string
	else if (s.charAt(posLast) == target)
		return posLast;      // Found - return location.
	else  // Search rest of string.
		return searchStr(s.substring(0, posLast), target);
}

//	Figure 9.17
//	precondition : string s is defined.
//	postcondition: Returns the reverse of string s.
public static String reverseStr(String s) {
	int posLast = s.length() - 1; // index of last character

	if (posLast == -1)
		return "";               // Return the empty string
	else
		return s.charAt(posLast) + 
		       reverseStr(s.substring(0, posLast));
}

//	Figure 9.20
//	precondition : The elements of table are sorted &
//      first and last are defined.
//    postcondition: If target is in the array, return its
//      position; otherwise, returns -1.
public static int binSearch (int[] table, 
                             int target,
                             int first,
                             int last) {
	int middle = (first + last) / 2; // middle of array

	if (first > last)            
		return -1;                  // unsuccessful search
	else if (target == table[middle])
		return middle;              // successful search
	else if (target < table[middle])
		return binSearch(table, target, first, middle-1);
	else  // search upper half of array 
		return binSearch(table, target, middle+1, last);
}

public static void main(String[] args) {

  // Test all the recursive methods.
  System.out.println(power(3, 4));
  System.out.println(gcd(12, 16));
  System.out.println(fibonacci(10));
  System.out.println(reverseStr("happy"));

  int x[] = {4, 5, 6};
  System.out.println(findSum(x, x.length));
  System.out.println(search(x, 5, x.length));
  System.out.println(search(x, 7, x.length));
  System.out.println(searchIt(x, 5, x.length));
  System.out.println(searchIt(x, 7, x.length));
  System.out.println(binSearch(x, 5, 0, x.length-1));
  System.out.println(binSearch(x, 7, 0, x.length-1));

  int y[] = {4, 5, 6};
  System.out.println(isEqual(x, y, x.length));
  y[2] = 7;
  System.out.println(isEqual(x, y, x.length));

  Vector v = new Vector();
  v.addElement("happy");
  v.addElement("lucky");
  System.out.println(searchVec(v, "lucky", v.size()));
  System.out.println(searchVec(v, "Lucky", v.size()));
}
}