17.9. Additional Practice Exercises

17.9.1. Practice Problems

Practice Problems

To see sample solutions, click on the "Configure activity" button and select "Show solutions" from the menu that appears.

Sample solutions not included, because "Show solutions" was not selected before printing.

Try each question before opening its solution. For each recursive method, identify the base case, the smaller subproblem, and the work that remains after the recursive call completes. Review Problems and Sub-problems, Recursive Count Up, or Tracing Calls Across Two Methods as needed.

The method fragments below belong inside a class. Unless a question says otherwise, assume that inputs satisfy its stated preconditions. Use small inputs when experimenting so that the calls do not exhaust the call stack.

17.9.2. Parsons Problems

Parsons Problems

To see sample solutions, click on the "Configure activity" button and select "Show solutions" from the menu that appears.

Sample solutions not included, because "Show solutions" was not selected before printing.

Each problem asks for a recursive method body. The method declaration belongs to the surrounding class and is not a movable block. Use every correct block once and leave the incorrect blocks unused. Do not add loops or replace the requested recursion with a library shortcut.

Arrange blocks vertically. The blocks show indentation relative to the left edge of the method body; add the enclosing method's indentation when inserting the fragment into a class. Preserve relative indentation within each block. Problems 8 through 10 also ask you to fill blanks.

Use the interactive controls or open the text version to work on paper or without JavaScript. Letters identify whole blocks. Try each problem before opening its sample solution. Use Show Solutions to hide or show the solution dropdowns, including when printing.

17.9.2.1. Problem 1: Print a countdown

Construct the body of public static void countDown(int n). Assume 0 <= n <= 20. Use recursion to print the integers from n down through 1 on one line, each followed by one space, without ending the line. For zero, print nothing. Quotation marks in the table show where the printed text starts and ends; they are not printed.

Table 17.4 Test cases for countDown

n

Printed output of countDown(n)

0

No output

1

"1 "

4

"4 3 2 1 "

Text version of Problem 1 (inline)

Construct the body of public static void countDown(int n). Assume 0 <= n <= 20. Use recursion to print the integers from n down through 1 on one line, each followed by one space, without ending the line. For zero, print nothing. Quotation marks in the table show where the printed text starts and ends; they are not printed.

Test cases for countDown

n

Printed output of countDown(n)

0

No output

1

"1 "

4

"4 3 2 1 "

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

countDown(n - 1);

Block B

countDown(n);

Block C

System.out.print(n + " ");

Block D

if (n <= 1) {
    return;
} // if

Block E

if (n == 0) {
    return;
} // if
Sample solution for Problem 1 (inline)

Block order: E, C, A.

if (n == 0) {
    return;
} // if
System.out.print(n + " ");
countDown(n - 1);

The zero case completes without printing. For a positive argument, print the current value and its trailing space before solving the smaller countdown. No call ends the line, so every value appears on the same line. The argument decreases by one until it reaches zero. Stopping at 1 would omit 1; passing n again would make no progress.

Unused Blocks
Solution Construction

Text version of Problem 1

Construct the body of public static void countDown(int n). Assume 0 <= n <= 20. Use recursion to print the integers from n down through 1 on one line, each followed by one space, without ending the line. For zero, print nothing. Quotation marks in the table show where the printed text starts and ends; they are not printed.

Test cases for countDown

n

Printed output of countDown(n)

0

No output

1

"1 "

4

"4 3 2 1 "

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

countDown(n - 1);

Block B

countDown(n);

Block C

System.out.print(n + " ");

Block D

if (n <= 1) {
    return;
} // if

Block E

if (n == 0) {
    return;
} // if

Text version of Problem 1

Construct the body of public static void countDown(int n). Assume 0 <= n <= 20. Use recursion to print the integers from n down through 1 on one line, each followed by one space, without ending the line. For zero, print nothing. Quotation marks in the table show where the printed text starts and ends; they are not printed.

Test cases for countDown

n

Printed output of countDown(n)

0

No output

1

"1 "

4

"4 3 2 1 "

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

countDown(n - 1);

Block B

countDown(n);

Block C

System.out.print(n + " ");

Block D

if (n <= 1) {
    return;
} // if

Block E

if (n == 0) {
    return;
} // if

Sample solution for Problem 1

Block order: E, C, A.

if (n == 0) {
    return;
} // if
System.out.print(n + " ");
countDown(n - 1);

The zero case completes without printing. For a positive argument, print the current value and its trailing space before solving the smaller countdown. No call ends the line, so every value appears on the same line. The argument decreases by one until it reaches zero. Stopping at 1 would omit 1; passing n again would make no progress.

Sample solution for Problem 1

Block order: E, C, A.

if (n == 0) {
    return;
} // if
System.out.print(n + " ");
countDown(n - 1);

The zero case completes without printing. For a positive argument, print the current value and its trailing space before solving the smaller countdown. No call ends the line, so every value appears on the same line. The argument decreases by one until it reaches zero. Stopping at 1 would omit 1; passing n again would make no progress.

17.9.2.2. Problem 2: Print a countup

Construct the body of public static void countUp(int n). Assume 0 <= n <= 20. Print the integers from 1 through n, one per line, using recursion. For zero, print nothing.

Table 17.5 Test cases for countUp

n

Printed output of countUp(n)

0

No output

1

1

4

1
2
3
4
Text version of Problem 2 (inline)

Construct the body of public static void countUp(int n). Assume 0 <= n <= 20. Print the integers from 1 through n, one per line, using recursion. For zero, print nothing.

Test cases for countUp

n

Printed output of countUp(n)

0

No output

1

1

4

1
2
3
4

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

System.out.println(n);

Block B

countUp(n - 2);

Block C

countUp(n - 1);

Block D

if (n <= 1) {
    return;
} // if

Block E

if (n == 0) {
    return;
} // if
Sample solution for Problem 2 (inline)

Block order: E, C, A.

if (n == 0) {
    return;
} // if
countUp(n - 1);
System.out.println(n);

The smaller countup must complete before the current call prints n. Each suspended call keeps its own parameter value, so the printing occurs in ascending order as calls complete. Stopping at 1 omits 1. Subtracting two skips required values and misses zero for positive odd inputs.

Unused Blocks
Solution Construction

Text version of Problem 2

Construct the body of public static void countUp(int n). Assume 0 <= n <= 20. Print the integers from 1 through n, one per line, using recursion. For zero, print nothing.

Test cases for countUp

n

Printed output of countUp(n)

0

No output

1

1

4

1
2
3
4

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

System.out.println(n);

Block B

countUp(n - 2);

Block C

countUp(n - 1);

Block D

if (n <= 1) {
    return;
} // if

Block E

if (n == 0) {
    return;
} // if

Text version of Problem 2

Construct the body of public static void countUp(int n). Assume 0 <= n <= 20. Print the integers from 1 through n, one per line, using recursion. For zero, print nothing.

Test cases for countUp

n

Printed output of countUp(n)

0

No output

1

1

4

1
2
3
4

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

System.out.println(n);

Block B

countUp(n - 2);

Block C

countUp(n - 1);

Block D

if (n <= 1) {
    return;
} // if

Block E

if (n == 0) {
    return;
} // if

Sample solution for Problem 2

Block order: E, C, A.

if (n == 0) {
    return;
} // if
countUp(n - 1);
System.out.println(n);

The smaller countup must complete before the current call prints n. Each suspended call keeps its own parameter value, so the printing occurs in ascending order as calls complete. Stopping at 1 omits 1. Subtracting two skips required values and misses zero for positive odd inputs.

Sample solution for Problem 2

Block order: E, C, A.

if (n == 0) {
    return;
} // if
countUp(n - 1);
System.out.println(n);

The smaller countup must complete before the current call prints n. Each suspended call keeps its own parameter value, so the printing occurs in ascending order as calls complete. Stopping at 1 omits 1. Subtracting two skips required values and misses zero for positive odd inputs.

17.9.2.3. Problem 3: Compute a sum

Construct the body of public static int sum(int n). Assume 0 <= n <= 20. Use recursion to compute the sum of the integers from zero through n. The method must return with that int value and print nothing.

Table 17.6 Test cases for sum

n

sum(n)

0

0

1

1

5

15

20

210

Text version of Problem 3 (inline)

Construct the body of public static int sum(int n). Assume 0 <= n <= 20. Use recursion to compute the sum of the integers from zero through n. The method must return with that int value and print nothing.

Test cases for sum

n

sum(n)

0

0

1

1

5

15

20

210

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return n + rest;

Block B

return n;

Block C

int rest = sum(n - 1);

Block D

if (n == 0) {
    return 1;
} // if

Block E

if (n == 0) {
    return 0;
} // if
Sample solution for Problem 3 (inline)

Block order: E, C, A.

if (n == 0) {
    return 0;
} // if
int rest = sum(n - 1);
return n + rest;

Zero is the base-case result for this sum. The recursive call computes the sum through n - 1, and the caller adds n to that result. A base result of 1 adds an unwanted 1 to every answer. Returning only n loses the contribution of the smaller problem.

Unused Blocks
Solution Construction

Text version of Problem 3

Construct the body of public static int sum(int n). Assume 0 <= n <= 20. Use recursion to compute the sum of the integers from zero through n. The method must return with that int value and print nothing.

Test cases for sum

n

sum(n)

0

0

1

1

5

15

20

210

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return n + rest;

Block B

return n;

Block C

int rest = sum(n - 1);

Block D

if (n == 0) {
    return 1;
} // if

Block E

if (n == 0) {
    return 0;
} // if

Text version of Problem 3

Construct the body of public static int sum(int n). Assume 0 <= n <= 20. Use recursion to compute the sum of the integers from zero through n. The method must return with that int value and print nothing.

Test cases for sum

n

sum(n)

0

0

1

1

5

15

20

210

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return n + rest;

Block B

return n;

Block C

int rest = sum(n - 1);

Block D

if (n == 0) {
    return 1;
} // if

Block E

if (n == 0) {
    return 0;
} // if

Sample solution for Problem 3

Block order: E, C, A.

if (n == 0) {
    return 0;
} // if
int rest = sum(n - 1);
return n + rest;

Zero is the base-case result for this sum. The recursive call computes the sum through n - 1, and the caller adds n to that result. A base result of 1 adds an unwanted 1 to every answer. Returning only n loses the contribution of the smaller problem.

Sample solution for Problem 3

Block order: E, C, A.

if (n == 0) {
    return 0;
} // if
int rest = sum(n - 1);
return n + rest;

Zero is the base-case result for this sum. The recursive call computes the sum through n - 1, and the caller adds n to that result. A base result of 1 adds an unwanted 1 to every answer. Returning only n loses the contribution of the smaller problem.

17.9.2.4. Problem 4: Compute factorial

Construct the body of public static long factorial(int n). Assume 0 <= n <= 20, so the factorial fits in a long. Use recursion and return with the factorial value without printing. Remember that the factorial of zero is 1.

Table 17.7 Test cases for factorial

n

factorial(n)

0

1

1

1

5

120

20

2432902008176640000

Text version of Problem 4 (inline)

Construct the body of public static long factorial(int n). Assume 0 <= n <= 20, so the factorial fits in a long. Use recursion and return with the factorial value without printing. Remember that the factorial of zero is 1.

Test cases for factorial

n

factorial(n)

0

1

1

1

5

120

20

2432902008176640000

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return n * rest;

Block B

return n + rest;

Block C

long rest = factorial(n - 1);

Block D

if (n == 0) {
    return 0;
} // if

Block E

if (n == 0) {
    return 1;
} // if
Sample solution for Problem 4 (inline)

Block order: E, C, A.

if (n == 0) {
    return 1;
} // if
long rest = factorial(n - 1);
return n * rest;

The base result is 1, the multiplicative identity. Each caller multiplies its own n by the long result from the next call. Using zero at the base destroys the product; adding produces a different sequence. Keeping rest as a long also makes the multiplication use long arithmetic.

Unused Blocks
Solution Construction

Text version of Problem 4

Construct the body of public static long factorial(int n). Assume 0 <= n <= 20, so the factorial fits in a long. Use recursion and return with the factorial value without printing. Remember that the factorial of zero is 1.

Test cases for factorial

n

factorial(n)

0

1

1

1

5

120

20

2432902008176640000

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return n * rest;

Block B

return n + rest;

Block C

long rest = factorial(n - 1);

Block D

if (n == 0) {
    return 0;
} // if

Block E

if (n == 0) {
    return 1;
} // if

Text version of Problem 4

Construct the body of public static long factorial(int n). Assume 0 <= n <= 20, so the factorial fits in a long. Use recursion and return with the factorial value without printing. Remember that the factorial of zero is 1.

Test cases for factorial

n

factorial(n)

0

1

1

1

5

120

20

2432902008176640000

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return n * rest;

Block B

return n + rest;

Block C

long rest = factorial(n - 1);

Block D

if (n == 0) {
    return 0;
} // if

Block E

if (n == 0) {
    return 1;
} // if

Sample solution for Problem 4

Block order: E, C, A.

if (n == 0) {
    return 1;
} // if
long rest = factorial(n - 1);
return n * rest;

The base result is 1, the multiplicative identity. Each caller multiplies its own n by the long result from the next call. Using zero at the base destroys the product; adding produces a different sequence. Keeping rest as a long also makes the multiplication use long arithmetic.

Sample solution for Problem 4

Block order: E, C, A.

if (n == 0) {
    return 1;
} // if
long rest = factorial(n - 1);
return n * rest;

The base result is 1, the multiplicative identity. Each caller multiplies its own n by the long result from the next call. Using zero at the base destroys the product; adding produces a different sequence. Keeping rest as a long also makes the multiplication use long arithmetic.

17.9.2.5. Problem 5: Reverse a string

Construct the body of public static String reverse(String s). Assume s has a non-null reference value and the referenced string contains at most 20 ASCII characters. Empty strings are permitted. Use recursion to return with a reference to a string whose characters occur in reverse order. Do not use loops or a library reversal method. Each s and reverse(s) entry shows the contents of the referenced string.

Table 17.8 Test cases for reverse

s

reverse(s)

""

""

"a"

"a"

"ab"

"ba"

"desk"

"ksed"

Text version of Problem 5 (inline)

Construct the body of public static String reverse(String s). Assume s has a non-null reference value and the referenced string contains at most 20 ASCII characters. Empty strings are permitted. Use recursion to return with a reference to a string whose characters occur in reverse order. Do not use loops or a library reversal method. Each s and reverse(s) entry shows the contents of the referenced string.

Test cases for reverse

s

reverse(s)

""

""

"a"

"a"

"ab"

"ba"

"desk"

"ksed"

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

String rev = reverse(r);

Block B

String f = s.substring(0, 1);
String r = s;

Block C

String f = s.substring(0, 1);
String r = s.substring(1);

Block D

return rev + f;

Block E

return f + rev;

Block F

if (s.length() <= 1) {
    return s;
} // if
Sample solution for Problem 5 (inline)

Block order: F, C, A, D.

if (s.length() <= 1) {
    return s;
} // if
String f = s.substring(0, 1);
String r = s.substring(1);
String rev = reverse(r);
return rev + f;

A string of length zero or one needs no reversal. Otherwise, the two substring calls separate the first character from the remaining suffix: f refers to the first-character string, and r refers to the suffix. These independent declarations stay together in one block. The call reverse(r) returns with a reference value for the reversed suffix, stored in rev. Concatenating rev + f places the first character at the end.

The suffix is shorter by one character. Assigning s to r makes no progress, and concatenating f + rev places the first character at the wrong end. The ASCII contract keeps the exercise within the character behavior covered by the chapter.

Unused Blocks
Solution Construction

Text version of Problem 5

Construct the body of public static String reverse(String s). Assume s has a non-null reference value and the referenced string contains at most 20 ASCII characters. Empty strings are permitted. Use recursion to return with a reference to a string whose characters occur in reverse order. Do not use loops or a library reversal method. Each s and reverse(s) entry shows the contents of the referenced string.

Test cases for reverse

s

reverse(s)

""

""

"a"

"a"

"ab"

"ba"

"desk"

"ksed"

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

String rev = reverse(r);

Block B

String f = s.substring(0, 1);
String r = s;

Block C

String f = s.substring(0, 1);
String r = s.substring(1);

Block D

return rev + f;

Block E

return f + rev;

Block F

if (s.length() <= 1) {
    return s;
} // if

Text version of Problem 5

Construct the body of public static String reverse(String s). Assume s has a non-null reference value and the referenced string contains at most 20 ASCII characters. Empty strings are permitted. Use recursion to return with a reference to a string whose characters occur in reverse order. Do not use loops or a library reversal method. Each s and reverse(s) entry shows the contents of the referenced string.

Test cases for reverse

s

reverse(s)

""

""

"a"

"a"

"ab"

"ba"

"desk"

"ksed"

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

String rev = reverse(r);

Block B

String f = s.substring(0, 1);
String r = s;

Block C

String f = s.substring(0, 1);
String r = s.substring(1);

Block D

return rev + f;

Block E

return f + rev;

Block F

if (s.length() <= 1) {
    return s;
} // if

Sample solution for Problem 5

Block order: F, C, A, D.

if (s.length() <= 1) {
    return s;
} // if
String f = s.substring(0, 1);
String r = s.substring(1);
String rev = reverse(r);
return rev + f;

A string of length zero or one needs no reversal. Otherwise, the two substring calls separate the first character from the remaining suffix: f refers to the first-character string, and r refers to the suffix. These independent declarations stay together in one block. The call reverse(r) returns with a reference value for the reversed suffix, stored in rev. Concatenating rev + f places the first character at the end.

The suffix is shorter by one character. Assigning s to r makes no progress, and concatenating f + rev places the first character at the wrong end. The ASCII contract keeps the exercise within the character behavior covered by the chapter.

Sample solution for Problem 5

Block order: F, C, A, D.

if (s.length() <= 1) {
    return s;
} // if
String f = s.substring(0, 1);
String r = s.substring(1);
String rev = reverse(r);
return rev + f;

A string of length zero or one needs no reversal. Otherwise, the two substring calls separate the first character from the remaining suffix: f refers to the first-character string, and r refers to the suffix. These independent declarations stay together in one block. The call reverse(r) returns with a reference value for the reversed suffix, stored in rev. Concatenating rev + f places the first character at the end.

The suffix is shorter by one character. Assigning s to r makes no progress, and concatenating f + rev places the first character at the wrong end. The ASCII contract keeps the exercise within the character behavior covered by the chapter.

17.9.2.6. Problem 6: Sum decimal digits

Construct the body of public static int sumDigits(int n). Assume n is a nonnegative int. Use recursion to compute the sum of its decimal digits and return with that int value. Integer division by 10 removes the last digit; remainder by 10 extracts it. Do not convert the number to a string.

Table 17.9 Test cases for sumDigits

n

sumDigits(n)

0

0

7

7

507

12

1000

1

Text version of Problem 6 (inline)

Construct the body of public static int sumDigits(int n). Assume n is a nonnegative int. Use recursion to compute the sum of its decimal digits and return with that int value. Integer division by 10 removes the last digit; remainder by 10 extracts it. Do not convert the number to a string.

Test cases for sumDigits

n

sumDigits(n)

0

0

7

7

507

12

1000

1

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return n % 10 + sumDigits(r);

Block B

int r = n % 10;

Block C

int r = n / 10;

Block D

if (n < 10) {
    return 0;
} // if

Block E

if (n < 10) {
    return n;
} // if
Sample solution for Problem 6 (inline)

Block order: E, C, A.

if (n < 10) {
    return n;
} // if
int r = n / 10;
return n % 10 + sumDigits(r);

Other accepted arrangements may also be valid.

For a single digit, the digit sum is that digit. For a longer number, n / 10 is the smaller number and n % 10 is its removed last digit. Add the last digit to the smaller number's digit sum. A zero base result loses the leading digit. Recursing on the remainder counts the last digit again and loses the preceding digits. Computing r before checking the base case is also valid; the base case still completes before the recursive call.

Unused Blocks
Solution Construction

Text version of Problem 6

Construct the body of public static int sumDigits(int n). Assume n is a nonnegative int. Use recursion to compute the sum of its decimal digits and return with that int value. Integer division by 10 removes the last digit; remainder by 10 extracts it. Do not convert the number to a string.

Test cases for sumDigits

n

sumDigits(n)

0

0

7

7

507

12

1000

1

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return n % 10 + sumDigits(r);

Block B

int r = n % 10;

Block C

int r = n / 10;

Block D

if (n < 10) {
    return 0;
} // if

Block E

if (n < 10) {
    return n;
} // if

Text version of Problem 6

Construct the body of public static int sumDigits(int n). Assume n is a nonnegative int. Use recursion to compute the sum of its decimal digits and return with that int value. Integer division by 10 removes the last digit; remainder by 10 extracts it. Do not convert the number to a string.

Test cases for sumDigits

n

sumDigits(n)

0

0

7

7

507

12

1000

1

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return n % 10 + sumDigits(r);

Block B

int r = n % 10;

Block C

int r = n / 10;

Block D

if (n < 10) {
    return 0;
} // if

Block E

if (n < 10) {
    return n;
} // if

Sample solution for Problem 6

Block order: E, C, A.

if (n < 10) {
    return n;
} // if
int r = n / 10;
return n % 10 + sumDigits(r);

Other accepted arrangements may also be valid.

For a single digit, the digit sum is that digit. For a longer number, n / 10 is the smaller number and n % 10 is its removed last digit. Add the last digit to the smaller number's digit sum. A zero base result loses the leading digit. Recursing on the remainder counts the last digit again and loses the preceding digits. Computing r before checking the base case is also valid; the base case still completes before the recursive call.

Sample solution for Problem 6

Block order: E, C, A.

if (n < 10) {
    return n;
} // if
int r = n / 10;
return n % 10 + sumDigits(r);

Other accepted arrangements may also be valid.

For a single digit, the digit sum is that digit. For a longer number, n / 10 is the smaller number and n % 10 is its removed last digit. Add the last digit to the smaller number's digit sum. A zero base result loses the leading digit. Recursing on the remainder counts the last digit again and loses the preceding digits. Computing r before checking the base case is also valid; the base case still completes before the recursive call.

17.9.2.7. Problem 7: Count matches in an array suffix

Construct the body of public static int count(int[] a, int i, int t). Assume a has a non-null reference value, its array has at most 20 elements, and 0 <= i <= a.length. Count occurrences of t from i through the last element, using recursion. Return with the count and leave the array unchanged. An empty suffix has count zero. Each a entry shows the contents of the referenced array.

Table 17.10 Test cases for count

a

i

t

count(a, i, t)

{4, 2, 4}

0

4

2

{4, 2, 4}

1

4

1

{4, 2, 4}

2

4

1

{4, 2, 4}

3

4

0

{}

0

4

0

{4, 2, 4}

0

7

0

Text version of Problem 7 (inline)

Construct the body of public static int count(int[] a, int i, int t). Assume a has a non-null reference value, its array has at most 20 elements, and 0 <= i <= a.length. Count occurrences of t from i through the last element, using recursion. Return with the count and leave the array unchanged. An empty suffix has count zero. Each a entry shows the contents of the referenced array.

Test cases for count

a

i

t

count(a, i, t)

{4, 2, 4}

0

4

2

{4, 2, 4}

1

4

1

{4, 2, 4}

2

4

1

{4, 2, 4}

3

4

0

{}

0

4

0

{4, 2, 4}

0

7

0

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

if (a[i] == t) {
    n++;
} // if

Block B

if (i >= a.length - 1) {
    return 0;
} // if

Block C

int n = count(a, i + 1, t);

Block D

return n;

Block E

if (a[i] == t) {
    n = 1;
} // if

Block F

if (i == a.length) {
    return 0;
} // if
Sample solution for Problem 7 (inline)

Block order: F, C, A, D.

if (i == a.length) {
    return 0;
} // if
int n = count(a, i + 1, t);
if (a[i] == t) {
    n++;
} // if
return n;

The empty suffix begins at a.length. Count matches in the rest of the suffix, then include the current element if it matches. The last element is not an empty suffix. Incrementing preserves all later matches; assigning 1 would forget them. Each call advances the index by one, and no block modifies an array element.

Unused Blocks
Solution Construction

Text version of Problem 7

Construct the body of public static int count(int[] a, int i, int t). Assume a has a non-null reference value, its array has at most 20 elements, and 0 <= i <= a.length. Count occurrences of t from i through the last element, using recursion. Return with the count and leave the array unchanged. An empty suffix has count zero. Each a entry shows the contents of the referenced array.

Test cases for count

a

i

t

count(a, i, t)

{4, 2, 4}

0

4

2

{4, 2, 4}

1

4

1

{4, 2, 4}

2

4

1

{4, 2, 4}

3

4

0

{}

0

4

0

{4, 2, 4}

0

7

0

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

if (a[i] == t) {
    n++;
} // if

Block B

if (i >= a.length - 1) {
    return 0;
} // if

Block C

int n = count(a, i + 1, t);

Block D

return n;

Block E

if (a[i] == t) {
    n = 1;
} // if

Block F

if (i == a.length) {
    return 0;
} // if

Text version of Problem 7

Construct the body of public static int count(int[] a, int i, int t). Assume a has a non-null reference value, its array has at most 20 elements, and 0 <= i <= a.length. Count occurrences of t from i through the last element, using recursion. Return with the count and leave the array unchanged. An empty suffix has count zero. Each a entry shows the contents of the referenced array.

Test cases for count

a

i

t

count(a, i, t)

{4, 2, 4}

0

4

2

{4, 2, 4}

1

4

1

{4, 2, 4}

2

4

1

{4, 2, 4}

3

4

0

{}

0

4

0

{4, 2, 4}

0

7

0

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

if (a[i] == t) {
    n++;
} // if

Block B

if (i >= a.length - 1) {
    return 0;
} // if

Block C

int n = count(a, i + 1, t);

Block D

return n;

Block E

if (a[i] == t) {
    n = 1;
} // if

Block F

if (i == a.length) {
    return 0;
} // if

Sample solution for Problem 7

Block order: F, C, A, D.

if (i == a.length) {
    return 0;
} // if
int n = count(a, i + 1, t);
if (a[i] == t) {
    n++;
} // if
return n;

The empty suffix begins at a.length. Count matches in the rest of the suffix, then include the current element if it matches. The last element is not an empty suffix. Incrementing preserves all later matches; assigning 1 would forget them. Each call advances the index by one, and no block modifies an array element.

Sample solution for Problem 7

Block order: F, C, A, D.

if (i == a.length) {
    return 0;
} // if
int n = count(a, i + 1, t);
if (a[i] == t) {
    n++;
} // if
return n;

The empty suffix begins at a.length. Count matches in the rest of the suffix, then include the current element if it matches. The last element is not an empty suffix. Incrementing preserves all later matches; assigning 1 would forget them. Each call advances the index by one, and no block modifies an array element.

17.9.2.8. Problem 8: Find a suffix maximum

Construct the body of public static int maximum(int[] a, int i). Assume a has a non-null reference value, its array has 1 through 20 elements, and 0 <= i < a.length. Use recursion to return with the largest value in the nonempty suffix starting at i. Leave the array unchanged. Values may all be negative. Fill each blank with the integer literal that selects the last element or advances to the next element. Each a entry shows the contents of the referenced array.

Table 17.11 Test cases for maximum

a

i

maximum(a, i)

{3, 9, 5}

0

9

{9, 3, 5}

1

5

{3, 9, 5}

2

5

{-4, -2, -7}

0

-2

Text version of Problem 8 (inline)

Construct the body of public static int maximum(int[] a, int i). Assume a has a non-null reference value, its array has 1 through 20 elements, and 0 <= i < a.length. Use recursion to return with the largest value in the nonempty suffix starting at i. Leave the array unchanged. Values may all be negative. Fill each blank with the integer literal that selects the last element or advances to the next element. Each a entry shows the contents of the referenced array.

Test cases for maximum

a

i

maximum(a, i)

{3, 9, 5}

0

9

{9, 3, 5}

1

5

{3, 9, 5}

2

5

{-4, -2, -7}

0

-2

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return Math.max(a[i], m);

Block B

return Math.min(a[i], m);

Block C

int j = i + ___;
int m = maximum(a, j);

Block D

if (i == a.length - 1) {
    return 0;
} // if

Block E

if (i == a.length - ___) {
    return a[i];
} // if
Sample solution for Problem 8 (inline)

Block order: E, C, A.

if (i == a.length - 1) {
    return a[i];
} // if
int j = i + 1;
int m = maximum(a, j);
return Math.max(a[i], m);

Both blanks are 1. A one-element suffix has its element as its maximum. A longer suffix combines its first element with the maximum of the remaining suffix. Zero is not a valid default when every value is negative, and selecting the minimum reverses the required comparison.

Unused Blocks
Solution Construction

Text version of Problem 8

Construct the body of public static int maximum(int[] a, int i). Assume a has a non-null reference value, its array has 1 through 20 elements, and 0 <= i < a.length. Use recursion to return with the largest value in the nonempty suffix starting at i. Leave the array unchanged. Values may all be negative. Fill each blank with the integer literal that selects the last element or advances to the next element. Each a entry shows the contents of the referenced array.

Test cases for maximum

a

i

maximum(a, i)

{3, 9, 5}

0

9

{9, 3, 5}

1

5

{3, 9, 5}

2

5

{-4, -2, -7}

0

-2

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return Math.max(a[i], m);

Block B

return Math.min(a[i], m);

Block C

int j = i + ___;
int m = maximum(a, j);

Block D

if (i == a.length - 1) {
    return 0;
} // if

Block E

if (i == a.length - ___) {
    return a[i];
} // if

Text version of Problem 8

Construct the body of public static int maximum(int[] a, int i). Assume a has a non-null reference value, its array has 1 through 20 elements, and 0 <= i < a.length. Use recursion to return with the largest value in the nonempty suffix starting at i. Leave the array unchanged. Values may all be negative. Fill each blank with the integer literal that selects the last element or advances to the next element. Each a entry shows the contents of the referenced array.

Test cases for maximum

a

i

maximum(a, i)

{3, 9, 5}

0

9

{9, 3, 5}

1

5

{3, 9, 5}

2

5

{-4, -2, -7}

0

-2

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

return Math.max(a[i], m);

Block B

return Math.min(a[i], m);

Block C

int j = i + ___;
int m = maximum(a, j);

Block D

if (i == a.length - 1) {
    return 0;
} // if

Block E

if (i == a.length - ___) {
    return a[i];
} // if

Sample solution for Problem 8

Block order: E, C, A.

if (i == a.length - 1) {
    return a[i];
} // if
int j = i + 1;
int m = maximum(a, j);
return Math.max(a[i], m);

Both blanks are 1. A one-element suffix has its element as its maximum. A longer suffix combines its first element with the maximum of the remaining suffix. Zero is not a valid default when every value is negative, and selecting the minimum reverses the required comparison.

Sample solution for Problem 8

Block order: E, C, A.

if (i == a.length - 1) {
    return a[i];
} // if
int j = i + 1;
int m = maximum(a, j);
return Math.max(a[i], m);

Both blanks are 1. A one-element suffix has its element as its maximum. A longer suffix combines its first element with the maximum of the remaining suffix. Zero is not a valid default when every value is negative, and selecting the minimum reverses the required comparison.

17.9.2.9. Problem 9: Check a palindrome

Construct the body of public static boolean palindrome(String s, int i, int j). Assume s has a non-null reference value and the referenced string contains at most 20 ASCII characters. The initial call uses i = 0 and j = s.length() - 1. Use recursion to return with true exactly when this interval reads the same in both directions. The empty string is a palindrome. Comparison is case-sensitive. Fill the first blank with the comparison operator that recognizes both a single-character interval and crossed indices. Fill the other blanks with the integer literal that moves each endpoint inward by one. Each s entry shows the contents of the referenced string.

Table 17.12 Test cases for palindrome

s

palindrome(s, 0, s.length() - 1)

""

true

"a"

true

"abba"

true

"racecar"

true

"abca"

false

"Aa"

false

Text version of Problem 9 (inline)

Construct the body of public static boolean palindrome(String s, int i, int j). Assume s has a non-null reference value and the referenced string contains at most 20 ASCII characters. The initial call uses i = 0 and j = s.length() - 1. Use recursion to return with true exactly when this interval reads the same in both directions. The empty string is a palindrome. Comparison is case-sensitive. Fill the first blank with the comparison operator that recognizes both a single-character interval and crossed indices. Fill the other blanks with the integer literal that moves each endpoint inward by one. Each s entry shows the contents of the referenced string.

Test cases for palindrome

s

palindrome(s, 0, s.length() - 1)

""

true

"a"

true

"abba"

true

"racecar"

true

"abca"

false

"Aa"

false

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

i += ___;
j -= ___;
return palindrome(s, i, j);

Block B

return true;

Block C

char a = s.charAt(i);
char b = s.charAt(j);
if (a != b) {
    return false;
} // if

Block D

if (i >= j) {
    return false;
} // if

Block E

if (i ___ j) {
    return true;
} // if
Sample solution for Problem 9 (inline)

Block order: E, C, A.

if (i >= j) {
    return true;
} // if
char a = s.charAt(i);
char b = s.charAt(j);
if (a != b) {
    return false;
} // if
i += 1;
j -= 1;
return palindrome(s, i, j);

Use >= for the first blank and 1 for both endpoint changes. Check the base case before accessing characters: crossed indices occur for the empty interval. Unequal endpoints disprove a palindrome; equal endpoints leave the smaller interior to check. Advance i and decrease j before the recursive call. For example, "abca" has matching endpoints but is not a palindrome. Returning immediately after matching the endpoints would miss that interior mismatch.

Unused Blocks
Solution Construction

Text version of Problem 9

Construct the body of public static boolean palindrome(String s, int i, int j). Assume s has a non-null reference value and the referenced string contains at most 20 ASCII characters. The initial call uses i = 0 and j = s.length() - 1. Use recursion to return with true exactly when this interval reads the same in both directions. The empty string is a palindrome. Comparison is case-sensitive. Fill the first blank with the comparison operator that recognizes both a single-character interval and crossed indices. Fill the other blanks with the integer literal that moves each endpoint inward by one. Each s entry shows the contents of the referenced string.

Test cases for palindrome

s

palindrome(s, 0, s.length() - 1)

""

true

"a"

true

"abba"

true

"racecar"

true

"abca"

false

"Aa"

false

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

i += ___;
j -= ___;
return palindrome(s, i, j);

Block B

return true;

Block C

char a = s.charAt(i);
char b = s.charAt(j);
if (a != b) {
    return false;
} // if

Block D

if (i >= j) {
    return false;
} // if

Block E

if (i ___ j) {
    return true;
} // if

Text version of Problem 9

Construct the body of public static boolean palindrome(String s, int i, int j). Assume s has a non-null reference value and the referenced string contains at most 20 ASCII characters. The initial call uses i = 0 and j = s.length() - 1. Use recursion to return with true exactly when this interval reads the same in both directions. The empty string is a palindrome. Comparison is case-sensitive. Fill the first blank with the comparison operator that recognizes both a single-character interval and crossed indices. Fill the other blanks with the integer literal that moves each endpoint inward by one. Each s entry shows the contents of the referenced string.

Test cases for palindrome

s

palindrome(s, 0, s.length() - 1)

""

true

"a"

true

"abba"

true

"racecar"

true

"abca"

false

"Aa"

false

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

i += ___;
j -= ___;
return palindrome(s, i, j);

Block B

return true;

Block C

char a = s.charAt(i);
char b = s.charAt(j);
if (a != b) {
    return false;
} // if

Block D

if (i >= j) {
    return false;
} // if

Block E

if (i ___ j) {
    return true;
} // if

Sample solution for Problem 9

Block order: E, C, A.

if (i >= j) {
    return true;
} // if
char a = s.charAt(i);
char b = s.charAt(j);
if (a != b) {
    return false;
} // if
i += 1;
j -= 1;
return palindrome(s, i, j);

Use >= for the first blank and 1 for both endpoint changes. Check the base case before accessing characters: crossed indices occur for the empty interval. Unequal endpoints disprove a palindrome; equal endpoints leave the smaller interior to check. Advance i and decrease j before the recursive call. For example, "abca" has matching endpoints but is not a palindrome. Returning immediately after matching the endpoints would miss that interior mismatch.

Sample solution for Problem 9

Block order: E, C, A.

if (i >= j) {
    return true;
} // if
char a = s.charAt(i);
char b = s.charAt(j);
if (a != b) {
    return false;
} // if
i += 1;
j -= 1;
return palindrome(s, i, j);

Use >= for the first blank and 1 for both endpoint changes. Check the base case before accessing characters: crossed indices occur for the empty interval. Unequal endpoints disprove a palindrome; equal endpoints leave the smaller interior to check. Advance i and decrease j before the recursive call. For example, "abca" has matching endpoints but is not a palindrome. Returning immediately after matching the endpoints would miss that interior mismatch.

17.9.2.10. Problem 10: Combine results across two methods

Assume the following helper is already declared:

public static int sum(int n) {
    if (n == 0) {
        return 0;
    } // if
    return n + sum(n - 1);
} // sum

Construct only the body of public static int sumOfSums(int n). Assume 0 <= n <= 20. Use recursion to compute sum(0) + sum(1) + ... + sum(n) and return with that int value. Fill the blanks with the method names that compute the current sum and the remaining sum of sums. The two local-variable declarations may appear in either order.

Table 17.13 Test cases for sumOfSums

n

sumOfSums(n)

0

0

1

1

2

4

4

20

Text version of Problem 10 (inline)

Assume the following helper is already declared:

public static int sum(int n) {
    if (n == 0) {
        return 0;
    } // if
    return n + sum(n - 1);
} // sum

Construct only the body of public static int sumOfSums(int n). Assume 0 <= n <= 20. Use recursion to compute sum(0) + sum(1) + ... + sum(n) and return with that int value. Fill the blanks with the method names that compute the current sum and the remaining sum of sums. The two local-variable declarations may appear in either order.

Test cases for sumOfSums

n

sumOfSums(n)

0

0

1

1

2

4

4

20

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

int r = ___(n - 1);

Block B

int c = n;

Block C

int c = ___(n);

Block D

return c + r;

Block E

int r = sum(n - 1);

Block F

if (n == 0) {
    return 0;
} // if
Sample solution for Problem 10 (inline)

Block order: F, C, A, D.

if (n == 0) {
    return 0;
} // if
int c = sum(n);
int r = sumOfSums(n - 1);
return c + r;

Other accepted arrangements may also be valid.

The blanks are sum and sumOfSums. The first computes the current contribution; the second computes all earlier contributions. Adding them gives the requested sum of sums. The base case is zero. Using just n loses most of the current sum. Using sum(n - 1) loses the still smaller sums. Either declaration order gives the same final result because these calls have no side effects; their call-entry order does change. Computing c before the base check is also valid: sum(0) is defined and has no side effects. The base check must still occur before the recursive sumOfSums call.

Unused Blocks
Solution Construction

Text version of Problem 10

Assume the following helper is already declared:

public static int sum(int n) {
    if (n == 0) {
        return 0;
    } // if
    return n + sum(n - 1);
} // sum

Construct only the body of public static int sumOfSums(int n). Assume 0 <= n <= 20. Use recursion to compute sum(0) + sum(1) + ... + sum(n) and return with that int value. Fill the blanks with the method names that compute the current sum and the remaining sum of sums. The two local-variable declarations may appear in either order.

Test cases for sumOfSums

n

sumOfSums(n)

0

0

1

1

2

4

4

20

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

int r = ___(n - 1);

Block B

int c = n;

Block C

int c = ___(n);

Block D

return c + r;

Block E

int r = sum(n - 1);

Block F

if (n == 0) {
    return 0;
} // if

Text version of Problem 10

Assume the following helper is already declared:

public static int sum(int n) {
    if (n == 0) {
        return 0;
    } // if
    return n + sum(n - 1);
} // sum

Construct only the body of public static int sumOfSums(int n). Assume 0 <= n <= 20. Use recursion to compute sum(0) + sum(1) + ... + sum(n) and return with that int value. Fill the blanks with the method names that compute the current sum and the remaining sum of sums. The two local-variable declarations may appear in either order.

Test cases for sumOfSums

n

sumOfSums(n)

0

0

1

1

2

4

4

20

Write the letters of the correct blocks in order. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

int r = ___(n - 1);

Block B

int c = n;

Block C

int c = ___(n);

Block D

return c + r;

Block E

int r = sum(n - 1);

Block F

if (n == 0) {
    return 0;
} // if

Sample solution for Problem 10

Block order: F, C, A, D.

if (n == 0) {
    return 0;
} // if
int c = sum(n);
int r = sumOfSums(n - 1);
return c + r;

Other accepted arrangements may also be valid.

The blanks are sum and sumOfSums. The first computes the current contribution; the second computes all earlier contributions. Adding them gives the requested sum of sums. The base case is zero. Using just n loses most of the current sum. Using sum(n - 1) loses the still smaller sums. Either declaration order gives the same final result because these calls have no side effects; their call-entry order does change. Computing c before the base check is also valid: sum(0) is defined and has no side effects. The base check must still occur before the recursive sumOfSums call.

Sample solution for Problem 10

Block order: F, C, A, D.

if (n == 0) {
    return 0;
} // if
int c = sum(n);
int r = sumOfSums(n - 1);
return c + r;

Other accepted arrangements may also be valid.

The blanks are sum and sumOfSums. The first computes the current contribution; the second computes all earlier contributions. Adding them gives the requested sum of sums. The base case is zero. Using just n loses most of the current sum. Using sum(n - 1) loses the still smaller sums. Either declaration order gives the same final result because these calls have no side effects; their call-entry order does change. Computing c before the base check is also valid: sum(0) is defined and has no side effects. The base check must still occur before the recursive sumOfSums call.