Deck 12: Recursion

Question 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);

Answer 1

C

Question 2

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.

Answer 2

False

Question 3

Some problems are easier to solve recursively than iteratively.

Answer 3

True

Question 4

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 5

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 6

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 these

Question 7

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

Question 8

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 these

Question 9

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 10

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 11

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 these; this method isn't infinitely recursive

Question 12

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

Question 13

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 ofsum(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 14

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 15

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

Question 16

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 these

Question 17

Which of the following methods would properly compute the value of x % y (x mod y) recursively, assuming that x and y are 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 18

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

Question 19

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

Question 20

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 during the solution all of the disks must reside on each of the four towers.

Question 21

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
Recall the Towers of Hanoi recursive solution for this problem. If there are six 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

Question 22

Example Code Ch 12-2
Given the following recursive factorial method:
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
Refer to Example Code Ch 12-2: What is returned if factorial(3) is called?

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

Question 23

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 these

Question 24

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
Refer to Example Code 12-3: What is the result of calling bar(a, 8)?

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

Question 25

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
Recall the Towers of Hanoi recursive solution for this problem. The solution to the Towers of Hanoi has a(n) __________ complexity.

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

Question 26

Example Code Ch 12-1
Given 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;
}
Refer to Example Code Ch 12-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 27

Example Code Ch 12-1
Given 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;
}
Refer to Example Code Ch 12-1: Calling this method will result in infinite recursion if which of the following conditions is initially true?

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

Question 28

Example Code Ch 12-2
Given the following recursive factorial method:
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
Refer to Example Code Ch 12-2: How many times is the factorial method called with factorial(5)? Include the original method call in your counting.

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

Question 29

The Koch fractal of order 1 is

A) a triangle
B) a square
C) a point
D) a circle
E) None of these

Question 30

Example Code Ch 12-2
Given the following recursive factorial method:
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
Refer to Example Code Ch 12-2: 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 31

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
Recall the Towers of Hanoi recursive solution for this problem. If there are two 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 32

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 33

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
Refer to Example Code 12-3: What is the result of calling foo(a, 2, 9)?

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

Question 34

What can be said about the difference or similarity, if any, between an infinite loop and an infinite recursion?

A) It is impossible to detect the latter while it's 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 these

Question 35

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
Refer to Example Code 12-3: What is the result of calling bar(a, 0)?

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

Question 36

Example Code Ch 12-4
The following recursive method recognizes whether a String parameter consists of a specific pattern and returns true if the String has that pattern, false otherwise.
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 )
return false;
else if )
return patternRecognizer);
else return false;
}
Refer to Example Code Ch 12-4: Which String of the following would result in patternRecognizer returing true?

A) "abcba"
B) "aaabbb"
C) "abcde"
D) "aabba"
E) All of these

Question 37

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 38

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
Refer to Example Code 12-3: What is the result of calling foo(a, 2, 0)?

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

Question 39

Example Code Ch 12-2
Given the following recursive factorial method:
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
Refer to Example Code Ch 12-2: 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 40

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
Refer to Example Code 12-3: What is the result of calling foo(a, 3, 0)?

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

Question 41

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 would be 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 midpoint. 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 42

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

Question 43

Example Code Ch 12-4
The following recursive method recognizes whether a String parameter consists of a specific pattern and returns true if the String has that pattern, false otherwise.
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 )
return false;
else if )
return patternRecognizer);
else return false;
}
Explain what a "base case" is in a recursive method.

Question 44

Example Code Ch 12-4
The following recursive method recognizes whether a String parameter consists of a specific pattern and returns true if the String has that pattern, false otherwise.
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 )
return false;
else if )
return patternRecognizer);
else return false;
}
Refer to Example Code Ch 12-4: If the method is called as patternRecognizer(x) where x = "aa", what will the result be?

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

Question 45

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 46

Example Code Ch 12-4
The following recursive method recognizes whether a String parameter consists of a specific pattern and returns true if the String has that pattern, false otherwise.
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 )
return false;
else if )
return patternRecognizer);
else return false;
}
Provide a definition for the following terms as they relate to programming: recursion, indirect recursion and infinite recursion.

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

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 49

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 50

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 51

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 52

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

Question 53

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 54

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 55

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