- For this recursive merge sort, what is the base case that stops further splitting of the array?
public class Sorter {
public static void mergeSort(int[] nums, int left, int right) {
// Base case: one element (or empty) segment is already sorted
if (left >= right) {
return;
}
int mid = (left + right) / 2;
// Recursive step: sort both halves
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// Merge sorted halves
merge(nums, left, mid, right);
}
private static void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
// Merge elements in sorted order
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
// Copy back
for (int t = 0; t < temp.length; t++) {
nums[left + t] = temp[t];
}
}
} Answer: When left >= right, return immediately.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on identifying the base case in recursive merge sort. The base case in merge sort represents when a segment is so small that it's already sorted by definition. In this implementation, the condition if (left >= right) serves as the base case, stopping recursion when the segment has one element (left == right) or is empty (left > right). Choice C is correct because when left >= right, the segment contains at most one element, which is inherently sorted and requires no further splitting or merging. Choice A is incorrect because it only covers the empty segment case (left > right) but misses the single-element case (left == right), which is also a valid base case. To help students: Explain that arrays of size 0 or 1 are sorted by definition. Trace through examples showing how recursive calls eventually reach segments where left equals right, representing single elements that form the building blocks for merging.
- The recursive method above is called on a sorted array of 7 elements with search(arr, target, 0, 6) where the target is NOT in the array. What is the time complexity of this search method?
Answer: O(n) because it may visit every element in the worst case scenario
This method searches both left AND right subarrays recursively, unlike proper binary search which chooses one direction. Even on a sorted array, this creates a pattern where many elements are visited multiple times. In the worst case (target not found), this approaches O(n) behavior because it explores both branches at each level rather than eliminating half the search space.
- How does this merge sort handle the input array in recursive steps before calling
merge?
public class Sorter {
// Sorts nums[left..right] by recursively sorting subranges
public static void mergeSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
// Recursive step: split into two index ranges
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// Merge step combines sorted ranges
merge(nums, left, mid, right);
}
private static void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
for (int t = 0; t < temp.length; t++) nums[left + t] = temp[t];
}
} Answer: It updates left/right to work on smaller index ranges.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on how merge sort manages array segments during recursion. Efficient sorting algorithms minimize memory usage by working with index ranges rather than creating array copies. In this merge sort implementation, the original array is passed to all recursive calls, but each call operates on a specific segment defined by the left and right indices, effectively dividing the work without copying data. Choice B is correct because it accurately describes how the algorithm updates the left and right parameters to define progressively smaller index ranges, allowing each recursive call to focus on its assigned portion of the array. Choice A is incorrect because copying the entire array at each recursive call would be extremely inefficient and unnecessary when index boundaries suffice. To help students: Use diagrams showing the same array with different colored segments representing the ranges each recursive call handles. Emphasize that changing indices is much more efficient than copying array elements, especially for large datasets.
- In the recursive binary search code, how does the algorithm handle the input array in recursive steps?
public static int binarySearch(int[] nums, int target, int low, int high) {
if (low > high) return -1;
int mid = (low + high) / 2;
if (nums[mid] == target) return mid;
if (target < nums[mid]) return binarySearch(nums, target, low, mid - 1);
return binarySearch(nums, target, mid + 1, high);
} Answer: It narrows to one half by updating low or high bounds
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding how binary search narrows its search space. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, binary search compares the target with the middle element and then recursively searches only the appropriate half by adjusting the low or high bounds. Choice C is correct because the algorithm narrows the search to one half of the current range by updating either the high bound to mid-1 (when target < nums[mid]) or the low bound to mid+1 (when target > nums[mid]). Choice B is incorrect because binary search's efficiency comes from eliminating half the search space each time, not searching both halves. To help students: Use a visual representation of an array with arrows showing how low and high bounds move inward. Trace through a specific example showing how the search range shrinks with each recursive call.
- The modified binary search method above returns the recursion depth when the target is found, or the negative depth when not found. For a sorted array of 16 elements, what is the maximum possible absolute value that could be returned?
Answer: 5, representing the depth when the search terminates unsuccessfully
When analyzing recursive algorithms, you need to carefully trace through how the depth parameter changes and when the method terminates.
Let's trace through this modified binary search for a 16-element array. The method starts with depth = 0 and increments it with each recursive call. In a standard binary search of 16 elements, you need at most 4 comparisons to find any element (since 24=16). However, this method continues one step further when the target isn't found.
Here's the key insight: when the target is found, the method returns the current depth, which will be at most 4 for a 16-element array. But when the target isn't found, the recursion continues until left > right, then returns -depth. This happens after one additional recursive call beyond where an element would have been found.
So the maximum depth occurs when searching unsuccessfully - the algorithm makes 4 comparisons to narrow down to where the element should be, then makes one final call that triggers the base case left > right, incrementing depth to 5. The method then returns -5, giving an absolute value of 5.
Choice A (4) represents the maximum depth when an element is found, but not the absolute maximum return value. Choice B (16) incorrectly assumes you examine all elements, which isn't how binary search works. Choice C (15) seems to confuse array bounds with recursion depth.
Remember: in recursive algorithm problems, always trace through both successful and unsuccessful cases - the maximum often occurs in the failure condition, not the success condition. - For the recursive binary search method below, what is the time complexity of the given recursive algorithm?
public class Searcher {
public static int binarySearch(int[] nums, int target, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (nums[mid] == target) {
return mid;
}
if (target < nums[mid]) {
return binarySearch(nums, target, low, mid - 1);
} else {
return binarySearch(nums, target, mid + 1, high);
}
}
} Answer: O(logn) because it halves the search interval each call.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on analyzing binary search's time complexity. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the binary search algorithm halves the search interval with each recursive call by adjusting either the low or high boundary based on the comparison with the middle element. Choice C is correct because binary search has O(log n) time complexity since each recursive call eliminates half of the remaining elements, requiring at most log₂(n) comparisons to find the target or determine it's not present. Choice A is incorrect because O(n) would mean checking every element, which only happens in the worst case of linear search, not binary search's efficient halving strategy. To help students: Show how a 16-element array requires at most 4 comparisons (log₂16 = 4). Create a table showing how the search space shrinks: 16→8→4→2→1, demonstrating the logarithmic pattern. - In the recursive binary search below, what is the base case that stops further recursive calls?
// Recursive binary search on a sorted int array
public static int binarySearch(int[] nums, int target, int low, int high) {
// Base case: range is empty
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
// Base case: target found
if (nums[mid] == target) {
return mid;
}
// Recursive step: search one half
if (target < nums[mid]) {
return binarySearch(nums, target, low, mid - 1);
} else {
return binarySearch(nums, target, mid + 1, high);
}
} Answer: When low is greater than high, return -1
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding the base case in recursive binary search. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the recursive binary search has two base cases: when low > high (empty range) and when nums[mid] == target (element found). Choice B is correct because it correctly identifies that when low is greater than high, the search range is empty and the function returns -1, preventing further recursive calls. Choice A is incorrect because when low equals high, there's still one element to check, so the recursion should continue. To help students: Emphasize that base cases prevent infinite recursion and handle edge conditions. Practice tracing through binary search with small arrays to see when low > high occurs, particularly after unsuccessful searches.
- In this recursive merge sort, how does the recursive call structure ensure the entire array becomes sorted?
public class Sorter {
public static void mergeSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
// Recursive calls sort subarrays
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// Merge combines two sorted subarrays
merge(nums, left, mid, right);
}
private static void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
for (int t = 0; t < temp.length; t++) nums[left + t] = temp[t];
}
} Answer: Each call sorts both halves, then merge combines them into one sorted segment.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding the divide-and-conquer strategy in merge sort. Merge sort works by recursively breaking down the problem into smaller subproblems until they're trivial to solve, then combining solutions. In this implementation, each call to mergeSort first recursively sorts the left half (left to mid), then the right half (mid+1 to right), and finally merges these two sorted halves into one sorted segment. Choice B is correct because it accurately describes the two-phase process: recursive calls sort both halves independently, then the merge function combines these sorted halves while maintaining order. Choice D is incorrect because merge sort must sort both halves, not just the left half, to ensure the entire array becomes sorted. To help students: Use tree diagrams to visualize the recursive decomposition and subsequent merging phases. Emphasize that the 'magic' happens in the merge step, which combines two sorted sequences into one larger sorted sequence.
- What is the time complexity of this recursive binary search on a sorted integer array of size n?
public class Searcher {
public static int binarySearch(int[] nums, int target, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (nums[mid] == target) {
return mid;
}
if (target < nums[mid]) {
return binarySearch(nums, target, low, mid - 1);
} else {
return binarySearch(nums, target, mid + 1, high);
}
}
} Answer: O(logn) because each call halves the interval.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on analyzing the time complexity of recursive binary search. Time complexity analysis requires understanding how the number of operations grows with input size n. In binary search, each recursive call eliminates half of the remaining elements by choosing to search either the left or right half based on the comparison with the middle element. Choice D is correct because the algorithm halves the search interval with each recursive call, resulting in at most log₂(n) recursive calls before the base case is reached, giving O(log n) time complexity. Choice A is incorrect because O(n) would mean checking every element, which contradicts binary search's divide-and-conquer approach that skips half the elements at each step. To help students: Draw recursion trees showing how the problem size decreases from n to n/2 to n/4, etc. Emphasize that the number of times you can divide n by 2 until reaching 1 is log₂(n), which is the maximum recursion depth. - In this recursive factorial method, what is the base case that prevents infinite recursion?
public class MathUtil {
// Computes n! for n >= 0
public static int factorial(int n) {
// Base case
if (n == 0) {
return 1;
}
// Recursive step: n! = n * (n-1)!
return n * factorial(n - 1);
}
} Answer: When n == 0, return 1.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on identifying base cases in simple recursive functions. The base case in recursion provides the termination condition and the simplest solution that doesn't require further recursive calls. In this factorial implementation, the base case if (n == 0) return 1 correctly implements the mathematical definition that 0! = 1, which also serves as the stopping point for the recursive calls. Choice C is correct because when n equals 0, the method returns 1, which both matches the mathematical definition of factorial and prevents further recursive calls. Choice D is incorrect because calling factorial(n) again when n == 0 would create infinite recursion, as the parameter wouldn't decrease. To help students: Explain that base cases must move toward termination and provide concrete values. Use the mathematical definition of factorial to justify why 0! = 1, and trace through small examples like 3! to show how recursion eventually reaches the base case.
- How does the recursive call in this factorial code compute the final result for input
n?
public class MathUtil {
public static int factorial(int n) {
if (n == 0) {
return 1;
}
// Recursive call multiplies by the factorial of the smaller problem
return n * factorial(n - 1);
}
} Answer: It multiplies n by the result of factorial(n - 1) until the base case.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding how recursive calls build up the final result. Recursive factorial demonstrates how solutions to smaller problems combine to solve larger ones. In this implementation, each recursive call computes n! by multiplying n with the factorial of (n-1), following the mathematical definition n! = n × (n-1)!. Choice B is correct because it accurately describes the recursive process: each call multiplies the current value n by the result of factorial(n-1), continuing until reaching the base case where factorial(0) returns 1. Choice A is incorrect because factorial involves multiplication, not addition, and the recursive structure multiplies values rather than adding them. To help students: Trace through a concrete example like factorial(4), showing the call stack and how return values propagate back up. Emphasize how each recursive call waits for the result of the next call before completing its multiplication and returning.
- The recursive method above searches for a target value in an array. If called with recursiveFind(arr, 7, 0) on the array [3, 1, 7, 2, 7, 9], what value is returned and how many total recursive calls are made?
Answer: Returns 2, makes 3 total calls including the initial call
When you encounter recursive methods that search through arrays, you need to trace through each recursive call step-by-step to understand both what gets returned and how many calls occur.
Let's trace recursiveFind(arr, 7, 0) on array [3, 1, 7, 2, 7, 9]:
Call 1: index = 0, arr[0] = 3. Since 3 ≠ 7, make recursive call with index = 1.
Call 2: index = 1, arr[1] = 1. Since 1 ≠ 7, make recursive call with index = 2.
Call 3: index = 2, arr[2] = 7. Since arr[2] == 7, return 2.
The method finds the target at index 2 and returns immediately—it doesn't continue searching for other occurrences. Total calls: 3 (including the initial call).
Choice A is wrong because while it correctly counts 3 calls, it incorrectly returns 4. Choice B is wrong on both counts—it returns 4 and claims 5 calls were made. Choice C correctly identifies that 2 is returned but incorrectly states 4 calls were made.
Choice D is correct: the method returns 2 (the first occurrence of target 7) and makes exactly 3 total recursive calls.
Study tip: When tracing recursive methods, always count the initial call and remember that search functions typically return the first match they find, not the last. Practice tracing by writing down each call's parameters and return value—this prevents counting errors that are common on AP exam recursive problems.
- For the recursive merge sort shown below, what is the time complexity of the given recursive algorithm?
import java.util.*;
public class Sorter {
public static int[] mergeSort(int[] nums) {
if (nums.length <= 1) {
return nums;
}
int mid = nums.length / 2;
int[] left = Arrays.copyOfRange(nums, 0, mid);
int[] right = Arrays.copyOfRange(nums, mid, nums.length);
return merge(mergeSort(left), mergeSort(right));
}
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
result[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
while (i < left.length) result[k++] = left[i++];
while (j < right.length) result[k++] = right[j++];
return result;
}
} Answer: O(nlogn) because the array is split and merged by levels.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on analyzing the time complexity of merge sort. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the merge sort algorithm splits the array in half at each level, creating log n levels, and at each level, all n elements must be processed during the merge operations. Choice B is correct because merge sort has O(n log n) time complexity: there are log n levels of recursion (from splitting), and each level requires O(n) work to merge all elements at that level. Choice A is incorrect because it only considers the merge operation at one level, missing the recursive depth; each element is actually compared multiple times across different levels. To help students: Draw the recursion tree showing how an 8-element array splits into levels. Calculate the work at each level (n elements total) and count the levels (log n) to derive n log n complexity. - In this recursive merge sort on an int array, how does the algorithm handle the input array in recursive steps?
// Merge sort: split, sort halves recursively, then merge
public static void mergeSort(int[] nums, int left, int right) {
// Base case: one element (already sorted)
if (left >= right) {
return;
}
int mid = (left + right) / 2;
// Recursive calls: sort left half and right half
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// Merge step: combine two sorted halves
merge(nums, left, mid, right);
}
private static void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) temp[k++] = nums[i++];
else temp[k++] = nums[j++];
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
for (int t = 0; t < temp.length; t++) {
nums[left + t] = temp[t];
}
} Answer: It repeatedly splits into halves, then merges sorted subarrays
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding how merge sort processes arrays recursively. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the merge sort algorithm divides the array into two halves at each recursive level, sorts each half independently through recursive calls, then merges the sorted halves back together. Choice B is correct because it accurately describes the divide-and-conquer approach: the array is repeatedly split into halves until single elements remain, then sorted subarrays are merged bottom-up. Choice A is incorrect because it describes bubble sort's behavior of swapping adjacent elements, not merge sort's divide-and-conquer strategy. To help students: Use visual diagrams showing the recursive tree structure of merge sort. Trace through a small array example showing how it splits down to single elements then merges back up in sorted order.
- How does this recursive binary search handle the input array during recursive steps?
public class Searcher {
// Searches within nums[low..high] without creating new arrays
public static int binarySearch(int[] nums, int target, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (nums[mid] == target) {
return mid;
}
if (target < nums[mid]) {
return binarySearch(nums, target, low, mid - 1);
} else {
return binarySearch(nums, target, mid + 1, high);
}
}
} Answer: It searches using the same array but changes low and high.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding how recursive binary search manages memory and array access. Efficient recursive algorithms often work with the original data structure using index boundaries rather than creating copies. In this implementation, the same array reference nums is passed to each recursive call, but the search boundaries are adjusted through the low and high parameters, effectively limiting which portion of the array is being searched. Choice C is correct because it accurately describes that the algorithm reuses the same array throughout all recursive calls while changing only the index boundaries to focus on different segments. Choice A is incorrect because creating new subarrays would be inefficient and unnecessary, as we can simply adjust indices to work with different portions of the original array. To help students: Emphasize the difference between passing array references versus creating array copies. Use memory diagrams to show how all recursive calls share the same array in memory, with only the low and high values on the call stack changing.
- The recursive method above is part of a sorting algorithm. Based on the structure shown, which statement best describes the time complexity and the role of the combine method?
Answer: Time complexity is O(n log n) and combine merges two sorted subarrays into one sorted subarray
This is the structure of merge sort. The method divides the array in half recursively (log n levels) and the combine method must merge the sorted halves (O(n) work per level), giving O(n log n) overall. The divide-and-conquer pattern with mid-point splitting and post-recursive combination is characteristic of merge sort.
- Given this recursive binary search, what is the base case that stops recursion when the target cannot be found?
public class Searcher {
// Returns index of target in sorted array, or -1 if not found
public static int binarySearch(int[] nums, int target, int low, int high) {
// Base case: interval is empty
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
// Found target
if (nums[mid] == target) {
return mid;
}
// Recursive step: search one half
if (target < nums[mid]) {
return binarySearch(nums, target, low, mid - 1);
} else {
return binarySearch(nums, target, mid + 1, high);
}
}
} Answer: When low > high, return -1.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding the base case in recursive binary search. In recursive algorithms, the base case is the condition that stops the recursion and prevents infinite calls. In this binary search implementation, the base case if (low > high) occurs when the search interval becomes invalid (empty), meaning the target cannot be found in the remaining search space. Choice B is correct because when low > high, it indicates that the search boundaries have crossed, which happens after repeatedly narrowing the search interval without finding the target. Choice A is incorrect because low == high represents a valid single-element interval that still needs to be checked. To help students: Emphasize that base cases prevent infinite recursion and represent the simplest form of the problem. Practice tracing through examples where the target is not found, observing how the interval shrinks until low exceeds high.
- A recursive merge sort is applied to an array of 8 elements. During the sorting process, at what point in the recursion are individual elements first compared and potentially reordered during the merge operations?
Answer: When merging single-element arrays back together as the recursion unwinds
When you encounter questions about recursive merge sort, focus on understanding the two distinct phases: the dividing phase (going down the recursion) and the merging phase (unwinding back up). The key insight is that no comparisons or reordering happen during the dividing phase - elements are only compared when arrays are merged back together.
Merge sort recursively divides the array until each subarray contains just one element. At this point, the algorithm begins unwinding and merging. The first merge operations occur between single-element arrays, and this is precisely when the first comparisons happen. When you merge two single-element arrays, you must compare their values to determine which element goes first in the merged result.
Option A is incorrect because the "second level of unwinding" implies comparisons have already occurred at an earlier level. The first comparisons actually happen at the very first unwinding level. Option B misunderstands the process entirely - at the deepest recursion level, you're just dividing arrays, not comparing elements. Single elements by definition need no internal sorting. Option D confuses the dividing phase with the merging phase. When the array is first divided into halves, no comparisons occur - you're simply splitting the array.
Study tip: Remember that merge sort has two completely separate phases. Division requires no comparisons (just splitting arrays), while merging always requires comparisons. The first merge operations happen between the smallest possible arrays - single elements - so that's when comparisons begin.
- For the recursive binary search below on a sorted array, what is the time complexity in terms of n?
public static int binarySearch(int[] nums, int target, int low, int high) {
if (low > high) return -1;
int mid = (low + high) / 2;
if (nums[mid] == target) return mid;
if (target < nums[mid]) return binarySearch(nums, target, low, mid - 1);
return binarySearch(nums, target, mid + 1, high);
} Answer: O(logn) because it halves the search interval
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on analyzing the time complexity of recursive binary search. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, binary search eliminates half of the remaining search space with each recursive call by comparing the target with the middle element and recursing on only one half. Choice B is correct because the algorithm halves the search interval with each recursive call, resulting in at most log₂(n) recursive calls before finding the target or determining it's not present, giving O(log n) time complexity. Choice A is incorrect because it describes linear search complexity; binary search's key advantage is avoiding the need to check every element by exploiting the sorted order. To help students: Demonstrate how the search space reduces: n → n/2 → n/4 → ... → 1, which takes log₂(n) steps. Compare with linear search to highlight the efficiency gain from using the sorted property. - Given the recursive factorial method below, what is the base case in this recursive algorithm?
public class MathUtil {
// Computes n! for n >= 0
public static int factorial(int n) {
// Base case
if (n == 0) {
return 1;
}
// Recursive step
return n * factorial(n - 1);
}
}Assume factorial(4) is called. Answer: The base case is when n equals 0, returning 1.
This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on identifying the base case in a recursive factorial implementation. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the factorial method shows a clear base case when n equals 0, returning 1, which correctly implements the mathematical definition that 0! = 1. Choice C is correct because it accurately identifies that the base case occurs when n equals 0, returning 1, which stops the recursion and provides the foundation for building up the factorial calculation. Choice A is incorrect because while 1! = 1, the code doesn't check for n == 1 as a base case; instead, it would recurse to factorial(0) and use the n == 0 base case. To help students: Trace through factorial(4) showing the call stack building up and unwinding. Emphasize that 0! = 1 by definition and explain why this makes a good base case for the recursive formula n! = n × (n-1)!.
