26) 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
27) 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
28) 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
29) 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
30) 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
31) 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
32) The Koch fractal of order 1 is
A) a triangle
B) a square
C) a point
D) a circle
E) none of the above
33) 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
34) 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
35) 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
17
© Pearson Education Limited, 2015
12.2 True/False Questions
1) A recursive method without a base case leads to infinite recursion.
2) 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;
}
3) Traversing a maze is much easier to do iteratively than recursively.
4) Some problems are easier to solve recursively than iteratively.
5) 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;
}
6) 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.
7) The recursive method to solve the Towers of Hanoi is usable only if the parameter for the
number of disks is 7 or smaller.
8) A Koch snowflake of order = 1 can be drawn without recursion.
9) 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.
10) 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.
11) It always is possible to replace a recursion by an iteration and vice versa.
12) 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;
}
13) 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;
}
14) 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.
15) The Koch snowflake has an infinitely long perimeter, but it contains a finite area.
1) Provide a definition for the terms as they relate to programming: recursion, indirect recursion
and infinite recursion.
2) 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;
}
3) 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;
}
4) 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;
}
5) As identified in the text, some algorithms execute only (approximately) log2n 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 log2n for n = 1, 10, 100, 1000, 10,000,
100,000 and 1,000,000.
6) As identified in the text, some algorithms execute approximately 2n operations if the original
parameter or size of input is n. Compare the two values n and 2n by giving a table for n = 1, 5,
10, 20, 30, and 40.
7) Describe how to solve the Towers of Hanoi problem using 4 disks (that is, write down move
for move how to solve the problem).
8) 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.
9) 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.
}
10) 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;
}
11) 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( );
}
12) 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);
}
}
13) 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.
14) The following drawing is a line using the Koch snowflake design where order = 2. Show
how it would appear with order = 3.
15) Recursion is a popular programming tool but beginning programmers tend to shy away from
it. Why do you suppose this is true?
16) Write a recursive method called numSegments(int order) that yields the number of line
segments in a Koch snowflake of order “order.”
}
17) 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.
}
18) Explain what a “base case” is in a recursive method.