Java Recursion - Complete Tutorial

1. Introduction to Recursion

Recursion solves problems by breaking them into smaller instances of the same problem. Every recursive algorithm needs a base case and a recursive case.

• Function calls itself
• Base case stops recursion
• Recursive case moves toward base
• Uses call stack for state

public class RecursionIntro {
    static void countdown(int n) {
        if (n == 0) return;
        System.out.println(n);
        countdown(n - 1);
    }
    public static void main(String[] args) {
        countdown(3);
    }
}

2. Why Is Recursion Required?

Not every problem needs recursion, but some problems are naturally defined in terms of smaller versions of themselves. Recursion is required (or strongly preferred) when:

• The problem definition itself is recursive (factorial, Fibonacci, tree height)
• Data is recursive in shape (trees, linked lists, file folders)
• Divide-and-conquer is the clearest solution (merge sort, quick sort, binary search)
• Backtracking needs to explore choices and undo them (maze, N-Queens, permutations)
• The iterative version would need an explicit stack you manage by hand — recursion uses the JVM call stack for you

3. Applications of Recursion

4. Iterative vs Recursion

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

    static int factorialRecursive(int n) {
        if (n <= 1) return 1;
        return n * factorialRecursive(n - 1);
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("Iterative: " + factorialIterative(n));
        System.out.println("Recursive: " + factorialRecursive(n));
    }
}

5. Classic Recursive Algorithms

Factorial, Fibonacci, and binary search are textbook recursive examples. Understanding them builds intuition for tree and graph recursion.

• Factorial: n! = n * (n-1)!
• Fibonacci: F(n) = F(n-1) + F(n-2)
• Binary search halves search space
• Tower of Hanoi moves disks recursively

public class Fibonacci {
    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));
    }
}

6. How Recursion Uses the Stack

Each recursive call pushes a new stack frame onto the JVM call stack. The frame stores local variables (e.g. n), return address, and pending work until the inner call returns.

Example: factorial(4)

Growing phase — calls stack up until base case:

• main → factorial(4) → factorial(3) → factorial(2) → factorial(1)

Unwinding phase — returns multiply backward:

public class FactorialStack {
    static int factorial(int n) {
        System.out.println("  Enter factorial(" + n + ")");
        if (n <= 1) {
            System.out.println("  Base case, return 1");
            return 1;
        }
        int result = n * factorial(n - 1);
        System.out.println("  Leave factorial(" + n + "), return " + result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("Result: " + factorial(4));
    }
}

Depth for factorial(n) is O(n) frames at once — why very large n can cause StackOverflowError.

7. Disadvantages of Recursion

8. Recursion Tree Visualization

Drawing the call tree shows how recursive calls branch and reunite. Each node is a call; edges show the next smaller subproblem.

• Root is initial call
• Leaves are base cases
• Depth equals maximum stack depth
• Overlapping subproblems suggest memoization

public class Trace {
    static int sum(int n) {
        System.out.println("sum(" + n + ")");
        if (n == 0) return 0;
        return n + sum(n - 1);
    }
    public static void main(String[] args) {
        System.out.println("Result: " + sum(3));
    }
}

9. Tail Recursion

Tail recursion occurs when the recursive call is the last operation. Some languages optimize it to iteration; Java does not guarantee tail-call optimization.

• Last action is recursive call
• Can carry result in accumulator parameter
• Rewrite as loop for efficiency in Java
• Still useful for expressing logic clearly

public class TailSum {
    static int sum(int n, int acc) {
        if (n == 0) return acc;
        return sum(n - 1, acc + n);
    }
    public static void main(String[] args) {
        System.out.println(sum(5, 0));
    }
}

10. Recursion Best Practices

Use recursion when it simplifies the solution, but watch stack overflow and redundant work.

• Always define a reachable base case
• Ensure each recursive step moves toward the base case
• Use memoization for overlapping subproblems
• Prefer iteration when performance or depth is critical
• Test with small inputs first

11. Tricky Points

Common recursion mistakes in Java exams and coding practice.