Recursion in Java is a process where a method calls itself to solve a problem. It’s a powerful technique used in solving problems that can be broken down into simpler, similar subproblems. Below, we’ll explore recursion with various examples, providing insights into how it works and its applications.

### Basic Recursion Example: Factorial Calculation

A classic example of recursion is calculating the factorial of a number. The factorial of `n`

(denoted as `n!`

) is the product of all positive integers less than or equal to `n`

.

**Example**:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class RecursionExample { public static int factorial(int n) { if (n <= 1) { // Base case return 1; } else { // Recursive case return n * factorial(n - 1); } } public static void main(String[] args) { System.out.println(factorial(5)); // Output: 120 } } // Output: 120 |

Comments in the code explain the base case (stopping condition) and the recursive case, where the method calls itself.

### Recursion Example: Fibonacci Series

Another common example illustrating recursion is generating the Fibonacci series, where each number is the sum of the two preceding ones, usually starting with 0 and 1.

**Example**:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class FibonacciExample { public static int fibonacci(int n) { if (n <= 1) { return n; } else { 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 |

### Recursion Example: Tower of Hanoi

The Tower of Hanoi is a classic problem that demonstrates the power of recursion. It involves moving a stack of disks from one rod to another, with the constraint that no larger disk may be placed on top of a smaller disk.

**Example**:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class TowerOfHanoiExample { public static void moveDisks(int n, char fromRod, char toRod, char auxRod) { if (n == 1) { // Base case System.out.println("Move disk 1 from rod " + fromRod + " to rod " + toRod); return; } moveDisks(n - 1, fromRod, auxRod, toRod); System.out.println("Move disk " + n + " from rod " + fromRod + " to rod " + toRod); moveDisks(n - 1, auxRod, toRod, fromRod); } public static void main(String[] args) { int n = 3; // Number of disks moveDisks(n, 'A', 'C', 'B'); // A, B and C are names of rods } } |

Output:

1 2 3 4 5 6 7 |
Move disk 1 from rod A to rod C Move disk 2 from rod A to rod B Move disk 1 from rod C to rod B Move disk 3 from rod A to rod C Move disk 1 from rod B to rod A Move disk 2 from rod B to rod C Move disk 1 from rod A to rod C |

### Understanding Recursion

Recursion is based on two main concepts:

**Base Case**: The condition under which the recursion stops. Without a base case, you’d end up with infinite recursion, leading to a`StackOverflowError`

.**Recursive Step**: The part of the method where it calls itself but with a smaller or simpler problem to solve.

Recursion can be incredibly efficient and elegant for certain problems, such as those mentioned above. However, it’s also essential to understand that recursion can lead to high memory usage due to the call stack, and not all problems are best solved with recursion. For tasks where recursion leads to repeated calculations of the same values (e.g., naive Fibonacci calculation), iterative solutions or memoization techniques might be more efficient.