Exam Questions - Recursion Ch9

Chapter 9 - Recursion

True/False (9)

1. The program stack stores activation records chronologically.
2. Recursive method calls create multiple copies of the method in memory.
3. A recursive method uses less memory than an iterative method.
4. You can use a recurrence relation to determine the performance of a recursive method.
5. Recursive methods do not return a value.
6. Activation records for recursive methods are the same as activation records for non-recursive methods.
7. You should always trace a recursive method to ensure it is correct.
8. Converting a tail-recursive method to an iterative method is usually a straightforward process.
9. You can replace recursion with iteration by simulating the program stack.

Short Answer (6)

1. What is the value returned from the following method when it is called with the value 9?
   
   int mystery (int n)
   {
   if (n < 1)
   return 0;
   else if (n % 2 == 0)
   return mystery(n-1);
   else return 1 + mystery(n-1);
   }
2. What does the following method compute?
   
   int mystery (int n)
   {
   if (n < 1)
   return 0;
   else if (n % 2 == 0)
   return mystery(n-1);
   else return 1 + mystery(n-1);
   }
3. What is the value returned from the following method when it is called with the value 5?
   
   int mystery(int x, int y)
   {
   if (y == 0)
   return 1;
   if (y == 1)
   return x;
   return x mystery(x, y-1);
   }
4. What does the following method compute?
   
   int mystery(int x, int y)
   {
   if (y == 0)
   return 1;
   if (y == 1)
   return x;
   return x mystery(x, y-1);
   }
5. What does the following method compute?

boolean mystery(int[] x, int b, int c)
{
if (b > 0)
if (x[b-1] == c)
return true;
else
return mystery(x, b-1, c);
return false;
}

1. What does the following method compute?
   
   int mystery(int[] x, int b, int c)
   {
   if (b > 0)
   if (x[b-1] == c)
   return b-1;
   else
   return mystery(x, b-1, c);
   return -1;
   }
   
   

Multiple Choice (23) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. A method that calls itself is called a
   1. recursive method
   2. base method
   3. iterative method
   4. dynamic method
2. The condition when a recursive method does not satisfy a base case it is called
   1. infinite recursion
   2. finite recursion
   3. iterative recursion
   4. baseless recursion
3. When too many recursive calls are made creating more activation records than the allocated program memory can handle, what kind of error occurs?
   1. stack overflow
   2. activation record overflow
   3. recursive overflow
   4. infinite recursion
4. What happens when a recursive method does not reach the base case?
   1. the program crashes
   2. a stack overflow occurs
   3. both a & b
   4. none of the above
      
5. Recursion can be used to solve problems like
   1. processing linked chains
   2. processing arrays
   3. sorting
   4. all of the above
6. Recursive methods
   1. are useful when each recursive all is a solution to a smaller, identical problem
   2. do not use an if-statement
   3. are not useful in programming
   4. all of the above
7. Recursive methods need a(n)
   1. base case
   2. for loop
   3. trace
   4. all of the above
8. What question(s) should you keep in mind when debugging a recursive method?
   1. Is there at least one recursive call?
   2. Did you consider all possible cases?
   3. Does the method contain a statement to test an input value and leads to different cases?
   4. All of the above.
9. What question(s) should you keep in mind when debugging a recursive method?
   1. Does each base case produce a result that is correct for that case?
   2. Are there enough base cases?
   3. Is at least one of the cases a base case that has no recursive call?
   4. All of the above.
10. What question(s) should you keep in mind when debugging a recursive method?
    1. If the method returns a value, does each of the cases return a value?
    2. Should a for-loop be included in the method?
    3. Are the activation records correct?
    4. All of the above.
11. A recursive method that processes a chain of linked nodes
    1. uses the first node in the chain
    2. uses the last node in the chain
    3. divides the chain in half placing the middle node in the left chain
    4. divides the chain in half placing the middle node in the right chain
12. Traversing a chain of linked nodes
    1. is easier to do recursively than iteratively
    2. is easier to do iteratively than recursively
    3. is impossible to do recursively
    4. is easy to do iteratively
13. To determine the efficiency of a recursive method you need to solve a(n)
    1. recurrence relation
    2. recursive relation
    3. quadratic equation
    4. base case
14. The efficiency for recursively traversing a chain of linked nodes is
    1. O(n)
    2. O(1)
    3. O(n²)
    4. it cannot be proven
15. The efficiency for recursively calculating xⁿ is
    1. O(log n)
    2. O(n log n)
    3. O(n)
    4. O(n2)
16. When the last action in a recursive method is a recursive call, it is called
    1. tail recursion
    2. final recursion
    3. delayed recursion
    4. latent recursion
17. When method X calls method Y, method Y calls method Z, and method Z calls method X, this is called
    1. indirect recursion
    2. mutual recursion
    3. tail recursion
    4. an error
18. When method X calls method Y, and method Y calls method X, this is called
    1. mutual recursion
    2. tail recursion
    3. associative recursion
    4. an error
19. What is the output of the following program when the method is called with 4?
    
    void unknown(int n)
    {
    System.out.print("?");
    if (n > 0)
    unknown(n-1);
    }
    1. ?????
    2. ????
    3. ???
    4. none of the above
20. What is the output of the following program when the method is called with 4?
    
    void unknown(int n)
    {
    if (n > 0)
    {
    System.out.print("?");
    unknown(n-1);
    }
    }
    1. ????
    2. ?????
    3. ???
    4. none of the above
21. What is the output of the following program when the method is called with 4?
    
    void unknown(int n)
    {
    if (n > 0)
    unknown(n-1);
    System.out.print("?");
    }
    1. ?????
    2. ????
    3. ???
    4. none of the above
22. How many recursive calls will be made if the following method is called with 6?
    
    void greeting(int n)
    {
    System.out.println("Hello!");
    greeting(n-1);
    }
    1. infinitely
    2. 7
    3. 6
    4. 5
23. How many recursive calls will be made if the following method is called with 6?
    
    void greeting(int n)
    {
    if (n > 0)
    {
    System.out.println("Hello!");
    greeting(n+1);
    }
    }
    1. infinitely
    2. 7
    3. 6
    4. 5