Recursion is a programming technique where a method calls itself to solve a problem. In Java, recursion allows a function to repeat its behavior by calling itself with modified arguments until a base case (or stopping condition) is reached.

Basic Structure of Recursion

A recursive function typically consists of two parts:

1. Base case: The condition that stops the recursion. If this condition is met, the function will not call itself.

2. Recursive case: The part where the function calls itself with updated arguments to break the problem into smaller subproblems.

Example 1: Factorial Calculation

The factorial of a number $n$ is the product of all positive integers less than or equal to $n$. Mathematically, it's defined as:

For recursion, the factorial can be defined as:

The base case is when $n = 1$, then $1! = 1$.

Example: Factorial Using Recursion

public class Factorial {    // Recursive method to calculate factorial    public static int factorial(int n) {        // Base case        if (n == 0 || n == 1) {            return 1;        }        // Recursive case        return n * factorial(n - 1);    }    public static void main(String[] args) {        int number = 5;        int result = factorial(number);  // Call the recursive method        System.out.println("Factorial of " + number + " is: " + result);    }}

Output:

Factorial of 5 is: 120

Explanation:

• The factorial method calls itself with n-1 until it reaches the base case (n == 1 or n == 0).

• In this case, factorial(5) results in 5 * factorial(4), and so on, until the base case is reached.

Example 2: Fibonacci Series

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones. The first two numbers are 0 and 1, so the sequence starts as follows:
$0, 1, 1, 2, 3, 5, 8, 13, 21, \dots$

The Fibonacci sequence can be defined recursively as:

With base cases $F(0) = 0$ and $F(1) = 1$.

Example: Fibonacci Using Recursion

public class Fibonacci {    // Recursive method to calculate Fibonacci    public static int fibonacci(int n) {        // Base cases        if (n == 0) {            return 0;        }        if (n == 1) {            return 1;        }        // Recursive case        return fibonacci(n - 1) + fibonacci(n - 2);    }    public static void main(String[] args) {        int number = 6;        int result = fibonacci(number);  // Call the recursive method        System.out.println("Fibonacci of " + number + " is: " + result);    }}

Output:

Fibonacci of 6 is: 8

Explanation:

• The fibonacci method calls itself with n-1 and n-2 until the base cases are reached.

• In this case, fibonacci(6) results in fibonacci(5) + fibonacci(4), and so on, until the base case is reached.

Example 3: Sum of Numbers from 1 to N

You can use recursion to calculate the sum of numbers from 1 to $n$. This is an example of a simple recursive problem where the sum can be broken down into smaller sums.

Example: Sum of Numbers Using Recursion

public class SumNumbers {    // Recursive method to calculate sum    public static int sum(int n) {        // Base case        if (n <= 0) {            return 0;        }        // Recursive case        return n + sum(n - 1);    }    public static void main(String[] args) {        int number = 5;        int result = sum(number);  // Call the recursive method        System.out.println("Sum of numbers from 1 to " + number + " is: " + result);    }}

Output:

Sum of numbers from 1 to 5 is: 15

Explanation:

• The sum method adds the current number n to the result of sum(n-1) until the base case n <= 0 is reached.

• In this case, sum(5) results in 5 + sum(4), and so on, until the base case is reached.

Example 4: Reverse a String Using Recursion

You can use recursion to reverse a string by taking the first character and placing it at the end of the reversed substring.

Example: Reverse a String Using Recursion

public class ReverseString {    // Recursive method to reverse a string    public static String reverse(String str) {        // Base case        if (str.isEmpty()) {            return str;        }        // Recursive case        return reverse(str.substring(1)) + str.charAt(0);    }    public static void main(String[] args) {        String input = "Java";        String reversed = reverse(input);  // Call the recursive method        System.out.println("Reversed string: " + reversed);    }}

Output:

Reversed string: avaJ

Explanation:

• The reverse method works by breaking the string into smaller parts and appending the first character to the end of the reversed substring until the string is empty.

Key Points about Recursion in Java:

1. Base Case: Every recursive function must have a base case, which prevents the function from calling itself indefinitely and avoids a StackOverflowError.

2. Recursive Case: The recursive case is where the function calls itself with a smaller subset of the original problem.

3. Stack Overflow: If the recursion depth is too large (i.e., the function calls itself too many times without reaching the base case), it will cause a StackOverflowError because each recursive call consumes stack space.

Advantages of Recursion:

• Recursion simplifies problems that can be broken down into smaller, similar subproblems.

• Recursive solutions can be more elegant and easier to understand for problems like tree traversal, sorting algorithms (e.g., quicksort, mergesort), and searching (e.g., binary search).

Disadvantages of Recursion:

• Memory consumption: Each recursive call adds a new stack frame, so deep recursion can lead to high memory usage.

• Performance: Recursive solutions are sometimes slower than their iterative counterparts due to function call overhead.

Let me know if you'd like more detailed explanations or examples for recursion!