Java Recursion
Introduction
Recursion is a programming technique in which a method calls itself to solve a problem.
A method that calls itself is called a recursive method.
Recursion is useful for solving problems that can be divided into smaller versions of the same problem.
Simple Example
public class RecursionExample { static void count(int n) { if (n == 0) { return; } System.out.println(n); count(n - 1); } public static void main(String[] args) { count(5); } }
Output
5 4 3 2 1
Here, the method count() calls itself with a smaller value.
Basic Syntax of Recursion
returnType methodName(parameters) { if (baseCondition) { return value; } return methodName(modifiedParameters); }
A recursive method normally has two important parts:
- Base Case
- Recursive Case
1. Base Case
The base case is the condition that stops recursion.
Example:
if (n == 0) { return; }
Without a proper base case, the method may continue calling itself indefinitely.
2. Recursive Case
The recursive case is the part where the method calls itself.
Example:
count(n - 1);
The argument should normally move toward the base case.
How Recursion Works
Consider:
static void count(int n) { if (n == 0) { return; } System.out.println(n); count(n - 1); }
When we call:
count(3);
The execution is:
count(3) ↓ print 3 ↓ count(2) ↓ print 2 ↓ count(1) ↓ print 1 ↓ count(0) ↓ stop
Output:
3 2 1
Factorial Using Recursion
The factorial of a number n is:
n! = n × (n - 1) × (n - 2) × ... × 1
For example:
5! = 5 × 4 × 3 × 2 × 1 = 120
Java Program
public class FactorialRecursion { static int factorial(int n) { if (n == 0 || n == 1) { return 1; } return n * factorial(n - 1); } public static void main(String[] args) { int result = factorial(5); System.out.println("Factorial = " + result); } }
Output
Factorial = 120
How Factorial Recursion Works
For:
factorial(5)
The recursive calls are:
factorial(5) = 5 × factorial(4) = 5 × 4 × factorial(3) = 5 × 4 × 3 × factorial(2) = 5 × 4 × 3 × 2 × factorial(1)
Since:
factorial(1) = 1
The final result is:
5 × 4 × 3 × 2 × 1 = 120
Sum of Numbers Using Recursion
We can calculate the sum from 1 to n using recursion.
Example
public class SumRecursion { static int sum(int n) { if (n == 0) { return 0; } return n + sum(n - 1); } public static void main(String[] args) { int result = sum(5); System.out.println("Sum = " + result); } }
Output
Sum = 15
Calculation
5 + 4 + 3 + 2 + 1 = 15
Fibonacci Series Using Recursion
The Fibonacci sequence is:
0 1 1 2 3 5 8 13 21 ...
Each number is calculated by adding the previous two numbers.
F(n) = F(n-1) + F(n-2)
Java Example
public class FibonacciRecursion { static int fibonacci(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); } public static void main(String[] args) { for (int i = 0; i < 10; i++) { System.out.print(fibonacci(i) + " "); } } }
Output
0 1 1 2 3 5 8 13 21 34
This simple recursive Fibonacci implementation performs repeated calculations and becomes inefficient for larger
n. Dynamic programming or an iterative approach is usually better for practical use.
Countdown Using Recursion
public class Countdown { static void countdown(int n) { if (n == 0) { return; } System.out.println(n); countdown(n - 1); } public static void main(String[] args) { countdown(5); } }
Output
5 4 3 2 1
Count Up Using Recursion
We can also print numbers from 1 to n.
public class CountUp { static void count(int n) { if (n == 0) { return; } count(n - 1); System.out.println(n); } public static void main(String[] args) { count(5); } }
Output
1 2 3 4 5
Notice that the recursive call happens before System.out.println(n).
Reverse a String Using Recursion
A String can be reversed using recursion.
public class ReverseString { static String reverse(String text) { if (text.isEmpty()) { return text; } return reverse(text.substring(1)) + text.charAt(0); } public static void main(String[] args) { String result = reverse("Java"); System.out.println(result); } }
Output
avaJ
Sum of Array Elements Using Recursion
public class ArraySumRecursion { static int sum(int[] numbers, int index) { if (index == numbers.length) { return 0; } return numbers[index] + sum(numbers, index + 1); } public static void main(String[] args) { int[] numbers = {10, 20, 30, 40}; int result = sum(numbers, 0); System.out.println("Sum = " + result); } }
Output
Sum = 100
Recursive Method with Multiple Parameters
A recursive method can have multiple parameters.
Example
public class MultipleParameters { static int power(int base, int exponent) { if (exponent == 0) { return 1; } return base * power(base, exponent - 1); } public static void main(String[] args) { System.out.println(power(2, 5)); } }
Output
32
Because:
2⁵ = 2 × 2 × 2 × 2 × 2 = 32
Direct Recursion
When a method directly calls itself, it is called direct recursion.
Example:
static void display(int n) { if (n == 0) { return; } System.out.println(n); display(n - 1); }
The method display() directly calls itself.
Indirect Recursion
When one method calls another method, and the second method eventually calls the first method, it is called indirect recursion.
Example
public class IndirectRecursion { static void methodA(int n) { if (n <= 0) { return; } System.out.println("A: " + n); methodB(n - 1); } static void methodB(int n) { if (n <= 0) { return; } System.out.println("B: " + n); methodA(n - 1); } public static void main(String[] args) { methodA(3); } }
Output
A: 3 B: 2 A: 1
Recursion and Stack Memory
Every time a recursive method is called, Java creates a new stack frame for that method call.
For example:
factorial(5) ↓ factorial(4) ↓ factorial(3) ↓ factorial(2) ↓ factorial(1)
These calls remain on the call stack until the base case is reached and the calls return.
Stack Overflow
If recursion continues too deeply without reaching a base case, the program can eventually throw a StackOverflowError.
Example:
public class InfiniteRecursion { static void display() { display(); } public static void main(String[] args) { display(); } }
There is no base case, so the method keeps calling itself.
Eventually, the call stack becomes full.
Recursion vs Loop
Many recursive problems can also be solved using loops.
| Recursion | Loop |
|---|---|
| Method calls itself | Repeats using loop statements |
| Uses call stack | Usually uses less call-stack memory |
| Can make some problems easier to express | Often simpler for straightforward repetition |
| Requires a base case | Requires a loop condition |
| Can cause stack overflow for deep recursion | Does not normally create a stack frame per iteration |
| Useful for tree and graph traversal | Useful for simple repetition |
Recursion vs Iteration Example
Using Recursion
static int factorial(int n) { if (n == 0) { return 1; } return n * factorial(n - 1); }
Using Loop
static int factorial(int n) { int result = 1; for (int i = 1; i <= n; i++) { result *= i; } return result; }
Both methods can calculate factorial.
For simple repetition, the loop version is often more straightforward.
Advantages of Recursion
-
Simplifies complex problems Some problems naturally break into smaller versions of themselves.
-
Useful for tree structures Tree traversal is commonly implemented using recursion.
-
Useful for divide-and-conquer algorithms Examples include merge sort and quicksort.
-
Makes some mathematical solutions easier to understand.
-
Can produce concise code for suitable problems.
Disadvantages of Recursion
- Uses call stack memory.
- Deep recursion can cause
StackOverflowError. - Recursive solutions can be slower than iterative solutions in some cases.
- Repeated calculations can make some recursive algorithms inefficient.
- Recursive code can be harder for beginners to debug.
Real-Life Applications of Recursion
Recursion is commonly used in:
- Tree traversal
- File and directory traversal
- Graph algorithms
- Merge sort
- Quick sort
- Binary search
- Backtracking
- Mathematical calculations
- Parsing nested structures
- Solving maze problems
- Generating combinations and permutations
Important Rules of Recursion
When creating a recursive method, remember:
1. Always define a base case
if (n == 0) { return; }
2. Make progress toward the base case
For example:
method(n - 1);
3. Make sure recursion eventually stops
Avoid:
method(n);
if n never changes toward the stopping condition.
4. Be careful with deep recursion
Very deep recursion can cause:
StackOverflowError
Complete Example
The following program uses recursion to calculate factorial and the sum of numbers.
public class RecursionDemo { static int factorial(int n) { if (n == 0 || n == 1) { return 1; } return n * factorial(n - 1); } static int sum(int n) { if (n == 0) { return 0; } return n + sum(n - 1); } public static void main(String[] args) { int number = 5; System.out.println("Factorial = " + factorial(number)); System.out.println("Sum = " + sum(number)); } }
Output
Factorial = 120 Sum = 15
Summary
Recursion is a technique where a method calls itself.
The two most important parts of recursion are:
- Base Case – stops the recursion.
- Recursive Case – calls the method again with a smaller or changed problem.
Important points:
- Recursion can simplify complex problems.
- Every recursive solution needs a stopping condition.
- Recursive calls use stack memory.
- Too much recursion can cause
StackOverflowError. - Recursion is useful for trees, graphs, sorting, searching, and backtracking.
- Many recursive problems can also be solved using loops.