Recursion Exercises
++++++++++++++++++++++++++++++++++++++++++++

1. What does the acronym GNU mean?


2. Given the call gcd(20, 115), how many additional calls will be made to gcd()?
    /**
     * Euclidean algorithm for calculating the greatest common denominator (GCD) of two numbers.
     * @param a one of the two numbers
     * @param b one of the two numbers
     * @return the greatest common denominator of a and b (meaning the largest number that divides
     *         both a and b without a reminder)
     */
    public static long gcd( long a, long b ){
        System.out.println( "gcd("+a+","+b+")");

        if( b == 0 ){
            // base case
            return a;
        }else{
            return gcd( b, a % b );
        }
    }



3. Mystery Method: Given a recursive method like:

      public int recursiveFunctionA( int x, int y ){
          if( x == 0 || y == 0 ){
              return 0;
          }else{
              return x + recursiveFunctionA( y-1, x );
          }
      }
      
   We can trace this recursive method with something like the following. Below are some example calls:
   
      recursiveFunctionA(3, 2) returns  3 + recursiveFunctionA(1, 3)
        recursiveFunctionA(1, 3) returns  1 + recursiveFunctionA(2, 1)
          recursiveFunctionA(2, 1) returns  2 + recursiveFunctionA(0, 2)
            recursiveFunctionA(0, 2) returns  0
          recursiveFunctionA(2, 1) returns  2 + 0 = 2
        recursiveFunctionA(1, 3) returns  1 + 2 = 3
      recursiveFunctionA(3, 2) returns  3 + 3 = 6
      
      
      recursiveFunctionA(1, 4) returns  1 + recursiveFunctionA(3, 1)
        recursiveFunctionA(3, 1) returns  3 + recursiveFunctionA(0, 3)
          recursiveFunctionA(0, 3) returns  0
        recursiveFunctionA(3, 1) returns  3 + 0 = 3
      recursiveFunctionA(1, 4) returns  1 + 3 = 4
      
      
      recursiveFunctionA(3, 5) returns  3 + recursiveFunctionA(4, 3)
        recursiveFunctionA(4, 3) returns  4 + recursiveFunctionA(2, 4)
          recursiveFunctionA(2, 4) returns  2 + recursiveFunctionA(3, 2)
            recursiveFunctionA(3, 2) returns  6 (from above)
          recursiveFunctionA(2, 4) returns  2 + 6 = 8
        recursiveFunctionA(4, 3) returns  4 + 8 = 12
      recursiveFunctionA(3, 5) returns  3 + 12 = 15
      
      recursiveFunctionA(0, 9) returns  0
      
   It multiplies!
   
   Consider the following recursive method below:
   
      public int recursiveFunctionB( int a, int b ){
          if( a < b ){
              return 0;
          }else{
              return 1 + recursiveFunctionB( a - b, b );
          }
      }
      
   Answer the following two questions:
   
   A. What is the value returned for each of the following method calls (Show the recursive method calls that are generated)?
      I. recursiveFunctionB( 7, 2);


      II. recursiveFunctionB( 29, 5);


      III. recursiveFunctionB( 5, 7);


   B. In just a few words, state what the method is computing (assuming a > 0 and b > 0 for the initial call).



4. What are the four questions for constructing recursive solutions?
   *I. How can you break the problem down into a smaller problem?
   II. How does the recursive call diminish/lessens the problem?
   *III. What could be (what conditions) could serve as the base case?
   IV. Will it reach the base case?

5. Raising a number to a power, for example 3^5 is the same as 3*3*3*3*3. Apply the four questions for constructing recursive solutions to calculating a whole number raised to the power of another whole number:
   public long power( int base, int exp ){
        if( exp == 0 ){
	    return 1;
	}
 	return base * power( base, exp - 1);
   }

   I. How can you break the problem down into a smaller problem?
      3^5 = 3*(3^4)  -> base^exp = power(base, exp) = base * base^(exp-1) = base * power( base, exp - 1)
      3^4 = 3*(3^3)
      3^3 = 3*(3^2)
      3^2 = 3*(3^1)
      3^1 = 3*(3^0)
      3^0 = 1
      
   II. How does the recursive call diminish/lessens the problem?
       exp - 1
       
   III. What could be (what conditions) could serve as the base case?
        exp == 0, then return 1
	
   IV. Will it reach the base case?
       Yes (if exp is positive)
  

6. Apply the four questions for constructing recursive solutions:
   A. Write a recursive function to print out the contents of a String backwards

      Often, we'll have a public method to start the recursion and then a private method to execute the recursive calls.  For example:
      
          public void strBackwards( String s ){
              strBackwardsRecursive( String s, 0 );
          }

      I. How can you break the problem down into a smaller problem?
         desserts
	 Display the last letter of the string, then recursively display the rest of the string backwords
      
      II. How does the recursive call diminish/lessens the problem?
          The string to display is one shorter than the previous call's string length
	  
      III. What could be (what conditions) could serve as the base case?
           String is empty
	   s.length() == 1
	   
      IV. Will it reach the base case?
          Yes

          public void strBackwards( String s ){
	       System.out.println( s.charAt( s.length() - 1 ) );
	       strBackwards( s.substring(0, s.length() - 1) ); // s[0..n-1-1] where n is the number of characters in s
	  }


   B. Write a recursive binary search. Look at the middle element of an array.
      If the number you're searching for is larger than the middle element, search the upper half.
      If the number you're searching for is smaller than the middle element, search the lower half.
      Otherwise, the number is found.
      Consider completing the following: BinarySearch.java.


import java.util.Arrays;  // for Arrays.toString()

/**
 * Demonstration of the classic Binary Search
 * @author Hyrum D. Carroll
 * @version 0.1 (May 4, 2020)
 */
public class BinarySearch{

    /**
     * Binary search - recursively looks for an item in a sorted array by
     * reducing the search space to half the previous search space.
     * @param a SORTED array
     * @param item The search key
     * @return true is item is in a, false otherwise
     */
    public static boolean binarySearch( int[] a, int item ){




    }
    
    
    public static void main( String[] args ){
        int[] array1 = {0,1,2,3,4,6,8,9};
        int[] array2 = {0,0,1,2,3,3,4,6,8,9};

        int search = 3;
        int[] array = array1;
        boolean result = false;

        search = 3;
        array = array1;
        result = binarySearch( array, search );
        System.out.println( "binarySearch( array="+Arrays.toString(array)+", search="+search+" ) returns "+result);
        
        search = 7;
        array = array1;
        result = binarySearch( array, search );
        System.out.println( "binarySearch( array="+Arrays.toString(array)+", search="+search+" ) returns "+result);
        
        search = 3;
        array = array2;
        result = binarySearch( array, search );
        System.out.println( "binarySearch( array="+Arrays.toString(array)+", search="+search+" ) returns "+result);
    }
}



7. Tower of Hanoi (Interactive Game: http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm)
   Goal: Move all of the discs from tower 1 to tower 3
   Rules:
      You can only move 1 disc at a time
      Only smaller discs can go on top of larger discs
   A. Describe a recursive algorithm for moving all of the discs from tower 1 to tower 3.


   B. Implement your solution. Consider completing the following: TowerOfHanoi.java.

import java.util.Scanner;

/**
 * Demonstration of a solution to the classic Tower of Hanoi problem
 * @author Hyrum D. Carroll
 * @version 0.2 (May 4, 2020)
 */
public class TowerOfHanoi{

    public static void main( String[] args ){
        Scanner stdinScanner = new Scanner( System.in );
        int numDiscs = 0; // number of discs
        
        System.out.print( "Please enter the number of discs: " );
        numDiscs = stdinScanner.nextInt();
        String startingTower = "tower 1";
        String spareTower = "tower 2";
        String endingTower = "tower 3";
    










        
    }
}


8. n choose k (binomial coefficients):
   For any set containing n elements, the number of distinct k-element subsets.
      ( n )   ( n-1 )   ( n-1 )
      (   ) = (     ) + (     ) for 1 <= k <= n - 1				
      ( k )   ( k-1 )   (  k  )
   and
      ( n )   ( n )
      (   ) = (   ) = 1  for n >= 0 			   
      ( 0 )   ( n )
   Consider completing the following: NChooseK.java.

import java.util.Scanner;

/**
 * Demonstration of a solution to the N choose K problem (binomial coefficients).
 * <p>
      ( n )   ( n-1 )   ( n-1 )
      (   ) = (     ) + (     ) for 1 <= k <= n - 1
      ( k )   ( k-1 )   (  k  )

      ( n )   ( n )
      (   ) = (   ) = 1  for n >= 0 			   
      ( 0 )   ( n )
 * </p>
 * @author Hyrum D. Carroll
 * @version 0.2 (May 4, 2020)
 */
public class NChooseK{
    
    /**
     * Recursive solution to N choose K
     * @param n N
     * @param k K
     * @return The result of n choose k
    */
    public static int nChooseK( int n, int k ){
        int result = 0;
        








        return result;
            
    }
    
    public static void main( String[] args ){
        Scanner stdinScanner = new Scanner( System.in );
        int n = 0; 
        int k = 0;
        
        System.out.print( "Please enter n: " );
        n = stdinScanner.nextInt();
        
        System.out.print( "Please enter k: " );
        k = stdinScanner.nextInt();

        // check arguments
        if( k < 0 || k > n || n < 0 ){
            System.out.println("Invalid arguments: n: " + n + ", k: " + k);
            return;
        }
        
        System.out.println( n + " choose " + k + " = " + nChooseK( n, k ));
    }
}


9. Make Change: (OPTIONAL)
   Write a recursive implementation for makeChange() that counts the number of possible ways to make change for a given amount of money. Let's assume that we are only dealing with coins (and not concern ourselves with paper money). Ultimately, you want a method that takes the following argument:
      The number of cents, as an integer
   For example, makeChange( 100 ) asks how many ways there are to make change for a dollar, using pennies, nickels, dimes and quarters . The answer is 242.
   
   WARNING: This question is hard. Remember, it is optional. I want you to think about it because it is worth thinking about. Even if you don’t come up with an optimal answer, the process of thinking about it will be valuable.
   Note: If you get stuck, try the following: Solve makeChage( 10 ) by hand!