# 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.

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

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

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

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¶

- 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-5: Which line has the recursive call?

```
1public static int factorial(int n)
2{
3 if (n == 0)
4 return 1;
5 else return n * factorial(n-1);
6}
```

- 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-6: Which line has the recursive call?

```
1public String starString(int n)
2{
3 if (n == 0) {
4 return "*";
5 } else {
6 return starString(n - 1) + starString(n - 1);
7 }
8}
```

- 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-7: How many recursive calls does the following method contain?

```
1public static int fibonacci(int n)
2{
3 if (n == 0)
4 return 0;
5 else if (n == 1)
6 return 1;
7 else return fibonacci(n-1) + fibonacci(n-2);
8 }
```

- 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-8: How many recursive calls does the following method contain?

```
1public static int multiplyEvens(int n)
2{
3 if (n == 1) {
4 return 2;
5 } else {
6 return 2 * n * multiplyEvens(n - 1);
7 }
8}
```

## 11.7.2. Medium Multiple Choice Questions¶

- 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.

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

?

```
1//precondition: x >=0
2public static void mystery (int x)
3{
4 System.out.print(x % 10);
5
6 if ((x / 10) != 0)
7 {
8 mystery(x / 10);
9 }
10 System.out.print(x % 10);
11}
```

You can step through the code using the Java Visualizer by clicking on the following link: Q-11-7-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)`

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

?

```
1public static int mystery(int n)
2{
3 if (n == 0)
4 return 1;
5 else
6 return 3 * mystery (n - 1);
7}
```

You can step through the code using the Java Visualizer by clicking on the following link: Q-11-7-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`

.

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

?

```
1public static int product(int n)
2{
3 if (n <= 1)
4 return 1;
5 else
6 return n * product(n - 2);
7}
```

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

- 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)`

.

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

?

```
1public static int f(int n)
2{
3 if (n == 0)
4 return 0;
5 else if (n == 1)
6 return 1;
7 else return f(n-1) + f(n-2);
8}
```

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¶

- 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.

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)));
}
```

You can step through the code above by clicking on the following link Ex-11-8-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.

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;
}
```

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