Sample Data Structures Questions
Chapter 9
Recursive Thinking

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000

The Purpose of These Questions

Short Answers

Short Answers Section 9.1 Recursive Functions

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

2. 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.

3. 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
   

4. 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 n-1, 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.

5. 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):
   1. If n is even, then you may give back exactly n/2 bears.
   2. 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 next-to-last digit is ((n%100)/10).
   3. 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).
   

6. 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.

7. 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

8. Write a function with one positive int parameter called n. The function will write 2^n-1 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 n-1, followed by n itself, followed by a second copy of the output for n-1.

9. What property of fractals lends itself to recursive thinking?

10. 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?

11. 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

12. What two properties must a variant expression have to guarantee that a recursive function terminates?

Multiple Choice

Multiple Choice Section 9.1 Recursive Functions

1. 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

2. 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

3. 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

4. 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)

5. 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

6. 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

7. 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 Ctrl-C
   • C. The results are nondeterministic
   • D. The run-time stack overflows, halting the program

8. When the compiler compiles your program, how is a recursive call treated differently than a non-recursive 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

9. 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.

10. Consider the following function:

        void test_a(int n)
        {
           cout << n << " ";
           if (n>0)
              test_a(n-2);
        }
    

    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

11. Consider the following function:

        void test_b(int n)
        {
           if (n>0)
              test_b(n-2);
           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

12. 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?
    • A. 10
    • B. 20
    • C. 30
    • D. 200

13. 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?
    • A. 10
    • B. 20
    • C. 30
    • D. 200

14. 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

15. 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.

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

Data Structures and Other Objects Using C++

Thank you for visiting http://www.cs.colorado.edu/~main/questions/chap09q.html
Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group