Java Recursion

Recursion is a technique where a method calls itself to solve a problem. Instead of using a loop, recursion breaks a problem into smaller sub-problems of the same type, solves the simplest version first, and builds up the final answer from there.

Think of recursion like a mirror facing another mirror — each reflection contains a smaller version of itself, and eventually it reaches an end.

How Recursion Works

Every recursive method must have two key parts:

1. Base Case: The simplest version of the problem that can be solved directly, without further recursion. This stops the recursion from going on forever.
2. Recursive Case: The part where the method calls itself with a smaller or simpler version of the problem, moving closer to the base case.

If the base case is missing, the method calls itself endlessly, causing a StackOverflowError.

Basic Syntax of a Recursive Method

returnType methodName(parameters) {
    if (base case condition) {
        return base case value;
    }
    // recursive call with a simpler input
    return methodName(simpler parameters);
}

Example 1 – Countdown

public class CountDown {

    static void countDown(int n) {
        if (n == 0) {
            System.out.println("Go!");
            return;   // base case – stop recursion
        }
        System.out.println(n);
        countDown(n - 1);   // recursive call with smaller value
    }

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

Output:

5
4
3
2
1
Go!

Example 2 – Factorial

The factorial of a number n (written as n!) is the product of all positive integers from 1 to n.

5! = 5 × 4 × 3 × 2 × 1 = 120

Factorial is defined recursively as:

• Base case: 0! = 1
• Recursive case: n! = n × (n-1)!

public class Factorial {

    static int factorial(int n) {
        if (n == 0) {
            return 1;   // base case
        }
        return n * factorial(n - 1);   // recursive call
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));   // 120
        System.out.println("6! = " + factorial(6));   // 720
    }
}

How It Works – Call Stack Trace for factorial(4)

factorial(4)
  → 4 * factorial(3)
        → 3 * factorial(2)
              → 2 * factorial(1)
                    → 1 * factorial(0)
                          → returns 1   ← base case reached
                    returns 1 * 1 = 1
              returns 2 * 1 = 2
        returns 3 * 2 = 6
  returns 4 * 6 = 24

Example 3 – Fibonacci Sequence

The Fibonacci sequence is a series where each number is the sum of the two preceding ones:

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

• Base cases: fib(0) = 0, fib(1) = 1
• Recursive case: fib(n) = fib(n-1) + fib(n-2)

public class Fibonacci {

    static int fib(int n) {
        if (n == 0) return 0;   // base case 1
        if (n == 1) return 1;   // base case 2
        return fib(n - 1) + fib(n - 2);   // recursive call
    }

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

Output:

0 1 1 2 3 5 8 13 21 

Example 4 – Sum of Natural Numbers

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 of 1 to 5: " + sum(5));   // 15
}

Example 5 – Reverse a String

static String reverse(String s) {
    if (s.isEmpty()) return s;   // base case
    return reverse(s.substring(1)) + s.charAt(0);   // recursive
}

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

Recursion vs Iteration

Important Notes

• Every recursive method must have a base case or it will run indefinitely and crash.
• Each recursive call uses memory on the call stack. Too many calls can cause StackOverflowError.
• Recursion is naturally suited for problems with a self-similar structure: trees, factorials, sorting algorithms like merge sort.

Summary

• Recursion is when a method calls itself to solve a problem.
• Every recursive method needs a base case (stopping condition) and a recursive case.
• The base case prevents infinite recursion and eventual stack overflow.
• Classic examples include: factorial, Fibonacci, reverse a string, sum of numbers.
• Recursion is elegant for certain problems but may use more memory than iterative approaches.