Short Answers Section 8.1 Recursive Methods


What is the importance of the stopping case in recursive methods?

Write a recursive method that has one parameter which is an int value
called x. The method prints x asterisks, followed by x exclamation points.
Do NOT use any loops. Do NOT use any variables other than x.

Implement the following method. Do not use any local variables or loops.
public static void pattern(int n)
// Precondition: n > 0;
// Postcondition: The output consists of lines of integers. The first line
// is the number n. The next line is the number 2n. The next line is
// the number 4n, and so on until you reach a number that is larger than
// 4242. This list of numbers is then repeated backward until you get back
// to n.
/* Example output with n = 840:
840
1680
3360
6720
6720
3360
1680
840

Write a recursive method with two int parameters, m and n.
The precondition requires 0 <= m and m <= n.
The method prints a line of m asterisks, then a line of m+1 asterisks,
and so on up to a line of n asterisks. Then the same pattern is repeated
backward: a line of n asterisks, then n1, and so on down to n.
The only loop allowed in your implementation is a loop to print a line of m
asterisks. You may have two copies of this loop in different places
of the implementation.

This question involves a game with teddy bears, similar to the game in Chapter 8. The game starts when I give you
some bears. You can then give back some bears, but you must follow these rules
(where n is the number of bears that you have):

If n is even, then you may give back exactly n/2 bears.

If n is divisible by 3 or 4, then you may multiply the last two digits of n
and give back this many bears. (By the way, the last digit of n is
n%10, and the nexttolast digit is ((n%100)/10).

If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game is to end up with EXACTLY 42 bears.
For example, suppose that you start with 250 bears. Then you could make
these moves:
Start with 250 bears.
Since 250 is divisible by 5, you may return 42 of the bears,
leaving you with 208 bears.
Since 208 is even, you may return half of the bears,
leaving you with 104 bears.
Since 104 is even, you may return half of the bears,
leaving you with 52 bears.
Since 52 is divisible by 4, you may multiply the last two digits
(resulting in 10) and return these 10 bears. This leaves you
with 42 bears.
You have reached the goal!
Write a recursive method to meet this specification:
public static boolean bears(int n)
// Postcondition: A true return value means that it is possible to win
// the bear game by starting with n bears. A false return value means that
// it is not possible to win the bear game by starting with n bears.
// Examples:
// bear(250) is true (as shown above)
// bear(42) is true
// bear(84) is true
// bear(53) is false
// bear(41) is false
// Hint: To test whether n is even, use the expression ((n % 2) == 0).

Write a recursive method with this prototype:
void permute(String first, String second)
// Postcondition: The output consists of lines of Strings. Each String
// is made by writing some rearrangement of first followed by all
// of second.
// For example, if first is "CAT" and second is "MAN", then there will
// be six lines of output:
// CATMAN
// ACTMAN
// TCAMAN
// CTAMAN
// ATCMAN
// TACMAN
Hints: The stopping case occurs when the length of first is zero (in which case
the method prints second). Some String methods that will help you
for a String s:
 s.length( ) is the length of s.
 s.charAt(s.length( )  1) is a copy of the last character of s.
 System.out.println(s) will print s.
 s = (String.valueOf(c) + s) will insert the character c at the front of s.
 s = (s + String.valueOf(c)); will insert the character c at the end of s.
 s = s.substring(1) will remove one character from the front of s.
 s = s.substring(0, s.length( )1) will remove the last character from s.

Write a method with this specification:
public static void numbers(String prefix, int levels)
The method prints output consisting of
the String prefix followed by "section numbers" of the
form 1.1., 1.2., 1.3., and so on. The levels argument determines how may
levels the section numbers have. For example, if levels is 2, then the section
numbers have the form x.y. If levels is 3, then section numbers have the
form x.y.z. The digits permitted in each level are always '1' through '9'.
As an example, if prefix is the string "THERBLIG" and levels is 2, then the
method would print 81 strings. In this case, the method
starts by printing:
THERBLIG1.1.
THERBLIG1.2.
THERBLIG1.3.
and ends by printing:
THERBLIG9.7.
THERBLIG9.8.
THERBLIG9.9.
The stopping case occurs when levels reaches zero (in which case the
prefix is printed once by itself followed by nothing else).
You'll need the ability to make a new string which consists of
prefix followed by another character (such as '1') and a period ('.').
If s is the String that you want to create and c is the digit character
(such as '1'), then the following statement will correctly form s:
s = (prefix + String.valueOf(c)) + ".";
This new String s can be passed as a parameter to recursive calls of the
method.
Short Answers Section 8.2 Fractals and Mazes

 Write a method with one positive int parameter called n.
The method will write 2^n1 integers (where ^ is the
exponentiation operation). Here are the patterns of output for
various values of n:
n=1: Output is: 1
n=2: Output is: 1 2 1
n=3: Output is: 1 2 1 3 1 2 1
n=4: Output is: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
And so on. Note that the output for n always consists of the output
for n1, followed by n itself, followed by a second copy of the output
for n1.
 What property of fractals lends itself to recursive thinking?
 The first step of the maze search algorithm was to step forward and
write your name on the ground. What is the importance of writing your
name on the ground?
 Consider the following method:
public static boolean deadend()
// Postcondition: The return value is true if the direction directly
// in front is a dead end (i.e., a direction that cannot contain the
// tapestry).
{
return inquire("Are you facing a wall?")

inquire("Is your name written in front of you?");
}
Explain why the method deadend sometimes asks 2 questions and
sometimes asks only 1.
Short Answers Section 8.3 Reasoning About Recursion

 What two properties must a variant expression have to guarantee
that a recursive method terminates?
Multiple Choice Section 8.1 Recursive Methods


In a single method declaration, what is the maximum number of statements
that may be recursive calls?
 A. 1
 B. 2
 C. n (where n is the argument)
 D. There is no fixed maximum

What is the maximum depth of recursive calls a method may make?
 A. 1
 B. 2
 C. n (where n is the argument)
 D. There is no fixed maximum

Consider the following method:
void superWriteVertical(int number)
// Postcondition: The digits of the number have been written,
// stacked vertically. If number is negative, then a negative
// sign appears on top.
{
if (number < 0)
{
System.out.println("");
superWriteVertical(number);
}
else if (number < 10)
System.out.println(number);
else
{
superWriteVertical(number / 10);
System.out.println(number % 10);
}
}
What values of number are directly handled by the stopping case?
 A. number < 0
 B. number < 10
 C. number >= 0 && number < 10
 D. number > 10

Consider the following method:
void superWriteVertical(int number)
// Postcondition: The digits of the number have been written,
// stacked vertically. If number is negative, then a negative
// sign appears on top.
{
if (number < 0)
{
System.out.println("");
superWriteVertical(number);
}
else if (number < 10)
System.out.println(number);
else
{
superWriteVertical(number / 10);
System.out.println(number % 10);
}
}
Which call will result in the most recursive calls?
 A. super_write_vertical(1023)
 B. super_write_vertical(0)
 C. super_write_vertical(100)
 D. super_write_vertical(1023)
 Consider this method declaration:
void quiz(int i)
{
if (i > 1)
{
quiz(i / 2);
quiz(i / 2);
}
System.out.print("*");
}
How many asterisks are printed by the method call quiz(5)?
 A. 3
 B. 4
 C. 7
 D. 8
 E. Some other number

This question is appropriate if you studied a flood fill (which was
not part of the text).
Suppose that a flood fill starts at the point marked with an o in this diagram:
XXXXXXXXXX
XX XXXX This is row number 1
XX XX XXXX This is row number 2
XX o XXX This is row number 3
XXXXXXXXXX
Suppose that the first recursive call is always left; the second recursive
call is always right; the third recursive call is always up; the fourth
recursive call is always down.
How will the rows be completely filled?
 A. Row 1 is filled first, then row 2, then row 3
 B. Row 1 is filled first, then row 3, then row 2
 C. Row 2 is filled first, then row 3, then row 1
 D. Row 3 is filled first, then row 1, then row 2
 E. Row 3 is filled first, then row 2, then row 1

In a real computer, what will happen if you make a recursive call without
making the problem smaller?
 A. The operating system detects the infinite recursion because
of the "repeated state"
 B. The program keeps running until you press CtrlC
 C. The results are nondeterministic
 D. The runtime stack overflows, halting the program

When the compiler compiles your program, how is a recursive call
treated differently than a nonrecursive method call?
 A. Primitive values are all treated as reference variables
 B. Reference variables are all treated as primitive values
 C. There is no duplication of local variables
 D. None of the above

When a method call is executed, which information is not saved
in the activation record?
 A. Current depth of recursion.
 B. Formal parameters.
 C. Location where the method should return when done.
 D. Local variables.

Consider the following method:
public static void test_a(int n)
{
System.out.println(n + " ");
if (n>0)
test_a(n2);
}
What is printed by the call test_a(4)?
 A. 0 2 4
 B. 0 2
 C. 2 4
 D. 4 2
 E. 4 2 0

Consider the following method:
public static void test_b(int n)
{
if (n>0)
test_b(n2);
System.out.println(n + " ");
}
What is printed by the call test_b(4)?
 A. 0 2 4
 B. 0 2
 C. 2 4
 D. 4 2
 E. 4 2 0
Multiple Choice Section 8.2 Fractals and Mazes


Suppose you are exploring a rectangular maze containing 10 rows and
20 columns. What is the maximum
number of calls to traverse_maze
that can be generated if you start at the entrance and call traverse_maze?

Suppose you are exploring a rectangular maze containing 10 rows and
20 columns. What is the maximum
depth of recursion that can result
if you start at the entrance and call traverse_maze?

What is the relationship between the maximum depth of recursion for
traverse_maze and the length of an actual path found from the
entrance to the tapestry?
 A. The maximum depth is always less than or equal to the path length.
 B. The maximum depth is always equal to the path length.
 C. The maximum depth is always greater than or equal to the path length.
 D. None of the above relationships are always true.
Multiple Choice Section 8.3 Reasoning about Recursion


What would a suitable variant expression be for the traverse_maze
method which could be used to prove termination? Assume N is the
number of rows in the maze and M is the number of columns.
 A. N + M
 B. N + M + 1
 C. N * M
 D. The number of unexplored spaces in the maze.

What technique is often used to prove the correctness
of a recursive method?
 A. Communitivity.
 B. Diagonalization.
 C. Mathematical induction.
 D. Matrix Multiplication.