Due to the print book page limit, we cannot inlcude all good CheckPoint questions in the physical book. The CheckPoint on this Website may contain extra questions not printed in the book. The questions in some sections may have been reordered as a result. Nevertheless, it is easy to find the CheckPoint questions in the book on this Website. Please send suggestions and errata to Dr. Liang at y.daniel.liang@gmail.com. Indicate the book, edition, and question number in your email. Thanks!

Chapter 18 Check Point Questions

Section 18.2
▼18.2.1
What is a recursive method? What is an infinite recursion?
▼18.2.2
How many times is the factorial method in Listing 18.1 invoked for factorial(6)?
▼18.2.3
Show the output of the following programs and identify base cases and recursive calls. 
(a)
public class Test {
  public static void main(String[] args) {
    System.out.println(
      "Sum is " + xMethod(5));
  }

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

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

  public static void xMethod(int n) {
    if (n > 0) {
      System.out.print(n % 10);
      xMethod(n / 10);
    }
  }
}
▼18.2.4
Write a recursive mathematical definition for computing 2 n for a positive integer n.
▼18.2.5
Write a recursive mathematical definition for computing x n for a positive integer n and a real number x.
▼18.2.6
Write a recursive mathematical definition for computing 1 + 2 + 3 + ... + n for a positive integer n.
Section 18.3
▼18.3.1
Show the output of the following two programs: 
(a)
public class Test {
  public static void main(String[] args) {
    xMethod(5);
  }

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

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

  public static void xMethod(int n) {
    if (n > 0) {
      xMethod(n - 1);
      System.out.print(n + " ");
    }
  }
}
▼18.3.2
What is wrong in the following method? 
(a)
public class Test {
  public static void main(String[] args) {
    xMethod(1234567);
  }

  public static void xMethod(double n) {
    if (n != 0) {
      System.out.print(n);
      xMethod(n / 10);
    }
  }
}

(b)
public class Test { 
  public static void main(String[] args) {
    Test test = new Test();
    System.out.println(test.toString());
  }

  public Test() {
    Test test = new Test();
  }
}
▼18.3.3
How many times is the fib method in Listing 18.2 invoked for fib(6)?
Section 18.4
▼18.4.1
Describe the characteristics of recursive methods.
▼18.4.2
For the isPalindrome method in Listing 18.3, what are the base cases? How many times is this method called when invoking isPalindrome("abdxcxdba")?
▼18.4.3
Show the call stack for isPalindrome("abcba") using the method defined in Listing 18.3.
Section 18.5
▼18.5.1
Show the call stack for isPalindrome("abcba") using the method defined in Listing 18.4.
▼18.5.2
Show the call stack for selectionSort(new double[]{2, 3, 5, 1}) using the method defined in Listing 18.5.
▼18.5.3
What is a recursive helper method?
Section 18.6
▼18.6.1
What is the base case for the getSize method?
▼18.6.2
How does the program get all files and directories under a given directory?
▼18.6.3
How many times will the getSize method be invoked for a directory if the directory has three subdirectories and each subdirectory has four files?
▼18.6.4
Will the program work if the directory is empty (i.e., it does not contain any files)?
▼18.6.5
Will the program work if line 20 is replaced by the following code? 
for (int i = 0; i < files.length; i++)
▼18.6.6
Will the program work if lines 20-21 is replaced by the following code? 
for (File file: files) 
  size += getSize(file); // Recursive call
Section 18.7
▼18.7.1
How many times is the moveDisks method in Listing 18.8 invoked for moveDisks(5, 'A', 'B', 'C')?
Section 18.8
▼18.8.1
How do you obtain the midpoint between two points?
▼18.8.2
What is the base case for the displayTriangles method?
▼18.8.3
How many times is the displayTriangles method invoked for a Sierpinski triangle of order 0, order 1, order 2, and order n?
▼18.8.4
What happens if you enter a negative order? How do you fix this problem in the code?
▼18.8.5
Instead of drawing a triangle using a polygon, rewrite the code to draw a triangle by drawing three lines to connect the points in lines 71-77.
Section 18.9
▼18.9.1
Which of the following statements are true?
a. Any recursive method can be converted into a nonrecursive method.
b. Recursive methods take more time and memory to execute than nonrecursive methods.
c. Recursive methods are always simpler than nonrecursive methods.
d. There is always a selection statement in a recursive method to check whether a base case is reached.
▼18.9.2
What is a cause for a stack-overflow exception?
Section 18.10
▼18.10.1
Identify tail-recursive methods in this chapter.
▼18.10.2
Rewrite the fib method in Listing 18.2 using tail recursion.