Sample Data Structures Questions
Chapter 8
Recursive Thinking

Data Structures and Other Objects Using Java (Second Edition)
by Michael Main
ISBN 0-201-74093-1, Softcover, 808 pages, 2003

The Purpose of These Questions

Short Answers

Short Answers Section 8.1 Recursive Methods

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

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

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

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

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

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

8. Write a method with one positive int parameter called n. The method 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 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

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

Multiple Choice

Multiple Choice Section 8.1 Recursive Methods

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

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

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

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

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

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

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

10. Consider the following method:

    
        public static void test_a(int n)
    
        {
    
           System.out.println(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 method:

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

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 8.3 Reasoning about Recursion

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

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