Metadata Card

• Prerequisites: Ch5 (Methods & Stack)
• Estimated time: 45 min
• Core difficulty: (Advanced)
• Reading mode: High focus
• Completion marker: Can identify recursive problems, write recursive methods, identify base case vs recursive case

The Breakthrough · Tracing the Origins

A method that calls itself is recursive. It sounds circular, but with a proper "stopping condition" (base case), it's one of the most elegant programming concepts.

Act 1: The Self-Referencing Method

public static int factorial(int n) {
 // Base case: stop when n <= 1
 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(5)); // 120
}

Language: Java Expected output: 120What happens: factorial(5) → 5 * factorial(4) → 4 * factorial(3) → ... → 1 * factorial(1) = 1, then unwinds

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

Every recursion needs:

1. Base case: The condition that stops the recursion (n <= 1)
2. Recursive case: The call that moves toward the base case (n - 1)

The Stack and Recursion

Each recursive call pushes a new frame onto the call stack. factorial(5) creates 5 frames.

Stack overflow: If recursion goes too deep (no base case, or too many calls), the stack overflows:

public static void infinite() {
 infinite(); // StackOverflowError!
}

Classic Examples

Fibonacci:

public static int fib(int n) {
 if (n <= 1) return n;
 return fib(n - 1) + fib(n - 2);
}
// fib(6) = 8

Performance warning: This naive Fibonacci is O(2^n). For real use, use memoization or iteration.

Power of 2:

public static int powerOf2(int n) {
 if (n == 0) return 1;
 return 2 * powerOf2(n - 1);
}
// powerOf2(3) = 8

Final Challenge

1. Write a recursive method sum(int n) that returns 1 + 2 + ... + n
2. Write a recursive method reverseString(String s) that returns the reversed string
3. Write a recursive method gcd(int a, int b) using Euclid's algorithm

Traveler's Notes

Recursion = a method calling itself.
Every recursion needs a base case (stop) and a recursive case (progress).
Deep recursion can cause StackOverflowError.
Every recursive solution can also be written iteratively — but some problems are naturally recursive (tree traversal, divide-and-conquer).