Sometimes a problem can be solved by breaking it into smaller versions of the same problem. When a method calls itself to solve such a problem, it is called recursion.
In simple words, recursion is when a method calls itself.
At first, this might sound a little strange. You may be thinking, "Why would a method call itself?" 😄 But for certain problems, recursion can make the solution much easier to understand.
A Simple Example
Let's create a method that prints numbers from 5 down to 1:
static void countDown(int n) {
if (n == 0) {
return;
}
System.out.println(n);
countDown(n - 1);
}
We can call it like this:
countDown(5);
The output will be:
5
4
3
2
1
Notice what happens inside countDown():
countDown(n - 1);
The method calls itself with a smaller value.
When n becomes 0, this condition becomes true:
if (n == 0) {
return;
}
The method stops calling itself, and the recursion ends.
The Base Case
The condition that stops recursion is called the base case.
In our example:
if (n == 0) {
return;
}
is the base case.
A recursive method needs a condition that eventually stops the recursive calls. Otherwise, the method will keep calling itself indefinitely.
For example, this is dangerous:
static void hello() {
System.out.println("Hello");
hello();
}
There is no condition that stops the method. It keeps calling itself again and again, eventually causing a StackOverflowError.
So whenever you write a recursive method, always ask yourself:
"When should the recursion stop?"
Recursive Case
Apart from the base case, a recursive method has the part where it calls itself. This is called the recursive case.
In our example:
countDown(n - 1);
is the recursive case.
So a simple recursive method usually has two important parts:
Base Case
↓
Stops the recursion
Recursive Case
↓
Calls the method again
Recursion Example: Factorial
A classic example of recursion is calculating the factorial of a number.
The factorial of 5 is:
5 × 4 × 3 × 2 × 1 = 120
We can calculate it recursively:
static int factorial(int n) {
if (n == 1) {
return 1;
}
return n * factorial(n - 1);
}
Now:
int result = factorial(5);
System.out.println(result);
Output:
120
Let's see what Java is effectively calculating:
factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1
= 120
The method keeps calling itself with a smaller number until it reaches the base case.
When Should We Use Recursion?
Recursion is especially useful for problems that naturally contain smaller versions of themselves.
It is commonly used in problems involving:
Tree structures
Searching
Sorting
Graphs
Backtracking
Mathematical problems
However, recursion isn't always the best solution. A recursive solution can sometimes use more memory than a normal loop because each method call needs to be stored while the recursion is taking place.
For simple repetition, a loop is often easier and more efficient.
Recursion vs Loop
For example, we can print numbers from 1 to 5 using a loop:
for (int i = 1; i <= 5; i++) {
System.out.println(i);
}
We could also do it recursively:
static void printNumbers(int n) {
if (n > 5) {
return;
}
System.out.println(n);
printNumbers(n + 1);
}
Both can produce the same result, but the loop is simpler for this particular problem.
That's why recursion should not be used just because you can use it. It is most useful when the problem naturally fits a recursive approach.
The Important Idea
Don't worry if recursion feels strange at first. The most important thing to understand is simply this:
A recursive method calls itself, and it must have a base case that eventually stops the calls.
Once you understand those two ideas, more advanced recursive problems become much easier to follow.