Java Recursive Method

Introduction#

A recursive method is a method that calls itself to solve a problem. Recursion is useful for problems that can be broken down into smaller subproblems of the same type. It is commonly used for tasks such as factorial calculation, Fibonacci series, tree traversal, and searching algorithms.

How Recursion Works in Java?#

A recursive method must have:

1. Base Case – A condition that stops the recursion.
2. Recursive Case – A condition where the method calls itself with a modified argument to approach the base case.

Example: Simple Recursion#

Let’s start with a simple example of printing numbers from n to 1 using recursion.

class RecursionExample {
  // Recursive method to print numbers
  static void printNumbers(int n) {
    if (n == 0) {  // Base case: Stop when n reaches 0
      return;
    }
    System.out.println(n);
    printNumbers(n - 1);  // Recursive call
  }

  public static void main(String[] args) {
    printNumbers(5);
  }
}

Expected Output:#

5
4
3
2
1

Explanation:

• If n == 0, the method stops (base case).
• Otherwise, it prints n and calls itself with n - 1, reducing the number each time until it reaches 0.

Factorial Using Recursion#

Factorial of a number n is calculated as:

n! = n × (n-1) × (n-2) × ... × 1

Using recursion, the factorial of n can be defined as:

factorial(n) = n × factorial(n-1)   (if n > 1)
factorial(1) = 1   (base case)

Example: Factorial Calculation#

class FactorialExample {
  // Recursive method to calculate factorial
  static int factorial(int n) {
    if (n == 1) {  // Base case
      return 1;
    }
    return n * factorial(n - 1);  // Recursive call
  }

  public static void main(String[] args) {
    int num = 5;
    System.out.println("Factorial of " + num + " is: " + factorial(num));
  }
}

Expected Output:#

Factorial of 5 is: 120

Explanation:

• When n = 1, the recursion stops and returns 1 (base case).
• Otherwise, the method calls itself with n - 1, multiplying n with the result of factorial(n-1).
• The recursive calls unfold as:

factorial(5) → 5 × factorial(4)
factorial(4) → 4 × factorial(3)
factorial(3) → 3 × factorial(2)
factorial(2) → 2 × factorial(1)
factorial(1) → 1 (Base Case)

Fibonacci Series Using Recursion#

The Fibonacci sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Each term is the sum of the two preceding numbers:

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Example: Fibonacci Series#

class FibonacciExample {
  // Recursive method to find nth Fibonacci number
  static int fibonacci(int n) {
    if (n <= 1) {  // Base case
      return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive call
  }

  public static void main(String[] args) {
    int terms = 7;
    System.out.print("Fibonacci Series: ");
    for (int i = 0; i < terms; i++) {
      System.out.print(fibonacci(i) + " ");
    }
  }
}

Expected Output:#

Fibonacci Series: 0 1 1 2 3 5 8

Explanation:

• fibonacci(0) returns 0 and fibonacci(1) returns 1 (base case).
• fibonacci(n) calls fibonacci(n-1) and fibonacci(n-2), summing their results.
• This process continues recursively until reaching the base case.

Recursion vs Iteration#

Pros and Cons of Recursion#

✅ Advantages:#

✔ Simplifies complex problems.

✔ Reduces code length (compared to loops).

✔ Useful for problems involving recursion naturally (e.g., trees, graphs).

❌ Disadvantages:#

✖ Uses more memory (each function call stores data in stack).

✖ Can cause StackOverflowError if recursion is too deep.

✖ Generally slower than loops due to function call overhead.

When to Use Recursion?#

Recursion is best used when:

• The problem can be broken down into smaller subproblems.
• You need to traverse hierarchical structures (e.g., trees, graphs).
• The iterative solution is too complex or requires deep nesting.

Conclusion#

• Recursion is a method that calls itself to solve problems.
• It consists of a base case (stopping condition) and a recursive case.
• It is useful for factorials, Fibonacci series, searching, sorting, and tree traversal.
• Although shorter and more readable, it consumes more memory than loops.
• Always ensure that recursion has a base case to avoid infinite recursion.

Using recursion wisely helps write cleaner, more efficient code!