Java · Chapter 21 of 42
Java Recursion
Recursion is when a method calls itself to solve a smaller instance of the same problem. Every recursive method needs a base case to stop the recursion, and a recursive case that moves toward that base case.
Recursion is elegant for problems like factorials, Fibonacci numbers, and tree traversal, but can be less efficient than loops due to call-stack overhead.
Syntax
int f(int n) {
if (n == base) return baseValue;
return combine(n, f(n - 1));
}Base case and recursive case
The base case stops recursion immediately; without it, the method calls itself forever and causes a StackOverflowError.
When to use recursion
Recursion shines for naturally recursive structures like trees and divide-and-conquer algorithms, but simple counting loops are often clearer as iteration.
Example 1 (java)
public class Main {
static int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
public static void main(String[] args) {
System.out.println(factorial(5));
}
}Output
120factorial(5) calls itself down to factorial(0), the base case, then multiplies results back up.
Key points
- Every recursive method needs a base case.
- Recursive calls move toward the base case.
- Missing base case causes StackOverflowError.
- Recursion can replace some loops, especially for tree-like problems.
💡 Note: Deep recursion can be slower and more memory-intensive than an equivalent loop.