public class Recursion {
	
	public static void main(String[] args) {
	
		// Call all the various different recursive methods to test them out.	
		System.out.println("Answer is "+rec1(3,5));
		System.out.println("2^5 = "+power(2,5));
		System.out.println("1+2+..+100 "+sum(100));
		printChart(.15, 20, 40);
		Towers(4, 3, 2);
		
		int[] array = new int[50];
		for (int i=0; i<50; i++)
			array[i] = 5*i;
		for (int i=20; i<40; i++) {
			if (binSearch(array, 0, array.length, i))
				System.out.println("Found "+i);
			else
				System.out.println(i+ "is NOT in the array");
		}
	}
	
	
	// This was just used for a tracing question. It doesn't really
	// do anything meaningful but calculate (n+1)m
	public static int rec1(int n, int m) {
		if (n == 0)
			return m;
		else if (m == 0)
			return n;
		else return m +rec1(n-1, m);
	}
	
	// Calculates base raised to the exp power, exp must be non-negative.
	public static double power(double base, int exp) {
		
		if (exp == 0)
			return 1;
		else
			return base*power(base, exp-1);
	}
	
	
	// Calculates 1+2+3+...+n
	public static int sum(int n) {
		
		if (n == 0)
			return 0;
		else
			return sum(n-1)+n;
	}
	
	// Prints a tip chart with a tip rate of rate, starting with
	// a dollar value of low and ending with a dollar value of high
	public static void printChart(double rate, int low, int high) {
		
		if (low <= high) {
		
			System.out.println(low+"\t"+low*rate);
			printChart(rate, low+1, high);
		}
	}
	
	// Prints the moves necessary to solve the Towers of Hanoi problem
	// for n disks being moved from tower start to tower end. The towers
	// are numbered 1, 2 and 3.
	public static void Towers(int n, int start, int end) {
		
		if (n > 0) {
			
			int middle = 6 - start - end;
			Towers(n-1, start, middle);
			System.out.println("Move disk "+n+" from tower "+start+" to tower "+end);
			Towers(n-1, middle, end);
		}
	}
	
	// Determines whether or not target is store in the array vals in between
	// index low and index high.
	public static boolean binSearch(int[] vals, int low, int high, int target) {
		
		if (low > high)
			return false;
			
		int mid = (low+high)/2;
		
		if (target > vals[mid])
			return binSearch(vals, mid+1, high, target);
		else if (target < vals[mid])
			return binSearch(vals, low, mid-1, target);
		else
			return true;
	}
}