Recursion

Solve problems by having a method call itself - understand the base case, recursive case, and call stack.

Overview

Recursion is when a method calls itself to solve a smaller version of the same problem. Every recursive solution needs two things: a base case (the simplest case that returns without recursing) and a recursive case (where the method calls itself with a simpler input moving toward the base case). Recursion can make some problems elegant and readable - factorial, Fibonacci, tree traversal, and divide-and-conquer algorithms. However, deep recursion can cause a StackOverflowError if the base case is never reached.

Key Points

•A recursive method calls itself with a smaller/simpler input
•Base case: the condition that stops the recursion and returns directly
•Recursive case: calls itself with input that moves toward the base case
•Each call adds a stack frame - too many levels causes StackOverflowError
•Every recursion can be rewritten as a loop (and vice versa)
•Recursion is natural for problems defined in terms of themselves (factorial, Fibonacci, tree traversal)

Examples

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

public class Main {
    static int factorial(int n) {
        // Base case
        if (n <= 1) return 1;
        // Recursive case: n! = n * (n-1)!
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(1));  // 1
        System.out.println(factorial(5));  // 120
        System.out.println(factorial(10)); // 3628800
    }
}

factorial(5) → 5 * factorial(4) → 5 * 4 * factorial(3) → ... → 5*4*3*2*1 = 120.

Fibonacci sequence

public class Main {
    static int fibonacci(int n) {
        if (n <= 1) return n;  // Base cases: fib(0)=0, fib(1)=1
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.print(fibonacci(i) + " ");
        }
        // 0 1 1 2 3 5 8 13 21 34 55
    }
}

This naive implementation is exponential - it recalculates the same values many times. For large n, use a loop or memoisation.

Sum of digits of a number

public class Main {
    static int digitSum(int n) {
        if (n < 10) return n;         // Base case: single digit
        return (n % 10) + digitSum(n / 10); // last digit + sum of rest
    }

    public static void main(String[] args) {
        System.out.println(digitSum(12345)); // 15 (1+2+3+4+5)
        System.out.println(digitSum(9));     // 9
        System.out.println(digitSum(100));   // 1
    }
}

n % 10 gives the last digit; n / 10 removes it. This recurses until a single digit remains.

Common Mistakes

Missing base case: the recursion never stops and throws StackOverflowError
Base case that doesn't cover all terminal conditions - e.g., forgetting n == 0 alongside n == 1
Recursive call that doesn't move toward the base case: `factorial(n)` calling `factorial(n)` is an infinite loop

Note

When designing a recursive method: (1) identify the simplest case(s) first - those are your base cases. (2) Assume your method correctly solves the smaller problem, then use that result to solve the current problem.

Recursion

Overview

Key Points

Examples

Common Mistakes

Note

Exercises

Knowledge Check

What is the purpose of the base case in a recursive method?