Recursion

Recursion is when a method calls itself to solve a smaller version of the same problem. It sounds circular at first, but it is one of the most elegant tools in programming — once you understand the two rules it depends on, many complex problems become surprisingly simple.

The Two Rules of Recursion

Every correct recursive method must have:

1. A base case — a condition where the method stops calling itself and returns a direct answer.
2. A recursive case — where the method calls itself with a smaller or simpler input, moving toward the base case.

Without a base case, recursion never stops and you get a StackOverflowError. Without progress toward the base case, same result.

Tip: Think of recursion as breaking a problem into: “I can handle this small piece — and for the rest, I’ll trust myself to handle it too.”

Your First Recursive Method: Factorial

The factorial of a number n (written n!) is n × (n-1) × (n-2) × … × 1. The base case is 0! = 1.

public class Factorial {

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

    public static void main(String[] args) {
        System.out.println(factorial(5)); // 5 * 4 * 3 * 2 * 1
        System.out.println(factorial(0));
    }
}

Output:

120
1

Each call to factorial waits for the next one to return, then multiplies the result. Tracing it manually helps:

factorial(5)
  → 5 * factorial(4)
       → 4 * factorial(3)
            → 3 * factorial(2)
                 → 2 * factorial(1)
                      → 1 * factorial(0)
                           → 1   ← base case returns

Fibonacci Sequence

The Fibonacci sequence is another classic: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1.

public class Fibonacci {

    static int fib(int n) {
        if (n <= 1) return n; // base cases: fib(0)=0, fib(1)=1
        return fib(n - 1) + fib(n - 2);
    }

    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

Warning: This naive Fibonacci is exponential in time complexity — fib(40) makes over a billion calls. For real use, cache results (memoization) or use iteration instead. See the performance section below.

Summing an Array Recursively

Recursion is not just for math. Here it sums an int[] by handling one element at a time:

public class ArraySum {

    static int sum(int[] arr, int index) {
        if (index == arr.length) return 0; // base case: nothing left
        return arr[index] + sum(arr, index + 1);
    }

    public static void main(String[] args) {
        int[] nums = {3, 7, 2, 9, 4};
        System.out.println(sum(nums, 0)); // start from index 0
    }
}

Output:

25

Printing in Reverse with Recursion

A handy trick: do work after the recursive call to reverse order of processing.

public class ReversePrint {

    static void printReverse(int n) {
        if (n == 0) return;      // base case
        printReverse(n - 1);     // recurse first...
        System.out.print(n + " "); // ...then print on the way back up
    }

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

Output:

1 2 3 4 5

Compare this with printing before the recursive call — that would print 5 4 3 2 1. Where you place the logic relative to the recursive call completely changes the behavior.

Indirect Recursion (Mutual Recursion)

Two methods can call each other — this is called indirect or mutual recursion. It is less common but valid:

public class MutualRecursion {

    static boolean isEven(int n) {
        if (n == 0) return true;
        return isOdd(n - 1);
    }

    static boolean isOdd(int n) {
        if (n == 0) return false;
        return isEven(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(isEven(4)); // true
        System.out.println(isOdd(7));  // true
    }
}

Output:

true
true

Note: Mutual recursion can be harder to trace and debug. Make sure both methods have clear base cases that break the cycle.

Recursion vs Iteration

Most recursive solutions can be rewritten as loops. Knowing when to choose which is a core skill.

Aspect	Recursion	Iteration
Code clarity	Often cleaner for tree/graph problems	Cleaner for simple counted loops
Memory	Uses call stack — risk of StackOverflowError	Fixed memory, no stack overhead
Performance	Extra method-call overhead per step	Generally faster in tight loops
Tail-call opt.	Java does NOT optimize tail calls	Not applicable
Best for	Tree traversal, divide-and-conquer, backtracking	Simple counting, array scans

For the for loop or while loop equivalent of factorial:

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

This is faster and will never blow the stack. Prefer iteration when the recursive version gives no clarity benefit.

Under the Hood

The Call Stack

Every time a method is called in Java, the JVM pushes a stack frame onto the call stack. The frame holds local variables, the return address, and operand data. When the method returns, the frame is popped.

Recursive calls are no different — each call gets its own frame. For factorial(5), six frames are pushed before any are popped. The default stack size in the JVM is roughly 512 KB – 1 MB per thread, which translates to roughly 500–10,000 recursive calls depending on the frame size.

Call factorial(100_000) and you will see:

Exception in thread "main" java.lang.StackOverflowError

Why Java Does Not Optimize Tail Calls

A tail-recursive method makes the recursive call as its very last operation and does nothing after it returns. Some languages (like Scala, Kotlin with tailrec) transform tail calls into a loop at the bytecode level, eliminating stack growth.

Java’s JVM specification does not guarantee tail-call optimization (TCO). The JIT compiler may optimize some cases, but you cannot rely on it. If you need deep recursion in Java, rewrite it iteratively or use an explicit stack (a Deque) to simulate the call stack on the heap.

Memoization Pattern

The repeated-subproblems problem (like naive Fibonacci) is solved by caching results:

import java.util.HashMap;
import java.util.Map;

public class MemoFib {

    private static Map<Integer, Long> cache = new HashMap<>();

    static long fib(int n) {
        if (n <= 1) return n;
        if (cache.containsKey(n)) return cache.get(n);
        long result = fib(n - 1) + fib(n - 2);
        cache.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fib(50)); // instant, not billions of calls
    }
}

Output:

12586269025

With memoization, each unique value is computed exactly once — bringing Fibonacci from O(2ⁿ) down to O(n).

Common Mistakes

• Missing the base case — results in infinite recursion and StackOverflowError.
• Base case never reached — e.g., passing a negative number to factorial without guarding for it.
• Modifying shared state inside recursion — use method parameters or return values to pass data, not fields you mutate in place.
• Ignoring the return value — a recursive call that returns a value must have its result used (returned or combined).

Tip: When debugging recursion, add a System.out.println at the start of the method to print the current argument. Watching the values shrink toward the base case (or not) tells you exactly what is happening.

Related Topics

• Methods — recursion is just a method calling itself; solid method knowledge is a prerequisite.
• call-by-value — understanding how Java passes arguments explains why recursive calls get their own independent copies of primitive parameters.
• Stack — the java.util.Stack class lets you simulate recursion iteratively when the call stack is too deep.
• How Loops Work (Bytecode & JIT) — understand how the JVM executes loops and method calls at the bytecode level.
• Sorting Collections — merge sort and quicksort are classic recursive algorithms used under the hood in Java sorting.
• Design Patterns — the Composite and Visitor patterns rely heavily on recursive traversal of tree structures.