Recursion in Java, explained for AP Computer Science A
A recursive method is a method that calls itself. In AP Computer Science A you mostly need to read and trace recursive code, and recursion questions are a reliable source of multiple-choice marks once the method clicks.
On this page
The idea
Recursion solves a problem by reducing it to a smaller version of the same problem. To count the steps on a staircase, you could say: “the number of steps is one plus the number of steps left after the first one”. Each time, the problem shrinks, until you reach the bottom, where the answer is obvious: zero steps remain.
Every correct recursive method has two parts:
- a base case, a simple input that is answered directly without another recursive call;
- a recursive case, which calls the method on a smaller input and uses the result.
If there is no base case, or the input never gets closer to it, the calls never stop. Java eventually runs out of memory for the calls and throws a StackOverflowError.
Example: factorial
The factorial n! is n × (n − 1) × … × 1, and 0! = 1. Recursively, n! = n × (n − 1)!.
public static int factorial(int n)
{
if (n == 0)
{
return 1; // base case
}
return n * factorial(n - 1); // recursive case
}How to trace a recursive method
Each call waits for the call it makes to finish. Picture the calls as a stack of plates: each new call goes on top, and results come back down the stack in reverse order. For factorial(4):
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1 (base case)Now substitute back up: factorial(1) = 1, factorial(2) = 2, factorial(3) = 6, factorial(4) = 24. On the exam, write this trace in the margin. It turns a confusing question into simple arithmetic.
Worked examples
Example 1: sum of digits
public static int digitSum(int n)
{
if (n < 10)
{
return n;
}
return n % 10 + digitSum(n / 10);
}- digitSum(472) = 2 + digitSum(47) = 2 + 7 + digitSum(4) = 2 + 7 + 4.
- Returns 13. n % 10 takes the last digit and n / 10 removes it.
Example 2: reversing a string
public static String rev(String s)
{
if (s.length() <= 1)
{
return s;
}
return rev(s.substring(1)) + s.substring(0, 1);
}- rev("code") = rev("ode") + "c" = (rev("de") + "o") + "c" = ((rev("e") + "d") + "o") + "c".
- Returns "edoc".
Example 3: output order
public static void mystery(int n)
{
if (n > 0)
{
mystery(n - 1);
System.out.print(n + " ");
}
}- The print comes after the recursive call, so the deepest call prints first.
- Printed: 1 2 3. If the print came before the call, it would print 3 2 1. This before-or-after detail is a favourite exam trick.
Example 4: counting calls
How many times is factorial called, in total, when you call factorial(5)?
- Calls are made for n = 5, 4, 3, 2, 1 and 0.
- 6 calls, including the first one.
Example 5: two recursive calls
public static int fib(int n)
{
if (n <= 1)
{
return n;
}
return fib(n - 1) + fib(n - 2);
}- fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3.
- fib(5) = fib(4) + fib(3) = 5. Build up from the base cases rather than expanding every call: with two calls per level, the full tree grows very quickly.
A tracing checklist
When a multiple-choice question shows a recursive method, work through the same four checks. First, find the base case and note what it returns. Second, see how the argument changes in each call, and confirm it moves towards the base case. Third, notice whether any work, such as printing or adding, happens before or after the recursive call. Fourth, write out the calls in a column and substitute the returned values back up. This routine is quick, and it avoids the guesswork that costs marks on recursion questions.
Recursive binary search
Binary search finds a value in a sorted array by checking the middle element and discarding half the array each time. It is naturally recursive: search the left half or the right half, which is a smaller version of the same problem.
public static int search(int[] arr, int target, int low, int high)
{
if (low > high)
{
return -1; // not found
}
int mid = (low + high) / 2;
if (arr[mid] == target)
{
return mid;
}
else if (target < arr[mid])
{
return search(arr, target, low, mid - 1);
}
else
{
return search(arr, target, mid + 1, high);
}
}Each call halves the range, so even an array of a million elements needs only about 20 comparisons. Merge sort uses the same divide-and-conquer idea: split the array in half, sort each half recursively, then merge.
Recursion or a loop?
Anything written recursively can also be written with a loop. Factorial and digit sums are simpler as loops in real programs. Recursion shines when a problem naturally splits into smaller copies of itself, such as searching sorted data, sorting, or exploring tree-like structures such as folders inside folders. For the AP exam, the key skill is reading recursive code accurately.
Common mistakes
- Forgetting the base case, or writing one that the input never reaches.
- Changing the input in the wrong direction, so it moves away from the base case.
- Losing track of whether work happens before or after the recursive call.
- Mixing up substring(1) (everything after the first character) with substring(0, 1) (the first character).
Practice questions
Try each one before opening the answer.
Q1. What does factorial(5) return?
Show answer
Q2. What does digitSum(9005) return?
Show answer
Q3. A method f(n) returns n + f(n - 2) for n > 0, and 0 otherwise. What is f(6)?
Show answer
Q4. What happens if you call factorial(-1) with the code above?
Show answer
Frequently asked questions
Is recursion on the revised AP Computer Science A exam?
Recursion is still in the course in the 2025–26 revision, with a focus on tracing recursive methods and on recursive searching and sorting. Check the current Course and Exam Description on AP Central for the exact scope.
Will I have to write recursive code on the free-response section?
Free-response questions rarely require recursion. You are far more likely to meet it in multiple-choice questions that ask what a recursive method returns or prints.
Key takeaways
- Every recursive method needs a base case and a recursive case.
- Each call must move closer to the base case.
- Trace with a call stack, then substitute back up.
- Work after the recursive call happens in reverse order.
- Binary search and merge sort are classic recursive algorithms.