1. Recursion in Java
Recursion is a programming technique where a method calls itself to solve a problem.
It breaks a large problem into smaller sub-problems of the same type.
Each recursive call works on a reduced version of the original problem.
2. Why Recursion is Used
Recursion is used when a problem can naturally be divided into similar smaller problems.
- a. Simplifies complex problems
- b. Reduces code size
- c. Useful for mathematical problems
- d. Helps in tree and graph traversal
- e. Makes code more readable for certain problems
- f. Common in divide-and-conquer algorithms
3. Where Recursion is Used
Recursion is widely used in algorithmic and data structure problems.
- a. Factorial calculation
- b. Fibonacci series
- c. Tree traversal (DFS)
- d. Searching algorithms
- e. Sorting algorithms (QuickSort, MergeSort)
- f. Backtracking problems
4. Basic Structure of Recursion
A recursive method must contain two essential parts.
4.1 Base Case
The base case stops the recursion to prevent infinite calls.
4.2 Recursive Case
The recursive case is where the method calls itself with a smaller input.
Without a base case, recursion will continue forever and cause StackOverflowError.
5. Simple Recursion Example
A basic recursion example is printing numbers in reverse order.
5.1 Example: Counting Down
public class Main {
static void countdown(int n) {
if(n == 0) {
return;
}
System.out.println(n);
countdown(n - 1);
}
public static void main(String[] args) {
countdown(5);
}
}
The method keeps calling itself with a reduced value until it reaches 0.
6. How Recursion Works Internally
Each recursive call is stored in stack memory.
6.1 Stack Memory Behavior
- a. Each call creates a new stack frame
- b. Frames are stored on top of each other
- c. Execution pauses in previous calls
- d. Returns happen in reverse order
6.2 Example Flow
countdown(3) → countdown(2) → countdown(1) → countdown(0) STOP
After reaching the base case, the stack starts unwinding.
7. Simple Recursion Pattern
Most recursive solutions follow a standard pattern.
7.1 Pattern Structure
if (base condition) {
return;
}
solve smaller problem;
call function again;
This pattern is used in almost every recursive solution.
Recursion always reduces the problem size step-by-step until it reaches the base case.
8. Simple Factorial Preview
Factorial is one of the most common examples of recursion.
5! = 5 × 4 × 3 × 2 × 1
Recursion can solve this problem naturally by reducing the number step-by-step.
9. Factorial Using Recursion
The factorial of a number n is the product of all numbers from n to 1.
It is a perfect example of recursion because it can be broken into smaller identical problems.
9.1 Factorial Formula
n! = n × (n - 1)!
This formula clearly shows how the problem reduces step by step.
9.2 Base Case for Factorial
0! = 1
The recursion stops when the value reaches 0.
9.3 Recursive Factorial Example
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));
}
}
Each call multiplies the number with the result of the smaller subproblem.
10. Step-by-Step Execution of Factorial
Let’s understand how factorial(5) executes internally.
10.1 Call Breakdown
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 × factorial(0) = 120
The recursion builds calls first, then resolves results while returning back.
11. Recursion Tree Visualization
A recursion tree helps visualize how recursive calls are created.
factorial(5)
|
└── factorial(4)
|
└── factorial(3)
|
└── factorial(2)
|
└── factorial(1)
|
└── factorial(0)
Each level depends on the result of the next recursive call.
12. Internal Working of Recursion
Recursion uses stack memory to store function calls.
12.1 Push Phase
- a. Each method call is pushed into stack
- b. Execution pauses at each call
- c. Calls keep stacking until base case is reached
12.2 Pop Phase
- a. Base case returns value
- b. Stack starts unwinding
- c. Each call returns its result
- d. Final result is computed
Recursion heavily depends on stack memory, so deep recursion may cause StackOverflowError.
13. Recursion vs Iteration
Recursion and loops can solve similar problems but behave differently.
| Recursion | Iteration |
| Uses function calls | Uses loops |
| Uses stack memory | Uses less memory |
| Cleaner for complex problems | Faster for simple repetition |
14. Iterative vs Recursive Factorial
14.1 Iterative Approach
public class Main {
public static void main(String[] args) {
int n = 5;
int result = 1;
for(int i = 1; i <= n; i++) {
result = result * i;
}
System.out.println(result);
}
}
The loop calculates factorial without using stack memory.
14.2 Recursive Approach
static int factorial(int n) {
if(n == 0) {
return 1;
}
return n * factorial(n - 1);
}
Recursion is more elegant but uses more memory.
Choose recursion for clarity and iteration for performance.
15. Common Recursion Mistakes
15.1 Missing Base Case
A recursive method must always have a stopping condition.
public class Main {
static void print(int n) {
System.out.println(n);
print(n - 1);
}
public static void main(String[] args) {
print(5);
}
}
This code causes infinite recursion because there is no base case.
Without a base case, recursion leads to StackOverflowError.
15.2 Wrong Base Condition
static void count(int n) {
if(n == 5) {
return;
}
count(n - 1);
}
Incorrect base conditions may stop recursion too early or too late.
15.3 Not Reducing Problem Size
static void loop(int n) {
if(n == 0) {
return;
}
loop(n);
}
The value of n never changes, causing infinite recursion.
16. Edge Cases in Recursion
16.1 Negative Input Values
static int factorial(int n) {
if(n == 0) {
return 1;
}
return n * factorial(n - 1);
}
Negative values can lead to infinite recursion if not handled properly.
16.2 Large Input Values
Large recursive calls can exceed stack memory limits.
Too many recursive calls can cause StackOverflowError.
16.3 Single Step Recursion
static void test(int n) {
if(n == 0) {
return;
}
System.out.println(n);
test(n - 1);
}
Each recursive call processes only one step at a time.
17. Internal Memory Behavior of Recursion
Recursion uses stack memory to store function calls.
17.1 Stack Growth
- a. Each call is pushed into stack
- b. Stack grows with each recursion
- c. Base case stops further stacking
17.2 Stack Unwinding
- a. Base case returns value
- b. Previous calls resume execution
- c. Stack frames are removed one by one
18. Best Practices for Recursion
18.1 Always Define a Base Case
Every recursive method must include a clear stopping condition.
18.2 Ensure Problem Size Reduces
Each recursive call must move closer to the base case.
18.3 Avoid Deep Recursion
Use iteration when recursion depth becomes too large.
Good recursion design ensures safety, clarity, and performance balance.
19. Important Points to Remember
- a. Recursion means method calling itself
- b. Base case is mandatory
- c. Each call uses stack memory
- d. Stack unwinds after reaching base case
- e. Missing base case causes infinite recursion
- f. Recursion is useful for complex problems
- g. Iteration is more memory efficient
- h. Factorial and tree traversal are common examples
Recursion is a powerful programming technique in Java that simplifies complex problems by breaking them into smaller subproblems. When used correctly with a proper base case and controlled depth, recursion leads to elegant and readable solutions, especially in mathematical computations and data structure traversal.