OBJECT ORIENTED PROGRAMMING THROUGH JAVA : Unit - 2 : Topic - 14 : Recursive Methods

 

Unit - 2

Topic - 14 : Recursive Methods

Recursion is the process where a method calls itself, either directly or indirectly.
In Java, recursion is often used to solve problems that can be broken down into smaller subproblems of the same type.

A recursive method must have:

1. Base Case – A condition that stops further recursive calls.

2. Recursive Call – The method calls itself with a modified argument.

---

Example: Factorial using Recursion

// A simple example of recursion (factorial)
class Factorial {
    // This is a recursive function
    int fact(int n) {
        if (n == 1) // Base case
            return 1;
        return fact(n - 1) * n; // Recursive call
    }
}

class Recursion {
    public static void main(String args[]) {
        Factorial f = new Factorial();
        System.out.println("Factorial of 3 is " + f.fact(3));
        System.out.println("Factorial of 4 is " + f.fact(4));
        System.out.println("Factorial of 5 is " + f.fact(5));
    }
}

---

Output:

Factorial of 3 is 6
Factorial of 4 is 24
Factorial of 5 is 120

---

How it Works (Factorial Example)

For fact(3):

1. fact(3) → calls fact(2)

2. fact(2) → calls fact(1)

3. fact(1) → returns 1 (base case)

4. Return chain:

   • fact(2) returns 1 * 2 = 2

   • fact(3) returns 2 * 3 = 6

---

✅ Key Points:

• Base case prevents infinite recursion.

• Recursive methods are often shorter and cleaner, but can be less efficient due to repeated method calls.

• Common uses:

• Mathematical problems (factorial, Fibonacci, GCD)

• Tree/graph traversals

• Divide-and-conquer algorithms (Merge Sort, Quick Sort)

Example 2: Fibonacci Series using Recursion

The Fibonacci sequence is a series of numbers where:

F(0) = 0  
F(1) = 1  
F(n) = F(n-1) + F(n-2)  (for n > 1)

---

Java Program

// Fibonacci series using recursion
class Fibonacci {
    // Recursive method to find nth Fibonacci number
    int fib(int n) {
        if (n == 0) // Base case 1
            return 0;
        else if (n == 1) // Base case 2
            return 1;
        else
            return fib(n - 1) + fib(n - 2); // Recursive calls
    }
}

class RecursionFibonacci {
    public static void main(String args[]) {
        Fibonacci f = new Fibonacci();

        System.out.print("Fibonacci series for first 7 terms: ");
        for (int i = 0; i < 7; i++) {
            System.out.print(f.fib(i) + " ");
        }
    }
}

---

Output

Fibonacci series for first 7 terms: 0 1 1 2 3 5 8

---

How it Works

For fib(5):

1. fib(5) → fib(4) + fib(3)

2. fib(4) → fib(3) + fib(2)

3. fib(3) → fib(2) + fib(1)
   ...and so on, until it reaches the base cases (fib(0) and fib(1)).

---

✅ Key Points:

• Uses two base cases (n==0 and n==1).

• Shows how recursion can branch into multiple calls.

• Not very efficient for large n because of repeated calculations — but great for understanding recursion.