Java Recursion — Recursive Methods Explained with Examples

Recursion is when a method calls itself. It’s a powerful technique for problems that can be broken down into smaller versions of the same problem.

---

How Recursion Works

Every recursive method needs:

1. Base case — when to stop
2. Recursive case — the method calls itself with a smaller input

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

System.out.println(factorial(5));  // 120

Execution Trace

factorial(5)
  → 5 * factorial(4)
    → 4 * factorial(3)
      → 3 * factorial(2)
        → 2 * factorial(1)
          → 1  (base case)
        → 2 * 1 = 2
      → 3 * 2 = 6
    → 4 * 6 = 24
  → 5 * 24 = 120

Each call creates a stack frame. When the base case is reached, the frames unwind and return values back up.

---

Classic Examples

Fibonacci Numbers

public static int fibonacci(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
for (int i = 0; i < 10; i++) {
    System.out.print(fibonacci(i) + " ");
}

⚠️ This naive implementation is very slow for large n because it recalculates the same values. Use memoization or iteration for real use.

Sum of Digits

public static int sumOfDigits(int n) {
    if (n == 0) return 0;
    return (n % 10) + sumOfDigits(n / 10);
}

System.out.println(sumOfDigits(1234));  // 10

Power

public static long power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

System.out.println(power(2, 10));  // 1024

Reverse a String

public static String reverse(String s) {
    if (s.length() <= 1) return s;
    return reverse(s.substring(1)) + s.charAt(0);
}

System.out.println(reverse("hello"));  // olleh

Binary Search (Recursive)

public static int binarySearch(int[] arr, int target, int low, int high) {
    if (low > high) return -1;  // not found

    int mid = (low + high) / 2;

    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binarySearch(arr, target, mid + 1, high);
    return binarySearch(arr, target, low, mid - 1);
}

---

The Call Stack

Each method call is pushed onto the call stack. Too many calls cause a StackOverflowError.

// DANGER — no base case!
public static void infinite() {
    infinite();  // StackOverflowError
}

Java’s default stack size allows roughly 5,000–10,000 frames (varies by JVM and frame size).

---

Recursion vs Iteration

Every recursive solution can be rewritten with a loop:

// Recursive
public static int factorialRec(int n) {
    if (n <= 1) return 1;
    return n * factorialRec(n - 1);
}

// Iterative
public static int factorialIter(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

	Recursion	Iteration
Readability	Often cleaner for tree/divide-and-conquer problems	Cleaner for simple counting
Memory	Uses stack frames (risk of overflow)	Constant extra memory
Performance	Can be slower (function call overhead)	Generally faster
Use when	Problem is naturally recursive (trees, graphs, divide & conquer)	Simple repetition

---

Tail Recursion

A recursive call is tail recursive if it’s the last thing the method does:

// Tail recursive — the recursive call is the last operation
public static int factorialTail(int n, int accumulator) {
    if (n <= 1) return accumulator;
    return factorialTail(n - 1, n * accumulator);
}

// Usage
System.out.println(factorialTail(5, 1));  // 120

⚠️ Java does not optimize tail recursion (unlike Scala or Kotlin). You still risk StackOverflowError.

---

Memoization — Optimizing Recursive Solutions

Cache results to avoid redundant calculations:

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

public static long fibMemo(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (cache.containsKey(n)) return cache.get(n);

    long result = fibMemo(n - 1) + fibMemo(n - 2);
    cache.put(n, result);
    return result;
}

System.out.println(fibMemo(50));  // 12586269025 — instant!

---

Quick Exercises

1. Write a recursive method to check if a string is a palindrome.
2. Write a recursive method to calculate the GCD of two numbers.
3. Write a recursive method to print all permutations of a string.
4. Convert the recursive Fibonacci to an iterative version.

---

Summary

• Recursion = method calls itself
• Always have a base case to prevent infinite recursion
• Each call uses a stack frame → risk of StackOverflowError
• Use recursion for naturally recursive problems (trees, divide & conquer)
• Use iteration for simple repetition
• Memoization can dramatically improve recursive performance

---

What’s Next?

Let’s wrap up Core Java Basics with tips on writing clean, readable code: Writing Clean and Readable Code.