Short Answers Section 9.1 Recursive Functions


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

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

Implement the following function. Do not use any local variables or loops.
void pattern(unsigned 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 function with two unsigned int parameters, m and n.
The precondition requires 0 <= m and m <= n.
The function 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. 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 function to meet this specification:
bool 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 function with this prototype (using the string type from
the new C++ String class):
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 function prints second). Some string member functions that will help you
for a String s:
 s[s.length( )  1] is a copy of the last character of s.
 s.length( ) is the length of s.
 cout << s << endl; will print s.
 s = c + s; will insert the character c at the front of s.
 s += c; will append the character c to the end of s.
 s.erase(0, 1); will remove one character from the front of s.
 s.erase(s.length( )1, 1) will remove the last character from s.

Write a function with this prototype:
#include <strclass.h>
void numbers(ostream& outs, const string& prefix, unsigned int levels);
The function prints output to the ostream outs.
The output consists 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
function would print 81 strings. In this case, the function
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).
The string class from <string> has many manipulation functions, but
you'll need only 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 + c) + '.';
This new string s can be passed as a parameter to recursive calls of the
function.
Short Answers Section 9.2 Fractals and Mazes

 Write a function with one positive int parameter called n.
The function 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 function:
bool dead_end()
// 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).
// Library facilities used: useful.h (from Appendix 1).
{
return inquire("Are you facing a wall?")

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

 What two properties must a variant expression have to guarantee
that a recursive function terminates?
Multiple Choice Section 9.1 Recursive Functions


In a single function 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 function may make?
 A. 1
 B. 2
 C. n (where n is the argument)
 D. There is no fixed maximum

Consider the following function:
void super_write_vertical(int number)
// Postcondition: The digits of the number have been written,
// stacked vertically. If number is negative, then a negative
// sign appears on top.
// Library facilities used: iostream.h, math.h
{
if (number < 0)
{
cout << '' << endl;
super_write_vertical(abs(number));
}
else if (number < 10)
cout << number << endl;
else
{
super_write_vertical(number/10);
cout << number % 10 << endl;
}
}
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 function:
void super_write_vertical(int number)
// Postcondition: The digits of the number have been written,
// stacked vertically. If number is negative, then a negative
// sign appears on top.
// Library facilities used: iostream.h, math.h
{
if (number < 0)
{
cout << '' << endl;
super_write_vertical(abs(number));
}
else if (number < 10)
cout << number << endl;
else
{
super_write_vertical(number/10);
cout << number % 10 << endl;
}
}
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 function declaration:
void quiz(int i)
{
if (i > 1)
{
quiz(i / 2);
quiz(i / 2);
}
cout << "*";
}
How many asterisks are printed by the function 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 function call?
 A. Parameters are all treated as reference arguments
 B. Parameters are all treated as value arguments
 C. There is no duplication of local variables
 D. None of the above

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

Consider the following function:
void test_a(int n)
{
cout << 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 function:
void test_b(int n)
{
if (n>0)
test_b(n2);
cout << 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 9.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 9.3 Reasoning about Recursion


What would a suitable variant expression be for the traverse_maze
function 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 function?
 A. Communitivity.
 B. Diagonalization.
 C. Mathematical induction.
 D. Matrix Multiplication.