Introduction to Java Programming, Sixth Edtion

1 Which of the following statements are true?

A. Every recursive method must have a base case or a stopping condition.

B. Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.

C. Infinite recursion can occur if recursion does not reduce the problem in a manner that allows it to eventually converge into the base case.

D. Every recursive method must have a return value.

E. A recursive method is invoked differently from a non-recursive method.

2 Fill in the code to complete the following method for computing factorial.

   /** Return the factorial for a specified index */
   public static long factorial(int n) {
     if (n == 0) // Base case
       return 1;
     else
       return _____________; // Recursive call
   }

A. n * (n - 1)

B. n

C. n * factorial(n - 1)

D. factorial(n - 1) * n

3 Analyze the following recursive method.

   public static long factorial(int n) {
     return n * factorial(n - 1);
   }

A. Invoking factorial(0) returns 0.

B. Invoking factorial(1) returns 1.

C. Invoking factorial(2) returns 2.

D. Invoking factorial(3) returns 6.

E. The method runs infinitely and causes a StackOverflowError.

5 Which of the following statements are true?

A. The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the preceding two numbers in the series.

B. The Fibonacci series begins with 1 and 1, and each subsequent number is the sum of the preceding two numbers in the series.

C. The Fibonacci series begins with 1 and 2, and each subsequent number is the sum of the preceding two numbers in the series.

D. The Fibonacci series begins with 2 and 3, and each subsequent number is the sum of the preceding two numbers in the series.

6 How many times is the fib method in Listing 19.2 invoked for fib(5)?
f. 32
Hint: number of time fib is invoked in fib(5) = 1 + number of time fib is invoked in fib(3) + number of time fib is invoked in fib(4) = 1 + 5 + 9 = 15

A. 14

B. 15

D. 25

E. 31

7 Fill in the code to complete the following method for computing a Fibonnaci number.

   public static long fib(long index) {
     if (index == 0) // Base case
       return 0;
     else if (index == 1) // Base case
       return 1;
     else // Reduction and recursive calls
       return __________________;
   }

A. fib(index - 1)

B. fib(index - 2)

C. fib(index - 1) + fib(index - 2)

D. fib(index - 2) + fib(index - 1)

8 In the following method, what is the base case?

static int xMethod(int n) {
   if (n == 1)
     return 1;
   else
     return n + xMethod(n - 1);
}

A. n is 1.

B. n is greater than 1.

C. n is less than 1.

D. no base case.

9 What is the return value for xMethod(4) after calling the following method?

static int xMethod(int n) {
   if (n == 1)
     return 1;
   else
     return n + xMethod(n - 1);
}

A. 12

B. 11

C. 10

D. 9

10 Fill in the code to complete the following method for checking whether a string is a palindrome.

public static boolean isPalindrome(String s) {
   if (s.length() <= 1) // Base case
     return true;
   else if _____________________________
     return false;
   else
     return isPalindrome(s.substring(1, s.length() - 1));
}

A. (s.charAt(0) != s.charAt(s.length() - 1)) // Base case

B. (s.charAt(0) != s.charAt(s.length())) // Base case

C. (s.charAt(1) != s.charAt(s.length() - 1)) // Base case

D. (s.charAt(1) != s.charAt(s.length())) // Base case

11 Analyze the following code:

public class Test {
   public static void main(String[] args) {
     int[] x = {1, 2, 3, 4, 5};
     xMethod(x, 5);
   }

   public static void xMethod(int[] x, int length) {
     System.out.print(" " + x[length - 1]);
     xMethod(x, length - 1);
   }
}

A. The program displays 1 2 3 4 6.

B. The program displays 1 2 3 4 5 and then raises an ArrayIndexOutOfBoundsException.

C. The program displays 5 4 3 2 1.

D. The program displays 5 4 3 2 1 and then raises an ArrayIndexOutOfBoundsException.

12 Fill in the code to complete the following method for checking whether a string is a palindrome.

public static boolean isPalindrome(String s) {
   return isPalindrome(s, 0, s.length() - 1);
}

public static boolean isPalindrome(String s, int low, int high) {
   if (high <= low) // Base case
     return true;
   else if (s.charAt(low) != s.charAt(high)) // Base case
     return false;
   else
     return _______________________________;
}

A. isPalindrome(s)

B. isPalindrome(s, low, high)

C. isPalindrome(s, low + 1, high)

D. isPalindrome(s, low, high - 1)

E. isPalindrome(s, low + 1, high - 1)

13 Fill in the code to complete the following method for sorting a list.

public static void sort(double[] list) {
   ___________________________;
}

public static void sort(double[] list, int high) {
   if (high > 1) {
     // Find the largest number and its index
     int indexOfMax = 0;
     double max = list[0];
     for (int i = 1; i <= high; i++) {
       if (list[i] > max) {
         max = list[i];
         indexOfMax = i;
       }
     }

     // Swap the largest with the last number in the list
     list[indexOfMax] = list[high];
     list[high] = max;

     // Sort the remaining list
     sort(list, high - 1);
   }
}

A. sort(list)

B. sort(list, list.length)

C. sort(list, list.length - 1)

D. sort(list, list.length - 2)

14 Fill in the code to complete the following method for binary search.

public static int recursiveBinarySearch(int[] list, int key) {
   int low = 0;
   int high = list.length - 1;
   return __________________________;
}

public static int recursiveBinarySearch(int[] list, int key,
     int low, int high) {
   if (low > high) // The list has been exhausted without a match
     return -low - 1; // Return -insertion point - 1

   int mid = (low + high) / 2;
   if (key < list[mid])
     return recursiveBinarySearch(list, key, low, mid - 1);
   else if (key == list[mid])
     return mid;
   else
     return recursiveBinarySearch(list, key, mid + 1, high);
}

A. recursiveBinarySearch(list, key)

B. recursiveBinarySearch(list, key, low + 1, high - 1)

C. recursiveBinarySearch(list, key, low - 1, high + 1)

D. recursiveBinarySearch(list, key, low, high)

17 Analyze the following two programs:

A:

public class Test {
   public static void main(String[] args) {
     xMethod(5);
   }

   public static void xMethod(int length) {
     if (length > 1) {
       System.out.print((length - 1) + " ");
       xMethod(length - 1);
     }
   }
}

B:
public class Test {
   public static void main(String[] args) {
     xMethod(5);
   }

   public static void xMethod(int length) {
     while (length > 1) {
       System.out.print((length - 1) + " ");
       xMethod(length - 1);
     }
   }
}

A. The two programs produce the same output 5 4 3 2 1.

B. The two programs produce the same output 1 2 3 4 5.

C. The two programs produce the same output 4 3 2 1.

D. The two programs produce the same output 1 2 3 4.

E. Program A produces the output 4 3 2 1 and Program B prints 4 3 2 1 1 1 .... 1 infinitely.

18 The following program draws squares recursively. Fill in the missing code.

import javax.swing.*;
import java.awt.*;

public class Test extends JApplet {
   public Test() {
     add(new SquarePanel());
   }

   static class SquarePanel extends JPanel {
     public void paintComponent(Graphics g) {
       super.paintComponent(g);

       int width = (int)(Math.min(getWidth(), getHeight()) * 0.4);
       int centerx = getWidth() / 2;
       int centery = getHeight() / 2;

       displaySquares(g, width, centerx, centery);
     }

     private static void displaySquares(Graphics g, int width,
         int centerx, int centery) {
       if (width >= 20) {
         g.drawRect(centerx - width, centery - width, 2* width, 2 * width);
         displaySquares(_________, width - 20, centerx, centery);
       }
     }
   }
}

A. getGraphics()

B. newGraphics()

C. null

D. g

19 Which of the following statements are true?

A. Recursive methods run faster than non-recursive methods.

B. Recursive methods usually takes more memory space than non-recursive methods.

C. A recursive method can always be replaced by a non-recursive method.

D. In some cases, however, using recursion enables you to give a natural, straightforward, simple solution to a program that would otherwise be difficult to solve.

Introduction to Java Programming, Sixth Edition, Y. Daniel Liang

Chapter 19 Recursion