Recursion Exercises

   < Previous  
  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 long gcd( long a, long b ){
        System.out.println( "gcd("+a+","+b+")");

        if( b == 0 ){
            // base case
            return a;
        }else{
            long returnValue = gcd( b, a % b );
            return returnValue;
        }
    }
  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:
    1. What is the value returned for each of the following method calls (Show the recursive method calls that are generated)?
      1. recursiveFunctionB( 7, 2);
      2. recursiveFunctionB( 29, 5);
      3. recursiveFunctionB( 5, 7);
    2. 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?
  5. Raising a number to a power, for example 35 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:
  6. Apply the four questions for constructing recursive solutions:
    1. Write a recursive function to print out the contents of a String backwards
    2. 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.
  7. Tower of Hanoi (Game)
    • 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
    1. Describe a recursive algorithm for moving all of the discs from tower 1 to tower 3.
    2. Implement your solution. Consider completing the following: TowerOfHanoi.java .
  8. n choose k (binomial coefficients):
    For any set containing n elements, the number of distinct k-element subsets.
    Definition of n-choose-k
    and
    Definition of n-choose-k
    Consider completing the following: NChooseK.java.
  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 makeChange( 10 ) by hand!