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.
Question 1: Identify a recursive decomposition
Examine the method below. Assume 0 <= n <= 20.
1public static int oddSum(int n) {
2 if (n == 0) {
3 return 0;
4 } // if
5 return (2 * n - 1) + oddSum(n - 1);
6} // oddSum
Identify the base case and the smaller subproblem.
What quantity decreases on every recursive call?
What work remains after that call completes?
Determine the results of
oddSum(0)andoddSum(3). What does the method compute for other values ofnin the stated range?
Solution
The base case is n == 0. It returns with 0 because there are
no odd numbers to add. The smaller subproblem is the sum of the first
n - 1 positive odd integers. The nonnegative argument decreases
by one on each recursive call, so it eventually reaches zero.
After oddSum(n - 1) completes, its result is added to
2 * n - 1, the next odd integer. Thus, oddSum(0) produces
0, and oddSum(3) produces 5 + 3 + 1 + 0, which is 9.
In general, the method computes the sum of the first n positive
odd integers.
Question 2: Compare the output order
Assume 0 <= n <= 20 for both methods below. Each number is printed
on its own line; neither method should print zero.
1public static void before(int n) {
2 if (n == 0) {
3 return;
4 } // if
5 System.out.println(n);
6 before(n - 1);
7} // before
8
9public static void after(int n) {
10 if (n == 0) {
11 return;
12 } // if
13 after(n - 1);
14 System.out.println(n);
15} // after
Write the output of before(3) and after(3) separately. Explain
why the two outputs have different orders. What does each method
print when called with zero?
Solution
Each tree records the calls made during the trace. Each line connects a caller to a call it begins. Read sibling calls from left to right, completing each call and its descendants before beginning the next sibling.
In before, each call prints its argument before beginning the
smaller subproblem. In after, each call waits for its recursive
call to complete before printing its own argument. The pending
print operations therefore execute as the calls finish.
Both calls with zero return without printing anything. A void
method returns without a value; it does not return with zero.
Question 3: Track the active frames
Consider visit(3) using the method below:
1public static void visit(int n) {
2 if (n == 0) {
3 return;
4 } // if
5 int saved = n + 10;
6 visit(n - 1);
7 System.out.println(saved);
8} // visit
Immediately after visit(0) begins, but before its if executes,
list the active visit frames from oldest to newest. Record n
and the value of saved in each frame, or say that its initializer
has not executed. Then predict the complete output of visit(3).
Explain why beginning another call does not overwrite the caller's
saved value.
Solution
The active calls at the specified pause point are:
Call |
|
|
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
Initializer has not executed |
Each method invocation has its own parameter and local variables.
The first three calls are suspended at their recursive calls with
their own saved values. The base-case call returns before
reaching the declaration of saved. The remaining calls resume
from newest to oldest and print:
11
12
13
Question 4: Starting a call or resuming a caller
Trace outer(2) using the methods below. Count only calls to
outer and helper; exclude the driver and library methods.
1public static void outer(int n) {
2 if (n == 0) {
3 return;
4 } // if
5 helper(n);
6 outer(n - 1);
7 System.out.println(-n);
8} // outer
9
10public static void helper(int n) {
11 System.out.println(n);
12} // helper
List the calls in the order they begin.
Immediately after
helper(1)completes, which call resumes? Which new call begins next?List the calls in the order they complete, then write the output.
Solution
The numbered lists count only outer and helper calls.
The trees also show their println calls. Read sibling calls
from left to right, completing each call and its descendants
before beginning the next sibling.
After helper(1) completes, the existing outer(1) call
resumes. It then begins a new call to outer(0). Resuming
outer(1) does not create another frame for that call.
The helper calls print before the recursive outer calls. Each
negative value is printed after its corresponding recursive call
completes. The complete output is:
2
1
-1
-2
Question 5: Repair a call that makes no progress
The following method should compute the sum from zero through n
for 0 <= n <= 20, but its recursive case is incorrect.
1public static int total(int n) {
2 if (n == 0) {
3 return 0;
4 } // if
5 return n + total(n);
6} // total
Use total(2) to explain the defect without running the faulty
method. Change one expression to repair it. Explain why the repaired
method reaches its base case, then determine total(0) and
total(4).
Solution
total(2) calls total(2) again. The pending addition cannot
finish, and each new call receives the same argument. Having a
base case is insufficient when the recursive path never reaches
it. Executing this path repeatedly would exhaust the available
call stack.
Replace total(n) in the recursive case with total(n - 1):
return n + total(n - 1);
For a positive argument, subtracting one produces a smaller
nonnegative argument. Eventually the argument is zero, where the
method returns with 0. The repaired method produces 0 for
total(0) and 10 for total(4).
Question 6: Recover results while unwinding
Assume 0 <= n <= 20 for this method. Its result fits in a long.
1public static long factorial(int n) {
2 if (n == 0) {
3 return 1;
4 } // if
5 return n * factorial(n - 1);
6} // factorial
Trace factorial(4). For each call, record the multiplication
waiting for its recursive result and the value supplied when that
call completes. Explain why replacing return 1; with
System.out.println(1); would not provide the required base-case
result. What should factorial(0) produce?
Solution
The calls have these pending operations and completed results:
Call |
Pending operation |
Result |
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
None |
|
The base-case call completes first. The waiting calls then use
their recursive results to compute 1, 2, 6, and 24.
Printing changes the output; it does not supply a value to the
caller or finish the current method call. With the proposed
replacement, execution at zero would continue to the recursive
return statement and call factorial(-1).
factorial(0) must return with 1, the multiplicative identity.
Question 7: Count a character recursively
Write public static int countChar(String text, char target).
It must return with the number of occurrences of target in
text. Assume text is a short ASCII string whose reference
value is not null, and target is an ASCII character. The empty
string is allowed.
Use recursion over a shorter suffix; do not use a loop or a stream.
Explain the base case and how the current character contributes to
the result. Check your method against these test cases. Each
text entry shows the contents of the referenced string.
|
|
|
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Solution
1public static int countChar(String text, char target) {
2 if (text.length() == 0) {
3 return 0;
4 } // if
5 int current = 0;
6 if (text.charAt(0) == target) {
7 current = 1;
8 } // if
9 return current + countChar(text.substring(1), target);
10} // countChar
An empty string contains zero matches. Otherwise, current
records whether the first character matches. The recursive call
counts matches in the suffix with that character removed. Adding
those contributions counts each character once.
The method produces each result in the test-case table. The empty
check occurs before charAt(0), so an empty string is never
indexed.
Question 8: Count decimal digits
Write public static int digits(int n) for a nonnegative int.
It must return with the number of digits in the usual decimal
representation of n. In particular, zero has one digit.
Use recursion and integer division by ten. Do not convert the number to a string or use a loop. Explain how the recursive argument becomes smaller. Check your method against these test cases:
|
|
|---|---|
|
|
|
|
|
|
|
|
Solution
1public static int digits(int n) {
2 if (n < 10) {
3 return 1;
4 } // if
5 return 1 + digits(n / 10);
6} // digits
Every nonnegative integer below ten has one digit, including zero. For a larger value, integer division by ten removes its last decimal digit. The recursive call counts the remaining digits, and adding one accounts for the removed digit.
The method produces each result in the test-case table. Removing a zero digit still contributes one to the count.
Question 9: Find the first matching index
Write the recursive helper
public static int firstIndex(int[] values, int target, int index).
Assume values is a short array whose reference value is not
null and 0 <= index <= values.length. The method must return
with the smallest index at or after index whose element equals
target, or -1 when that suffix contains no match. It must not
change the array or use a loop.
Explain why the array bounds check must come first. Check your method
against these test cases. Each values entry shows the contents of
the referenced array.
|
|
|
|
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Solution
1public static int firstIndex(int[] values, int target, int index) {
2 if (index == values.length) {
3 return -1;
4 } // if
5 if (values[index] == target) {
6 return index;
7 } // if
8 return firstIndex(values, target, index + 1);
9} // firstIndex
An index equal to the array length denotes an empty suffix. The
method returns with -1 before attempting to read an element.
Otherwise, the current element is the earliest remaining
candidate. A match can be supplied immediately; a nonmatch leaves
only the suffix beginning at index + 1 to search.
The method produces each result in the test-case table. Although
index grows, the number of elements left to inspect decreases
on every recursive call.
Question 10: Compare a recursion tree and a call stack
Use the sum and sumOfSums methods from
Tracing Calls Across Two Methods to trace sumOfSums(3).
Count only invocations of those two methods; exclude the driver and
library methods. Count a base-case invocation as a call and as an
active frame until it completes.
Draw the recursion tree and determine the final result.
How many method calls begin during the computation?
What is the maximum number of simultaneously active example-method frames? Give a stack snapshot that reaches this depth.
Explain why the total-call count differs from the maximum depth. What are these two counts for
sumOfSums(0)?
Solution
The recursion tree is:
There are four sumOfSums invocations and nine sum
invocations, for a total of thirteen. The result is
6 + 3 + 1 + 0, which is 10.
The maximum depth is five frames. One snapshot, from oldest to newest, is:
sumOfSums(3)
sum(3)
sum(2)
sum(1)
sum(0)
Java evaluates the left operand of + before the right operand.
Thus, sum(3) completes before sumOfSums(2) begins. Later
branches can reuse stack space released by completed calls.
Thirteen calls begin over the whole computation, but at most five
are active at once. sumOfSums(0) has one call and a maximum
depth of one frame; it returns with 0 without calling sum.
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.
|
Printed output of |
|---|---|
|
No output |
|
|
|
|
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.
|
Printed output of |
|---|---|
|
No output |
|
|
|
|
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.
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.
|
Printed output of |
|---|---|
|
No output |
|
1 |
|
1234 |
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.
|
Printed output of |
|---|---|
|
No output |
|
1 |
|
1234 |
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.
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.
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.
|
|
|
|
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.
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.
|
|
|
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
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.
|
|
|
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
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.
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
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.
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.
|
|
|---|---|
|
|
|
|
|
|
|
|
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.