Recursion occurs when a method calls itself, directly or indirectly, to solve a smaller version of a problem. A useful recursive solution needs a base case that stops calling and a recursive step that moves toward that case. Without both, calls can continue until the program exhausts its stack.
Think of each call as its own unfinished task, with separate parameters and local variables. A result from a smaller call can help complete the caller’s task. The examples start with a countdown, then show returned results and a recursive traversal.
The base case answers the smallest problem
A base case supplies an answer without another recursive call. For a nonnegative countdown, reaching zero can stop printing. For factorial, zero factorial is one. The right base case comes from the problem’s definition, not from an arbitrary convenient number.
Validate inputs that cannot reach the base case through your chosen step. A factorial helper that decreases its input toward zero will not handle a negative input correctly unless it rejects it or defines another contract. Multiple base cases can be appropriate. For instance, a recursive tree operation often stops at a missing node, while a numeric recurrence may have two starting values. State accepted inputs before tracing the calls.
The recursive step must make progress
A recursive step should reduce a meaningful measure of the remaining work. A countdown decreases the count; an array traversal increases an index until it reaches the length; a tree operation moves to smaller subtrees. Calling the same method with the same unchanged argument usually makes no progress.
Progress does not have to mean subtracting one. Binary search narrows a range, and divide-and-conquer algorithms split a problem. The important point is that the smaller problem approaches a stopping condition. Prove this informally for the permitted inputs: name the measure, show how each call reduces it and explain why it cannot decrease forever without reaching a base case. This reasoning finds mistakes before you run them.
Separate going down from returning up
When a method calls itself, the caller waits while the called method runs. For factorial(3), the calls reach factorial(2), factorial(1) and factorial(0). The base case returns one. Then the pending multiplications finish in reverse order, producing one, two and six.
Statements before a recursive call execute while descending through the calls. Statements after it execute while returning. A countdown that prints before its call displays values in descending order; moving the print after the call reverses that order. This is not a sorting operation: it follows the stack of waiting calls. Trace a small input on paper and record both the argument for each call and the value that returns.
Stack space and practical limits
Each active recursive call consumes stack space for its execution state. A deep linear recursion can fail with StackOverflowError even when the algorithm’s mathematical answer is well defined. Java does not guarantee tail-call optimization, so writing a recursive call as the last operation does not automatically remove this risk.
For a simple long countdown or array sum, a loop is often more practical. Recursion can be clearer for naturally recursive structures such as trees or backtracking problems. Avoid catching StackOverflowError as the ordinary stopping mechanism; define a real base case and choose a depth suitable for the environment. The precise maximum safe depth depends on runtime settings and method details rather than a universal lesson number.
Correct recursion still needs arithmetic boundaries
A terminating factorial method can still overflow its numeric result. An int stores only a limited range, and factorial grows quickly. A long extends that range but does not make it unlimited. For this lesson, use small inputs where the result fits and treat the range as part of the method’s contract.
A simple recursive array sum makes one call per element plus the base case, so both time and stack space grow linearly with the number of elements. Some recurrences repeat subproblems and become much more expensive. Recursive Fibonacci is a familiar example, but learning recursion does not require starting with that inefficient pattern. Choose a small example whose call count and returned value can be explained accurately.
Practice with explained solutions
Task 1. Move RecursiveCountdown’s println after its recursive call and predict the output for three.
Solution. The outputs become 1, 2 and 3 because printing occurs while waiting calls resume in reverse order.
Task 2. State a base case and progress measure for traversing a nonnull array from index zero.
Solution. Stop at index == values.length; each call increases index by one, reducing the number of unvisited elements.
Java Summary
- Define both a stopping base case and a step that approaches it.
- Each recursive invocation has its own parameters and pending work.
- Termination alone does not prevent arithmetic overflow or excessive stack depth.
- Continue with recursive algorithm practice.
Java Examples
Each example shows the code, the output it produces and what each part does.
Stop a recursive countdown
Save this complete program as RecursiveCountdown.java. Compile with javac --release 17 RecursiveCountdown.java and run with java RecursiveCountdown.
public class RecursiveCountdown {
static void countdown(int remaining) {
if (remaining == 0) {
return;
}
System.out.println(remaining);
countdown(remaining - 1);
}
public static void main(String[] args) {
countdown(3);
}
}3
2
1Line-by-line explanation
- Lines 1 to 8Each call prints its positive argument before requesting the next smaller countdown. The call with zero returns without printing, so the chain stops.
- Lines 9 to 12The example’s contract permits nonnegative inputs; a negative starting value would move away from zero. Printing after the recursive call instead would display one, two and three as the calls return.
Build a result as calls return
Save this complete program as SmallFactorial.java. Compile with javac --release 17 SmallFactorial.java and run with java SmallFactorial.
public class SmallFactorial {
static int factorial(int value) {
if (value == 0) {
return 1;
}
return value * factorial(value - 1);
}
public static void main(String[] args) {
System.out.println(factorial(4));
}
}24Line-by-line explanation
- Lines 1 to 11The argument decreases until factorial(0) returns one. The waiting calls then compute 1 times 1, 2 times 1, 3 times 2 and 4 times 6. The final result is twenty-four. This helper deliberately assumes small nonnegative values; production code should validate that contract and choose a representation that handles the required range.
Advance through an array
Save this complete program as RecursiveArraySum.java. Compile with javac --release 17 RecursiveArraySum.java and run with java RecursiveArraySum.
public class RecursiveArraySum {
static int sum(int[] values, int index) {
if (index == values.length) {
return 0;
}
return values[index] + sum(values, index + 1);
}
public static void main(String[] args) {
int[] values = {4, 1, 6};
System.out.println(sum(values, 0));
}
}11Line-by-line explanation
- Lines 1 to 8The index identifies the remaining suffix of the array. Reaching the length gives the empty suffix a sum of zero.
- Lines 9 to 12Each earlier call adds its element to the returned suffix sum, giving six, seven and finally eleven. Start at zero and use a nonnull array. A negative or oversized starting index would violate this simple helper’s preconditions.
Common Java Mistakes
Recursing before checking the base case
Do not check for a base case after making an unconditional recursive call. The next call must be avoided when the smallest problem has already been reached. Also verify the direction of change: increasing a positive countdown moves away from zero. A program producing a few correct-looking lines can still be headed toward an eventual stack failure.
Java FAQ
Is recursion always better than a loop?
No. Choose it when it expresses the structure clearly and the depth is suitable. Simple linear repetition often fits a loop better.
Does reaching a base case guarantee the numeric result is correct?
No. The recurrence, permitted inputs and arithmetic range must also be correct.
Does Java optimise tail recursion?
No. The JVM doesn't perform tail-call elimination, so even a recursive call in the last position uses a new stack frame. Deep linear recursion can therefore fail with StackOverflowError in Java where it might not in some functional languages. Rewrite such methods as loops when the depth can be large.
How do I turn a recursive method into a loop?
For linear recursion, keep the changing parameters in local variables and update them in a loop, often with an accumulator for the result. For branching recursion, such as walking a tree, push pending work onto an explicit ArrayDeque used as a stack and loop until it's empty.
Where is recursion used in real programs?
Recursion fits problems that contain smaller copies of themselves: walking folders and their subfolders, traversing trees and nested JSON, parsing expressions, and divide-and-conquer algorithms such as merge sort and binary search. The recursion and backtracking lesson builds on these ideas.
Java Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
What does factorial(0) return in the example?
How does RecursiveArraySum approach its base case?
Java Quiz
2 questions to check what you learned.
What prevents further recursive calls for the smallest input?
- A base case
- A class filename
- An output label
Does Java guarantee tail-call optimization?
- No
- Yes for every recursive method
- Only when printing