11.7. Exercises¶

A recursive method contains a call to itself. The recursion stops when a base case test is true and a value is returned.

11-7-1: Click on the line or lines that contain the test for the base caseWhen a base case test is true a value is returned and the recursion stops

public static int mystery(int n)
{
    if (n == 0)
        return 1;
    else
        return 2 * mystery (n - 1);
}

11-7-2: Click on the line or lines that contain the test for the base caseWhen a base case test is true a value is returned and the recursion stops

public static int bunnyEars(int bunnies)
{
    if (bunnies == 0) return 0;
    else if (bunnies == 1) return 2;
    else return 2 + bunnyEars(bunnies - 1);
}

11-7-3: Click on the line or lines that contain the test for the base caseWhen a base case test is true a value is returned and the recursion stops

public static void mystery (int x) {
    System.out.print(x % 10);
    if ((x / 10) != 0) {
        mystery(x / 10);
    }
    System.out.print(x % 10);
}

11-7-4: Click on the line or lines that contain the test for the base caseWhen a base case test is true a value is returned and the recursion stops

public static int mystery(String str)
{
    if (str.length() == 1) return 0;
    else
    {
        if (str.substring(0,1).equals("y")) return 1 +
                           mystery(str.substring(1));
         else return mystery(str.substring(1));
      }
   }

11.7.1. Easier Multiple Choice Questions¶

11-7-5: Which line has the recursive call?

public static int factorial(int n)
{
   if (n == 0)
      return 1;
   else return n * factorial(n-1);
}

1
This is the method declaration. Look for a call to the same method in the body of the method.
3
This is a conditional, not a method call.
4
This is a return statement, not a method call.
5
This line contains a call to the same method which makes this method recursive.

11-7-6: Which line has the recursive call?

public String starString(int n)
{
   if (n == 0) {
      return "*";
   } else {
      return starString(n - 1) + starString(n - 1);
   }
}

1
This is the method declaration. Look for a call to the same method in the body of the method.
3
This is a conditional, not a method call.
4
This is a return statement, not a method call.
5
This is an else which is part of a conditional, not a method call.
6
This line contains a call to the same method which makes this method recursive.

11-7-7: How many recursive calls does the following method contain?

public static int fibonacci(int n)
{
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else return fibonacci(n-1) + fibonacci(n-2);
    }

0
Look at line 7 more closely.
1
Many recursive methods only have one recursive call. But, this one has two.
2
Line 7 has two calls to fibonacci.
3
There are not 3 calls to fibonacci.

11-7-8: How many recursive calls does the following method contain?

public static int multiplyEvens(int n)
{
   if (n == 1) {
      return 2;
   } else {
      return 2 * n * multiplyEvens(n - 1);
   }
}

0
Look for a call to the same method in the body of the method.
1
Line 6 has one call to multiplyEvens.
2
Where do you see 2 calls to multiplyEvens?
3
Where do you see 3 calls to multiplyEvens?

11.7.2. Medium Multiple Choice Questions¶

11-7-9: Given the following method declaration, which of the following is printed as the result of the call mystery(1234)?

//precondition:  x >=0
public static void mystery (int x)
{
   System.out.print(x % 10);

   if ((x / 10) != 0)
   {
      mystery(x / 10);
   }
   System.out.print(x % 10);
}

1441
The first call to mystery with the integer 1234 will print 1234 % 10. The '%' means modulo or remainder. The remainder of 1234 divided by 10 is 4 so the first thing printed must be 4.
43211234
This has a recursive call which means that the method calls itself when (x / 10) is greater than or equal to zero. Each time the method is called it prints the remainder of the passed value divided by 10 and then calls the method again with the result of the integer division of the passed number by 10 (which throws away the decimal part). After the recursion stops by (x / 10) == 0 the method will print the remainder of the passed value divided by 10 again.
3443
The first call to mystery with the integer 1234 will print 1234 % 10. The '%' means modulo or remainder. The remainder of 1234 divided by 10 is 4 so the first thing printed must be 4.
12344321
The first call to mystery with the integer 1234 will print 1234 % 10. The '%' means modulo or remainder. The remainder of 1234 divided by 10 is 4 so the first thing printed must be 4.
Many digits are printed due to infinite recursion.
When the recursive call to mystery(1) occurs (the 4th call to mystery), the division of x /10 equals .01--this becomes 0 because this is integer division and the remainder is thrown away. Therefore the current call will be completed and all of the previous calls to mystery will be completed.

You can step through the code using the Java Visualizer by clicking on the following link: Q-11-7-1.

11-7-10: Given the following method declaration, what value is returned as the result of the call mystery(5)?

public static int mystery(int n)
{
   if (n == 0)
      return 1;
   else
      return 3 * mystery (n - 1);
}

243
For the call mystery(5), n != 0 so the else statement is executed. This results in the next recursive call of mystery(4). This will continue until the call mystery(0) is executed. At this point, the value 1 will be returned. Then each call of mystery can return with the 3 * the result of the recursive call. So this method will compute 3 to the given power.
0
This can never be 0 because the stopping condition returns 1 when you call mystery(0)
3
This would only be true if you called mystery(1)
81
This would be true if you called mystery(4)
27
This would be true if you called mystery(3)

You can step through the code using the Java Visualizer by clicking on the following link: Q-11-7-2.

11-7-11: Given the following method declaration, what value is returned as the result of the call product(5)?

public static int product(int n)
{
   if (n <= 1)
      return 1;
   else
      return n * product(n - 2);
}

1
The value 1 will only be returned when the initial call to product is less than or equal to 1.
10
If you assume the purpose of the method is to compute n * 2, this is correct, but the product method does not do this. Be sure to trace the code to see what happens.
25
If you assume the purpose of the method is to compute n * n this is correct, but the product method does not do this. Be sure to trace the code to see what happens.
3125
If you assume the purpose of the method is to compute n ^ n, this would be correct. But product does not do this. Be sure to trace the code to see what happens.
15
The result from product(5) is 5 * product(3) which is 3 * product(1) which is 1 so the answer is 1 * 3 * 5 = 15.

You can step through the code using the Java Visualizer by clicking on the following link: Q11-7-3.

11-7-12: Given the following method declaration, what value is returned as the result of the call f(5)?

public static int f(int n)
{
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else return f(n-1) + f(n-2);
}

8
This would be true if it was f(6) not f(5).
3
This would be true if it was f(4) not f(5).
There is no result because of infinite recursion.
This method will stop when n equals 0 or 1.
5
This is the Fibonacci method which returns 0 for 0 and 1 for 1 and Fibonacci(n-1) + Fibonacci(n-2) for the rest of the numbers.
0
This would be true if it was f(0) not f(5).

You can step through the code using the Java Visualizer by clicking on the following link: Q11-7-4.

11.7.3. Hard Multiple Choice Questions¶

11-7-13: Given the following method declaration, this method will return true if and only if:

public static boolean check(String s)
{
   return s.length() >= 2 &&
          (s.charAt(0) == s.charAt(1) ||
           check(s.substring(1)));
}

The string s contains two or more of the same characters.
It is not enough for s to contain two of the same characters, they must be adjacent to satisfy s.charAt(0) == s.charAt(1).
The string s starts with two or more of the same characters.
It is not neccessary for the adjacent characters to be at the start of the string.
The string s contains two or more of the same character that are next to each other.
This method will return true when s has at least 2 characters in it and at least 2 characters are the same and are adjacent.
The string s ends with two or more of the same characters
It is not neccessary for the adjacent characters to be at the end of the string.

Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

Support Runestone Academy Today

You can step through the code above by clicking on the following link Ex-11-8-1.

11-7-14: Given the following method declaration, what will redo(82, 3) return?

public static int redo(int i, int j)
{
   if (i==0)
      return 0;
   else
      return redo(i/j, j)+1;
}

5
The first time the method is called, i is not equal to 0, so the method makes a recursive call to itself, with the value of 82/3 which equals 27 due to integer division. This is still not equal to 0, so the method calls itself with the first parameter equal to 9, then 3, then 1. Finally, the method is called with the first parameter of 1/3 which equals 0 due to integer division which throws away any decimal part. Each method call adds 1 to the result, except for the final call when i is equal to 0.
4
Each time the method is called when i is not equal to 0, the return value is incremented. This happens 5 times, with i equal to 81, 27, 9, 3, and 1.
6
The return value is not incremented the last time the method is called, when i is equal to 0.
7
The method only executes 6 times, with the return value incremented each time i is not equal to zero
The method never returns due to infinite recursion.
Infinite recursion would happen if the method never reached its base case where i is equal to 0. This would be true if the division could result in a constantly shrinking fraction, but integer division truncates the fractional portion of the division.

You can step through the code above by clicking on the following link Ex-11-8-2.