Deck 12: Recursion

Question 1

For the questions below, recall the Towers of Hanoi recursive solution.
If there are 6 disks to move from one Tower to another, how many disk movements would it take to solve the problem using the recursive solution?

A) 6
B) 13
C) 31
D) 63
E) 127

Answer 1

D
Explanation: D) The Towers of Hanoi solution requires using the previous solution twice + 1 extra move. To solve it for 1 disk, it takes 1 move. To solve it for 2 disks, it takes using the solution for 1 disk twice + 1 extra move, or 1 move + 1 move + 1 extra move = 3 moves. We capture this in the equation 2ⁿ - 1 where n is the number of disks. For 3 disks this takes 7 moves, for 4 disks this takes 15 moves, for 5 disks this takes 31 moves and for 6 disks this takes 63 moves.

Question 2

For the questions below, assume that int[ ] a = {6, 2, 4, 6, 2, 1, 6, 2, 5} and consider the two recursive methods below foo and bar.
public int foo(int[ ] a, int b, int j)
{
if (j < a.length)
if (a[j] != b) return foo (a, b, j+1);
else return foo (a, b, j+1) + 1;
else return 0;
}
public int bar(int[ ] a, int j)
{
if (j < a.length)
return a[I] + bar(a, j+1);
else return 0;
}
What is the result of calling foo(a, 2, 0);?

A) 0
B) 1
C) 2
D) 3
E) 4

Answer 2

C
Explanation: C) The method foo counts the number of occurrences of the int parameter in the second position in the array starting at the index given as the third parameter. So, foo(a, 2, 0) finds the number of 2s in a. 2 appears 3 times in array a.

Question 3

What does the following recursive method determine?
Public boolean question16(int[ ]a, int[ ] b, int j)
{
If (j = = a.length) return false;
Else if (j = = b.length) return True;
Else return question16(a, b, j+1);
}

A) returns True if a and b are equal in size, false otherwise
B) returns True if a is larger than b, false otherwise
C) returns True if b is larger than a, false otherwise
D) returns True if a and b have no elements
E) returns the length of array a + length of array b

Answer 3

B
Explanation: B) The method returns True if the third parameter, j, is equal to the length of b but not equal to the length of a. Thus, the method returns True if the third parameter has reached the value indicating the end of array b but not the end of array a so this is True if a is larger than b. If a and b are equal length or if a is shorter than b, false is returned.

Question 4

For the questions below, refer to the following recursive factorial method.
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
How many times is the factorial method invoked if originally called with factorial(5)? Include the original method call in your counting.

A) 1
B) 4
C) 5
D) 6
E) 7

Question 5

For the questions below, refer to the following recursive factorial method.
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
What condition defines the base case for this method?

A) (x > 1)
B) (x = = 1)
C) (x = = 0)
D) (x <= 0)
E) (x <= 1)

Question 6

For the questions below, use the following recursive method.
public int question1_2(int x, int y)
{
if (x == y) return 0;
else return question1_2(x-1, y) + 1;
}
If the method is called as question1_2(8, 3), what is returned?

A) 11
B) 8
C) 5
D) 3
E) 24

Question 7

For the questions below, use the following recursive method.
public int question1_2(int x, int y)
{
if (x == y) return 0;
else return question1_2(x-1, y) + 1;
}
The following method should return True if the int parameter is even and either positive or 0, and false otherwise. Which set of code should you use to replace ... so that the method works appropriately?
Public boolean question3(int x) { ... }

A) if (x = = 0) return True;else if (x < 0) return false;else return question3(x - 1);
B) if (x = = 0) return false;else if (x < 0) return True;else return question3(x - 1);
C) if (x = = 0) return True;else if (x < 0) return false;else return question3(x - 2);
D) if (x = = 0) return false;else if (x < 0) return True;else return question3(x - 2);
E) return(x = = 0);

Question 8

Which of the following recursive methods would execute approximately log ₂ n times for an initial parameter n?

A) public void logcode(int n) {
If (n > 1) logcode(n - 1);
}
B) public void logcode(int n) {
If (n > 2) logcode(n - 2);
}
C) public void logcode(int n) {
If (n > 0) logcode(0);
}
D) public void logcode(int n) {
If (n > 1) logcode(n / 2);
}
E) public void logcode(int n) {
If (n > 1) logcode(n - 1 /2);
}

Question 9

For the questions below, recall the Towers of Hanoi recursive solution.
If there are 2 disks to move from one Tower to another, how many disk movements would it take to solve the problem using the recursive solution?

A) 0
B) 1
C) 2
D) 3
E) 4

Question 10

For the questions below, recall the Towers of Hanoi recursive solution.
The solution to the Towers of Hanoi has a(n) ________ complexity.

A) linear
B) polynomial
C) logarithmic
D) exponential
E) bad

Question 11

For the questions below, assume that int[ ] a = {6, 2, 4, 6, 2, 1, 6, 2, 5} and consider the two recursive methods below foo and bar.
public int foo(int[ ] a, int b, int j)
{
if (j < a.length)
if (a[j] != b) return foo (a, b, j+1);
else return foo (a, b, j+1) + 1;
else return 0;
}
public int bar(int[ ] a, int j)
{
if (j < a.length)
return a[I] + bar(a, j+1);
else return 0;
}
What is the result of calling foo(a, 2, 9);?

A) 0
B) 1
C) 2
D) 3
E) 4

Question 12

For the questions below, assume that int[ ] a = {6, 2, 4, 6, 2, 1, 6, 2, 5} and consider the two recursive methods below foo and bar.
public int foo(int[ ] a, int b, int j)
{
if (j < a.length)
if (a[j] != b) return foo (a, b, j+1);
else return foo (a, b, j+1) + 1;
else return 0;
}
public int bar(int[ ] a, int j)
{
if (j < a.length)
return a[I] + bar(a, j+1);
else return 0;
}
What is the result of calling bar(a, 0);?

A) 0
B) 5
C) 6
D) 12
E) 34

Question 13

For the questions below, refer to the following recursive factorial method.
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
What is returned if factorial(0) is called?

A) 0
B) 1
C) 2
D) nothing, factorial(0) causes infinite recursion
E) nothing, factorial(0) produces a run-time error

Question 14

What is wrong with the following recursive sum method? The method is supposed to sum up the values between 1 and x (for instance, sum(5) should be 5 + 4 + 3 + 2 + 1 = 15).
Public int sum(int x)
{
If (x = = 0) return 0;
Else return sum(x - 1) + x;
}

A) the base case should return 1 instead of 0
B) the recursive case should return sum(x - 1) + 1; instead of sum(x - 1) + x;
C) the base case condition should be (x <= 0) instead of (x = = 0)
D) the recursive case should return sum(x) + 1;
E) the method should return a boolean instead of an int

Question 15

For the questions below, use the following recursive method.
public int question1_2(int x, int y)
{
if (x == y) return 0;
else return question1_2(x-1, y) + 1;
}
Calling this method will result in infinite recursion if which condition below is initially True?

A) (x = = y)
B) (x != y)
C) (x > y)
D) (x < y)
E) (x = = 0 && y != 0)

Question 16

For the questions below, refer to the following recursive factorial method.
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
What is returned if factorial(3) is called?

A) 0
B) 1
C) 3
D) 6
E) 9

Question 17

Why is the following method one which has infinite recursion?
Public int infiniteRecursion(int n)
{
If (n > 0) return infiniteRecursion(n) + 1;
Else return 0;
}

A) Because there is no base case
B) Because the base case will never be True
C) Because the recursive call does not move the parameter closer to the base case
D) Because the recursive call moves the problem further away from the base case
E) None of the above, there is no infinite recursion in this method

Question 18

For the questions below, assume that int[ ] a = {6, 2, 4, 6, 2, 1, 6, 2, 5} and consider the two recursive methods below foo and bar.
public int foo(int[ ] a, int b, int j)
{
if (j < a.length)
if (a[j] != b) return foo (a, b, j+1);
else return foo (a, b, j+1) + 1;
else return 0;
}
public int bar(int[ ] a, int j)
{
if (j < a.length)
return a[I] + bar(a, j+1);
else return 0;
}
What is the result of bar(a, 8);?

A) 0
B) 5
C) 6
D) 12
E) 34

Question 19

For the questions below, assume that int[ ] a = {6, 2, 4, 6, 2, 1, 6, 2, 5} and consider the two recursive methods below foo and bar.
public int foo(int[ ] a, int b, int j)
{
if (j < a.length)
if (a[j] != b) return foo (a, b, j+1);
else return foo (a, b, j+1) + 1;
else return 0;
}
public int bar(int[ ] a, int j)
{
if (j < a.length)
return a[I] + bar(a, j+1);
else return 0;
}
What is the result of calling foo(a, 3, 0);?

A) 0
B) 1
C) 2
D) 3
E) 4

Question 20

What does the following method compute? Assume the method is called initially with i = 0
Public int question9(String a, char b, int i)
{
If (i = = a.length( )) return 0;
Else if (b = = a.charAt(i)) return question9(a, b, i+1) + 1;
Else return question9(a, b, i+1);
}

A) the length of String a
B) the length of String a concatenated with char b
C) the number of times char b appears in String a
D) returns 1 if char b appears in String a at least once, and 0 otherwise
E) the char which appears at location i in String a

Question 21

Some problems are easier to solve recursively than iteratively.

Question 22

Traversing a maze is much easier to do iteratively than recursively.

Question 23

The following two methods will both compute the same thing when invoked with the same value of x. That is, method1(x) = = method2(x).
public int method1(int x)
{
if (x > 0) return method1(x - 1) + 1;
else return 0;
}
public int method2(int x)
{
if (x > 0) return 1 + method2(x - 1);
else return 0;
}

Question 24

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
public boolean patternRecognizer(String a)
{
if (a == null) return false;
else if (a.length( ) = = 1 | | (a.length( ) = = 2 && a.charAt(0) = = a.charAt(1) ) ) return True;
else if (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
If the statement a.substring(1, a.length( ) - 1) were changed to be (a.substring(1, a.length( )), then the method would

A) have infinite recursion unless the String were null
B) always return True
C) always return false
D) return True only if all characters of the String were the same
E) return True only the String had only two characters and they were the same

Question 25

For the questions below, consider the following representation of grid and the maze code from Chapter 11.
Grid:
1 1 1 1 1 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 1 0
0 0 1 1 0 0 1 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 1 1
Code:
public boolean traverse(int row, int column)
{
if (valid(row, column))
{
boolean done = false;
grid[row][column] = TRIED;
if (row == grid.length - 1 && column == grid[0].length - 1)
done = True;
else
{
done = traverse(row + 1, column);
if (!done) done = traverse(row, column + 1);
if (!done) done = traverse(row - 1, column);
if (!done) done = traverse(row, column - 1);
}
if (done) grid[row][column] = PATH;
}
return done;
}
Assume valid returns True if row and column are >= 0 and <= the grid's row length or column length and the entry at this position = = 1. And assume TRIED = 3 and PATH = 7
Assume at some point in processing, grid's row 0 has become 3 3 3 1 1 1 0 0. Which direction will next be tried?

A) up
B) down
C) left
D) right
E) none, the recursion ends at this point

Question 26

For the questions below, consider the following representation of grid and the maze code from Chapter 11.
Grid:
1 1 1 1 1 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 1 0
0 0 1 1 0 0 1 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 1 1
Code:
public boolean traverse(int row, int column)
{
if (valid(row, column))
{
boolean done = false;
grid[row][column] = TRIED;
if (row == grid.length - 1 && column == grid[0].length - 1)
done = True;
else
{
done = traverse(row + 1, column);
if (!done) done = traverse(row, column + 1);
if (!done) done = traverse(row - 1, column);
if (!done) done = traverse(row, column - 1);
}
if (done) grid[row][column] = PATH;
}
return done;
}
Assume valid returns True if row and column are >= 0 and <= the grid's row length or column length and the entry at this position = = 1. And assume TRIED = 3 and PATH = 7
Which of the following grids would be the result after traverse has completed all of its recursive calls?

A) 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0
0 0 1 0 0 1 1 0
0 0 1 1 0 0 1 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 1 1
B) 3 3 3 3 3 3 0 0 0 0 3 0 0 3 0 0
0 0 3 0 0 3 3 0
0 0 3 3 0 0 3 0
0 0 0 3 3 0 0 0
0 0 0 0 3 3 3 3
C) 7 7 7 3 3 3 0 0 0 0 7 0 0 3 0 0
0 0 7 0 0 3 3 0
0 0 7 7 0 0 3 0
0 0 0 7 7 0 0 0
0 0 0 0 7 7 7 7
D) 7 7 7 7 7 7 0 0 0 0 3 0 0 7 0 0
0 0 3 0 0 7 7 0
0 0 3 3 0 0 7 0
0 0 0 3 3 0 0 0
0 0 0 0 3 3 3 3
E) 3 3 3 7 7 7 0 0 0 0 3 0 0 7 0 0
0 0 3 0 0 7 7 0
0 0 3 3 0 0 7 0
0 0 0 3 3 0 0 0
0 0 0 0 3 3 3 3

Question 27

For the questions below, consider the following representation of grid and the maze code from Chapter 11.
Grid:
1 1 1 1 1 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 1 0
0 0 1 1 0 0 1 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 1 1
Code:
public boolean traverse(int row, int column)
{
if (valid(row, column))
{
boolean done = false;
grid[row][column] = TRIED;
if (row == grid.length - 1 && column == grid[0].length - 1)
done = True;
else
{
done = traverse(row + 1, column);
if (!done) done = traverse(row, column + 1);
if (!done) done = traverse(row - 1, column);
if (!done) done = traverse(row, column - 1);
}
if (done) grid[row][column] = PATH;
}
return done;
}
Assume valid returns True if row and column are >= 0 and <= the grid's row length or column length and the entry at this position = = 1. And assume TRIED = 3 and PATH = 7
Define the magnitude of a number as the location of the decimal point from the left of the number (that is, if a number has 4 digits followed by the decimal point, it will have a magnitude of 4). 100 would then have a magnitude of 3 and 55,555.555 would have a magnitude of 5. A partial recursive method is given below to compute a positive int parameter's magnitude. Which answer below is needed to complete the method?
Public int magnitude(double x)
{
If (x < 1) return 0;
Else return _______;
}

A) magnitude(x - 1) + 10;
B) magnitude(x - 10) + 1;
C) magnitude(x / 10) + 10;
D) magnitude(x / 10) + 1;
E) magnitude(x / 10) * 2;

Question 28

A recursive method without a base case leads to infinite recursion.

Question 29

Each time the order of a Koch fractal increases by one, the number of straight line segments

A) increases by a factor of two
B) increases by a factor of three
C) increases by a factor of four
D) is squared
E) is cubed

Question 30

For the questions below, consider the following representation of grid and the maze code from Chapter 11.
Grid:
1 1 1 1 1 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 1 0
0 0 1 1 0 0 1 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 1 1
Code:
public boolean traverse(int row, int column)
{
if (valid(row, column))
{
boolean done = false;
grid[row][column] = TRIED;
if (row == grid.length - 1 && column == grid[0].length - 1)
done = True;
else
{
done = traverse(row + 1, column);
if (!done) done = traverse(row, column + 1);
if (!done) done = traverse(row - 1, column);
if (!done) done = traverse(row, column - 1);
}
if (done) grid[row][column] = PATH;
}
return done;
}
Assume valid returns True if row and column are >= 0 and <= the grid's row length or column length and the entry at this position = = 1. And assume TRIED = 3 and PATH = 7
If traverse is first called with traverse(0, 0); what will the first recursive call of traverse be?

A) traverse(0, 0);
B) traverse(0, 1);
C) traverse(1, 0);
D) traverse(1, 1);
E) traverse(0, -1);

Question 31

The difference between direct and indirect recursion is

A) direct recursion occurs when a method invokes itself; indirect recursion occurs when there is an intervening method
B) indirect recursion occurs when a method invokes itself; direct recursion occurs when there is an intervening method
C) direct recursion only occurs with methods declared to be private; indirect recursion can occur with methods declared to be private, protected, or public
D) indirect recursion only occurs with methods declared to be private; direct recursion can occur with methods declared to be private, protected, or public
E) none of the above

Question 32

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
public boolean patternRecognizer(String a)
{
if (a == null) return false;
else if (a.length( ) = = 1 | | (a.length( ) = = 2 && a.charAt(0) = = a.charAt(1) ) ) return True;
else if (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
If the method is called as patternRecognizer(x) where x is "aa", what will the result be?

A) True
B) false
C) a NullPointerException
D) a run-time error
E) infinite recursion

Question 33

An infinite loop and an infinite recursion

A) are different because it is impossible to detect the latter, while it's quite easy to detect the former
B) both continue to repeat indefinitely
C) both will be caught by the compiler
D) both will be caught by the Java Virtual Machine during execution
E) none of the above

Question 34

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
public boolean patternRecognizer(String a)
{
if (a == null) return false;
else if (a.length( ) = = 1 | | (a.length( ) = = 2 && a.charAt(0) = = a.charAt(1) ) ) return True;
else if (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
What is a fractal?

A) a portion of a larger structure (a fraction)
B) a geometric shape that can be made up of the same pattern repeated at different scales and orientations
C) a recursively defined numeric function
D) a ratio (a fraction)
E) none of the above

Question 35

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
public boolean patternRecognizer(String a)
{
if (a == null) return false;
else if (a.length( ) = = 1 | | (a.length( ) = = 2 && a.charAt(0) = = a.charAt(1) ) ) return True;
else if (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
A recursive algorithm is superior to an iterative algorithm along which of the following criteria?

A) The recursive algorithm is easier to debug
B) The recursive algorithm is computationally more efficient
C) The recursive algorithm is more elegant
D) The recursive algorithm requires less memory to execute
E) all of the above

Question 36

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
public boolean patternRecognizer(String a)
{
if (a == null) return false;
else if (a.length( ) = = 1 | | (a.length( ) = = 2 && a.charAt(0) = = a.charAt(1) ) ) return True;
else if (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
Aside from writing recursive methods, another way that recursion is often used is to define

A) words in English
B) mathematical functions
C) rules and laws
D) child classes of a parent class in object-oriented programming
E) recursion is used in all of the above

Question 37

The Koch fractal of order 1 is

A) a triangle
B) a square
C) a point
D) a circle
E) none of the above

Question 38

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
public boolean patternRecognizer(String a)
{
if (a == null) return false;
else if (a.length( ) = = 1 | | (a.length( ) = = 2 && a.charAt(0) = = a.charAt(1) ) ) return True;
else if (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
Which String below would result in patternRecognizer returning True?

A) "abcba"
B) "aaabbb"
C) "abcde"
D) "aabba"
E) all of the above Strings will result in the method returning True

Question 39

The following method lacks a base case.
public int noBaseCase(int x)
{
if (x > 0)
return noBaseCase(x - 1) + 1;
else return noBaseCase(x - 2) + 2;
}

Question 40

For the questions below, recall the Towers of Hanoi recursive solution.
Which of the following methods would properly compute the value of x % y (x mod y) recursively, assuming that x and y not negative numbers?

A) public int recursiveMod(int x, int y) {
If (x < y) return y;
Else return recursiveMod(x, y - x);
}
B) public int recursiveMod(int x, int y) {
If (x == y) return 0;
Else return recursiveMod(x - y, y) + 1;
}
C) public int recursiveMod(int x, int y) {
If (x < y) return x;
Else return recursiveMod(x - y, y) + 1;
}
D) public int recursiveMod(int x, int y) {
If (x < y) return x;
Else return recursiveMod(x - y, y);
}
E) public int recursiveMod(int x, int y) {
While (x > y)
X = x - y;
Return x;
}

Question 41

Assume a function g(x) is defined as follows where x is an int parameter:
g(x) = g(x - 1) * g (x - 3) if x is even and x > 3
= g(x - 2) if x is odd and x > 3
= x otherwise
Write a recursive method to compute g.

Question 42

For the Towers of Hanoi problem, show how many moves it will take to solve the problem with 5 disks, 6 disks, 7 disks, 8 disks, 9 disks, and 10 disks.

Question 43

Consider the following recursive sum method:
public int sum(int x)
{
if (x = = 0) return 0;
else return sum(x - 1) + 1;
}
If the base case is replaced with "if (x = = 1) return 1;" the method will still compute the same thing.

Question 44

As identified in the text, some algorithms execute only (approximately) log₂n operations if the original parameter or size of input is n. Compare this to an algorithm that executes n times by providing a table demonstrating the values of n and log₂n for n = 1, 10, 100, 1000, 10,000, 100,000 and 1,000,000.

Question 45

Since iterative solutions often use loop variables and recursive solutions do not, the recursive solution is usually more memory efficient (uses less memory) than the equivalent iterative solution.

Question 46

Demonstrate how factorial(4) is computed given the following recursive method for factorial:
public int factorial(int n)
{
if (n > 1) return factorial(n - 1) * n;
else return 1;
}

Question 47

Describe how to solve the Towers of Hanoi problem using 4 disks (that is, write down move for move how to solve the problem).

Question 48

Provide a definition for the terms as they relate to programming: recursion, indirect recursion and infinite recursion.

Question 49

Rewrite the following iterative method as a recursive method that computes the same thing. NOTE: your recursive method will require an extra parameter.
public int iterative1(int x)
{
int count = 0, factor = 2;
while (factor < x)
{
if (x % factor = = 0) count++;
factor++;
}
return count;
}

Question 50

As identified in the text, some algorithms execute approximately 2ⁿ operations if the original parameter or size of input is n. Compare the two values n and 2ⁿ by giving a table for n = 1, 5, 10, 20, 30, and 40.

Question 51

Rewrite the following iterative method as a recursive method that returns the same String.
public String listOfNumbers( )
{
String s = "";
for (j = 1; j<10; j++)
s += j;
return s;
}

Question 52

Rewrite the following iterative method as a recursive method that computes the same thing. NOTE: your recursive method will require an extra parameter.
public String reversal(String x)
{
int y = x.length( );
String s = "";
for (int j = y-1; j >=0; j--)
s += x.charAt(j);
return s;
}

Question 53

The recursive method to solve the Towers of Hanoi is usable only if the parameter for the number of disks is 7 or smaller.

Question 54

The following method correctly adds two ints, returning their sum:
public int add(int a, int b)
{
return (b > 0) ?
add(a+1, b-1) : a;
}

Question 55

A Koch snowflake of order = 1 can be drawn without recursion.

Question 56

The Koch snowflake has an infinitely long perimeter, but it contains a finite area.

Question 57

If one were to create a Towers of Hanoi puzzle with four towers instead of three, with rules changed appropriately, it should be possible to create a recursive solution for the puzzle where one of the constraints is that at some point in the solution all of the disks must reside on each of the four towers.

Question 58

The following method correctly multiplies two ints so long as both are non-negative:
public int mpy(int a, int b)
{
return (b > 0) ?
a + mpy(a, b-1) : 0;
}

Question 59

It always is possible to replace a recursion by an iteration and vice versa.

Question 60

We can define a list of int values recursively as: a list_item, followed by a comma, followed by a list where a list_item is any int value.

Question 61

Describe the difference(s) between the following two sets of code, neither of which reaches a terminating condition.
public void forever1( )
{
while (True);
}
public void forever2( )
{
forever2( );
}

Question 62

Assume page is a Graphics object. If the following method is called with drawIt(50, page), show what is displayed on the Graphics object page.
public void drawIt(int x, Graphics page)
{
if (x > 10)
{
page.setColor(Color.black);
page.drawRect(0, 0, x, x);
drawIt(x - 10, page);
}
}

Question 63

Write a recursive method called numSegments(int order) that yields the number of line segments in a Koch snowflake of order "order."

Question 64

The game of high-low is one where one person selects a number between 1 and 100 and a user tries to guess it by guessing a number and being told if the guessed number is the right number, too low or too high. The user repeats guessing until getting the correct answer. A logical user will always guess at the midpoint of the possible values (for instance, the first guess is 50 followed by either 25 or 75, etc). Write a recursive method to play the game of high-low by having the computer guess a mid point. The method should receive three parameters, the number itself, the lowest value in the range and the highest value in the range and return the number of guesses that it took to guess the right number.

Question 65

The following drawing is a line using the Koch snowflake design where order = 2. Show how it would appear with order = 3.

Question 66

The Euclidean algorithm for calculating the greatest common divisor (gcd) of two integers a and b is: "If a is a nonnegative integer, b is a positive integer, and r = a mod b, then gcd(a,b) = gcd(b,r). Write a recursive method that uses the Euclidean algorithm to calculate the gcd.

Question 67

Recursion is a popular programming tool but beginning programmers tend to shy away from it. Why do you suppose this is True?

Question 68

Explain what a "base case" is in a recursive method.