Recursion

By the end of this lesson, you will be able to trace recursive methods, identify base cases, write recursive solutions, and understand the call stack.

What Is Recursion?

A method is recursive if it calls itself. Every recursive method needs:

1. Base case: the stopping condition — does NOT call itself
2. Recursive case: calls itself with a smaller/simpler version of the problem

Classic: Factorial

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

$n! = n \times (n-1) \times \ldots \times 1$ and $0! = 1$

Trace: factorial(4)

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

Classic: Fibonacci

public 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); // recursive case
}

Trace: fib(4)

fib(4) = fib(3) + fib(2)
       = (fib(2) + fib(1)) + (fib(1) + fib(0))
       = ((fib(1) + fib(0)) + 1) + (1 + 0)
       = ((1 + 0) + 1) + 1
       = (1 + 1) + 1 = 3

Note: recursive Fibonacci has exponential time complexity — many redundant calls.

Recursion on Strings

// Reverse a string
public static String reverse(String s) {
    if (s.length() <= 1) return s;              // base case
    return reverse(s.substring(1)) + s.charAt(0); // recursive case
}
// reverse("hello") → reverse("ello") + 'h' → ... → "olleh"

Recursion on Arrays

// Sum of array from index start to end
public static int arraySum(int[] arr, int start) {
    if (start >= arr.length) return 0;          // base case: past end
    return arr[start] + arraySum(arr, start + 1); // recursive case
}
// Call: arraySum(arr, 0)

The Call Stack

Each recursive call adds a to the call stack. When the base case is hit, frames unwind one by one.