import java.util.ArrayList;

public class RecEGs{

	/**
	 * Recursive computation of n choose k
	 * @param n >= 0
	 * @param k <= n
	 * @return the number of possible combinations of
	 * k out of n
	 */
	public long combRec(long n, long k){
		// Spock can only visit k out of n planets, so he must choose...
		// pre: 0 <= k <= n
		// post:  return the number of possible combinations of
		// k out of n
		if (n==k || k==0) return 1;  // there is only one way
		else // n>k and k>0
			// Take planet n. Spock can either ...
			return combRec(n-1,k-1)  // visit n and then he must choose k-1 more out of n-1
				   + 
				   combRec(n-1,k);   // or not, then he must choose k more out of n-1
	}

	/*
	 * Fast Spock
	 */
	public long combFast(int n, int k, long[][] A) {
		long r;
		if (n==k || k==0) {
			A[n][k]=1;
			return 1;
		}
		else if (A[n][k] == 0) {
			r = combFast(n-1,k-1,A) + combFast(n-1,k,A);
			A[n][k] = r;
			return r;
		}
		else {
			r = A[n][k];
			return r;
		}
	}
 
	
    /**
     * 
     * @param n>0 size of the parking lot
     * @return the number of ways we can park:
     *   Explorers: size 2
     *   Civics:  size 1
     *   in a parking lot of size n
     *    
     */
	public long parkingLot (int n){
		if (n == 1) return 1;       // a Civic
		else if (n == 2) return 2;  // an Explorer or two Civics
		else return parkingLot(n-2)  // An Explorer in last position
	        	  + parkingLot(n-1); // A Civic in last position
	}
	

	/**
	 * 
	 * @param n>0: size of parking lot
	 * @param A: array of solved parking lot problems
	 * @return the number of ways we can park:
     *   Explorers: size 2
     *   Civics:  size 1
     *   in a parking lot of size n
	 */
	public long parkingLot (int n, long [] A) {

		if (A[n] == 0) { // you haven't already solved this subproblem
			// two base cases
			if (n == 1) A[n] = 1;       // C
			else if (n == 2) A[n] = 2;  // E or CC
			else {
				A[n] = parkingLot(n-2,A)  // Explorer in last position
				     + parkingLot(n-1,A); // Civic in last position
			}
		}
		return A[n];
	}

		



	/*
	 * Recursively generate all bit patterns of length n
	 * @param subsets - an ArrayList that accumulates the bit patterns
	 * @param n - length of the bit patterns to be generated
	 * precondition:  n >= 1, subsets contains bit patterns of length n-1
	 * postcondition:  subsets contains all bit patterns of length n
	 */
	void recursiveBitPatterns(ArrayList<String> subsets, int n){
		if (n == 1) {
			subsets.add("0");
			subsets.add("1");
			return;
		}
		recursiveBitPatterns(subsets, n - 1);
		int size = subsets.size();
		for (int i = 0; i<size; i++){
			String s = subsets.get(i);
			subsets.set(i, "0"+ s);
			subsets.add("1" + s);
		}
	}

	public void doSpock(int n) {
		if(n>0) {
			long[][] A = new long[n+1][n+1];
			long start, finish, res;
			for(int k = 0; k<=n; k++){ 
					
				start = System.currentTimeMillis();
				res = combFast(n, k, A);
				finish = System.currentTimeMillis();
				System.out.println("Number of combinations (fast): (" +
						n + " choose " +k+ ")  =  " + res + " time = " + (finish-start) + "  milliseconds");
			
				start = System.currentTimeMillis();
				res = combRec(n, k);
				finish = System.currentTimeMillis();
				System.out.println("Number of combinations (slow): (" +
						n + " choose " +k+ ")  =  " + res + ", time = " + (finish-start) + "  milliseconds\n");
			}
		}
	}
	
	
	public int gcdIt(int m, int n) {
		m = Math.abs(m); n = Math.abs(n);
		int r = m % n; 
		while (r != 0) {
		  m = n;
		  n = r;
		  r = m % n;
		}
		// When r is 0, n is the greatest divisor
		return n;
	}
	
    public int gcdRc(int m, int n) {
    	if (m%n == 0)
    		return n;
    	else 
    		return gcdRc(n,m%n);
    }
	
	/**
	 * @param args: input file name
	 * @throws FileNotFoundException 
	 */
	public static void main(String[] args) {
			
		RecEGs r = new RecEGs();		
		
		/*
		for(int i=1;i<=40;i++){
			System.out.println("slow parkingLot(" +i+ "): " + r.parkingLot(i));
		}  
		*/
		
		/*
		for(int i=1;i<=65;i++){
			long[] lot = new long[i+1];
			System.out.println("fast parkingLot(" +i+ "): " + r.parkingLot(i,lot));
		}  
		*/
		
		/*
		
		ArrayList<String> patterns = new ArrayList<String>();
		r.recursiveBitPatterns(patterns, 4);
		System.out.println("number of bit patterns of 4 bits: " + patterns.size());
		for(int i = 0; i < patterns.size(); i++)
			System.out.println(patterns.get(i));

        */
		
		// r.doSpock(32);
		
		System.out.println("gcdIt(14,35): " + r.gcdIt(14,35) );
		System.out.println("gcdIt(35,14): " + r.gcdIt(35,14) );	
		System.out.println("gcdIt(57,38): " + r.gcdIt(57,38) );
		System.out.println();
		System.out.println("gcdRc(14,35): " + r.gcdRc(14,35) );
		System.out.println("gcdRc(35,14): " + r.gcdRc(35,14) );	
		System.out.println("gcdRc(57,38): " + r.gcdRc(57,38) );	
	}

}