← Back to Home

Recursive Methods

A recursive method is a method that calls itself to solve a problem by breaking it into smaller subproblems. Recursion is powerful for problems that have a natural repetitive structure. This is a high-value interview topic and essential for understanding algorithms, stack behavior, and problem decomposition.

What Is a Recursive Method?

A method that invokes itself
Solves a problem using smaller instances of the same problem
Must have a base condition to stop execution

void recursiveMethod() {
    recursiveMethod();
}

⚠️ This example causes infinite recursion (no base case).

Two Mandatory Components of Recursion

1. Base Case (Termination Condition)

Stops recursive calls
Prevents infinite recursion

if (n == 0) {
    return;
}

2. Recursive Case

Method calls itself with modified arguments

print(n - 1);

Simple Example: Print Numbers (1 to N)

void print(int n) {
    if (n == 0) {
        return;
    }
    print(n - 1);
    System.out.println(n);
}

Call: print(3)

Output:

1
2
3

Example: Factorial Using Recursion

Mathematical Definition

n! = n × (n-1)!
0! = 1

Java Code

int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

Example: Fibonacci Series (Classic Interview Question)

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

⚠️ Not efficient for large n due to repeated calls.

Recursive Call Execution (Call Stack Concept)

For factorial(3):

factorial(3)
 └─ factorial(2)
     └─ factorial(1)
         └─ factorial(0)

Then results return backward.

Recursion vs Iteration

Feature	Recursion	Iteration
Code readability	High (for some problems)	High
Memory usage	Higher (stack)	Lower
Performance	Slower	Faster
Complexity	Elegant logic	More control
Risk	StackOverflowError	Infinite loop

StackOverflowError (Important)

Occurs when:

Base case is missing
Recursive depth is too large

Exception in thread "main" java.lang.StackOverflowError

Tail Recursion (Conceptual)

A recursion where the recursive call is the last statement.

void print(int n) {
    if (n == 0) return;
    System.out.println(n);
    print(n - 1);
}

⚠️ Java does not optimize tail recursion automatically.

When to Use Recursion

Tree and graph traversal
Divide-and-conquer algorithms
Mathematical problems
Backtracking problems

When NOT to Use Recursion

Very large input size
Performance-critical loops
Simple repetitive logic
Risk of deep recursion

Common Beginner Mistakes

Missing base case
Wrong base condition
Infinite recursion
Expecting recursion to be faster
Ignoring stack memory usage

Interview-Ready Answers

Short Answer

A recursive method is a method that calls itself to solve a problem in smaller steps.

Detailed Answer

In Java, recursion involves a method invoking itself with a base condition to terminate execution. Each recursive call is stored in the call stack, and results return in reverse order. Proper base conditions are essential to avoid StackOverflowError.

Key Takeaway

Recursive methods provide elegant solutions for naturally recursive problems, but they must be used carefully due to memory and performance considerations.

Recursive Methods Examples (Java)

1. Basic Recursion (Countdown)

class Demo {
    static void countDown(int n) {
        if (n == 0) return;
        System.out.println(n);
        countDown(n - 1);
    }

    public static void main(String[] args) {
        countDown(3);
    }
}

Explanation

Base case: n == 0

Output:

3
2
1

2. Recursion Without Base Case (❌ Dangerous)

class Demo {
    static void test() {
        test();
    }

    public static void main(String[] args) {
        // test(); // StackOverflowError
    }
}

Explanation

No stopping condition

Causes StackOverflowError

3. Factorial Using Recursion

class Demo {
    static int factorial(int n) {
        if (n == 1) return 1;
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
    }
}

Explanation

Classic interview question

Output: 120

4. Factorial with n == 0 Base Case

class Demo {
    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(0));
    }
}

Explanation

Mathematically correct base case

Output: 1

5. Fibonacci Series (Recursive)

class Demo {
    static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fib(6));
    }
}

Explanation

Time complexity: exponential

Output: 8

6. Print Fibonacci Series Using Recursion

class Demo {
    static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 6; i++) {
            System.out.print(fib(i) + " ");
        }
    }
}

Explanation

Output: 0 1 1 2 3 5

7. Sum of Natural Numbers

class Demo {
    static int sum(int n) {
        if (n == 1) return 1;
        return n + sum(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(sum(5));
    }
}

Explanation

Output: 15

8. Power of a Number (x^n)

class Demo {
    static int power(int x, int n) {
        if (n == 0) return 1;
        return x * power(x, n - 1);
    }

    public static void main(String[] args) {
        System.out.println(power(2, 4));
    }
}

Explanation

Output: 16

9. Reverse a String Using Recursion

class Demo {
    static String reverse(String s) {
        if (s.length() == 0) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    public static void main(String[] args) {
        System.out.println(reverse("JAVA"));
    }
}

Explanation

Output: AVAJ

10. Check Palindrome Using Recursion

class Demo {
    static boolean isPalindrome(String s, int start, int end) {
        if (start >= end) return true;
        if (s.charAt(start) != s.charAt(end)) return false;
        return isPalindrome(s, start + 1, end - 1);
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("madam", 0, 4));
    }
}

Explanation

Output: true

11. Count Digits Using Recursion

class Demo {
    static int countDigits(int n) {
        if (n == 0) return 0;
        return 1 + countDigits(n / 10);
    }

    public static void main(String[] args) {
        System.out.println(countDigits(12345));
    }
}

Explanation

Output: 5

12. Sum of Digits Using Recursion

class Demo {
    static int sumDigits(int n) {
        if (n == 0) return 0;
        return (n % 10) + sumDigits(n / 10);
    }

    public static void main(String[] args) {
        System.out.println(sumDigits(123));
    }
}

Explanation

Output: 6

13. Recursion with Array Traversal

class Demo {
    static void printArray(int[] arr, int index) {
        if (index == arr.length) return;
        System.out.print(arr[index] + " ");
        printArray(arr, index + 1);
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        printArray(a, 0);
    }
}

Explanation

Output: 1 2 3

14. Find Maximum Element in Array (Recursion)

class Demo {
    static int max(int[] arr, int index) {
        if (index == arr.length - 1) return arr[index];
        return Math.max(arr[index], max(arr, index + 1));
    }

    public static void main(String[] args) {
        int[] a = {4, 9, 2};
        System.out.println(max(a, 0));
    }
}

Explanation

Output: 9

15. Binary Search Using Recursion

class Demo {
    static int binarySearch(int[] arr, int low, int high, int key) {
        if (low > high) return -1;

        int mid = (low + high) / 2;
        if (arr[mid] == key) return mid;
        if (key < arr[mid]) return binarySearch(arr, low, mid - 1, key);
        return binarySearch(arr, mid + 1, high, key);
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 5, 7, 9};
        System.out.println(binarySearch(a, 0, a.length - 1, 7));
    }
}

Explanation

Output: 3

16. Recursive Method Calling Another Recursive Method

class Demo {
    static void a(int n) {
        if (n == 0) return;
        b(n - 1);
    }

    static void b(int n) {
        if (n == 0) return;
        a(n - 1);
    }

    public static void main(String[] args) {
        a(3);
    }
}

Explanation

Indirect recursion

Common interview concept

17. Tail Recursion Example

class Demo {
    static void tail(int n) {
        if (n == 0) return;
        System.out.println(n);
        tail(n - 1);
    }

    public static void main(String[] args) {
        tail(3);
    }
}

Explanation

Recursive call is last statement

JVM does not optimize tail calls

18. Recursion vs Loop (Factorial Comparison)

class Demo {
    static int factorial(int n) {
        if (n == 1) return 1;
        return n * factorial(n - 1);
    }

    static int factorialLoop(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}

Explanation

Loop is more memory-efficient

Recursion uses call stack

19. Recursion Stack Trace Order

class Demo {
    static void test(int n) {
        if (n == 0) return;
        System.out.println("Before " + n);
        test(n - 1);
        System.out.println("After " + n);
    }

    public static void main(String[] args) {
        test(2);
    }
}

Explanation

Output:

Before 2
Before 1
After 1
After 2

20. Interview Summary – Recursive Methods

class Demo {
    static int sum(int n) {
        if (n == 0) return 0;
        return n + sum(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(sum(4));
    }
}

Explanation

Must have base case

Uses call stack

Output: 10