Recursion in Java

What is Recursion?

A method that calls itself. Each call works on a smaller problem until reaching a base case.

Anatomy of Recursion

public class Recursion {
    // Base case: stops recursion
    // Recursive case: calls itself with smaller input
    
    // Example: Factorial
    public static long factorial(int n) {
        // Base case
        if (n <= 1) {
            return 1;
        }
        // Recursive case
        return n * factorial(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println(factorial(5));  // 120
        System.out.println(factorial(10)); // 3628800
    }
}

Recursion Trace

factorial(5)
  5 * factorial(4)
    4 * factorial(3)
      3 * factorial(2)
        2 * factorial(1)
          return 1
        return 2 * 1 = 2
      return 3 * 2 = 6
    return 4 * 6 = 24
  return 5 * 24 = 120

Two Essential Parts

1. Base case: Condition to stop (no more recursive calls)
2. Recursive case: Calls itself with modified input toward base case

// Missing base case = infinite recursion = StackOverflowError!
public static void infinite() {
    infinite();  // NO BASE CASE!
}

// Always ensure progress toward base case
public static void countdown(int n) {
    if (n <= 0) {  // base case
        System.out.println("Done!");
        return;
    }
    System.out.println(n);
    countdown(n - 1);  // progress toward base case
}

How Recursion Uses the Stack

Each method call creates a new stack frame containing:

• Local variables
• Parameters
• Return address

public class StackFrames {
    public static int sum(int n) {
        if (n == 0) return 0;
        return n + sum(n - 1);
    }
    
    public static void main(String[] args) {
        // Each call adds a frame to the stack:
        // sum(4) → frame 1
        //   sum(3) → frame 2
        //     sum(2) → frame 3
        //       sum(1) → frame 4
        //         sum(0) → frame 5 (base case)
        //       return 0
        //     return 1 + 0 = 1
        //   return 2 + 1 = 3
        // return 3 + 3 = 6
        // return 4 + 6 = 10
        
        System.out.println(sum(4));  // 10
    }
}

Stack Overflow

// Too many recursive calls cause StackOverflowError
public class StackOverflow {
    public static void recurse(int n) {
        if (n == 0) return;
        recurse(n - 1);
    }
    
    public static void main(String[] args) {
        try {
            recurse(100000);  // too deep!
        } catch (StackOverflowError e) {
            System.out.println("Stack overflow!");
        }
    }
}

// Stack size varies:
// - Usually 512KB to 1MB
// - Each frame ~100-1000 bytes
// - Max depth ~10,000-50,000 calls

Visualizing Stack Frames

┌─────────────────────┐
│ main()              │  Stack
├─────────────────────┤
│ factorial(5)        │  ← n=5
├─────────────────────┤
│ factorial(4)        │  ← n=4
├─────────────────────┤
│ factorial(3)        │  ← n=3
├─────────────────────┤
│ factorial(2)        │  ← n=2
├─────────────────────┤
│ factorial(1)        │  ← n=1 (base case)
└─────────────────────┘

Tail Recursion

// Regular recursion: operation AFTER recursive call
public static long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // multiplication after call
}

// Tail recursion: operation BEFORE recursive call
public static long factorialTail(int n, long acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);  // multiplication before call
}

// Java does NOT optimize tail recursion!
// But it's still a useful pattern

// Usage:
// factorialTail(5, 1) → factorialTail(4, 5) → factorialTail(3, 20) → ...
// Same result, but no pending operations on stack

Common Base Case Patterns

// Pattern 1: Simple boundary
public static int sum(int[] arr, int index) {
    if (index >= arr.length) return 0;  // base case
    return arr[index] + sum(arr, index + 1);
}

// Pattern 2: Value check
public static int power(int base, int exp) {
    if (exp == 0) return 1;  // base case
    if (exp < 0) return 1 / power(base, -exp);  // handle negatives
    return base * power(base, exp - 1);
}

// Pattern 3: String length
public static boolean isPalindrome(String s) {
    if (s.length() <= 1) return true;  // base case
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalindrome(s.substring(1, s.length() - 1));
}

// Pattern 4: Two pointers
public static boolean isPalindrome(char[] arr, int left, int right) {
    if (left >= right) return true;  // base case
    if (arr[left] != arr[right]) return false;
    return isPalindrome(arr, left + 1, right - 1);
}

Multi-way Base Cases

// Fibonacci
public static int fib(int n) {
    if (n <= 0) return 0;  // base case 1
    if (n == 1) return 1;  // base case 2
    return fib(n - 1) + fib(n - 2);
}

// Tower of Hanoi
public static void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {  // base case
        System.out.println("Move disk 1 from " + from + " to " + to);
        return;
    }
    hanoi(n - 1, from, aux, to);
    System.out.println("Move disk " + n + " from " + from + " to " + to);
    hanoi(n - 1, aux, to, from);
}

Ensuring Progress

// BAD: no progress toward base case
public static void badRecursion(int n) {
    if (n == 0) return;
    badRecursion(n);  // same n! infinite loop
}

// GOOD: progress toward base case
public static void goodRecursion(int n) {
    if (n == 0) return;
    goodRecursion(n - 1);  // n decreases!
}

// Check: does each recursive call move closer to base case?
// If n decreases: progress ✓
// If n stays same: infinite recursion ✗

Pattern 1: Linear Recursion

// Factorial
public static long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Sum of array
public static int sum(int[] arr, int index) {
    if (index >= arr.length) return 0;
    return arr[index] + sum(arr, index + 1);
}

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

Pattern 2: Binary Recursion

// Fibonacci (two recursive calls)
public static int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

// Power (efficient)
public static double power(double base, int exp) {
    if (exp == 0) return 1;
    if (exp % 2 == 0) {
        double half = power(base, exp / 2);
        return half * half;
    }
    return base * power(base, exp - 1);
}

Pattern 3: Divide and Conquer

// Merge Sort
public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;  // base case
    
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);      // sort left half
    mergeSort(arr, mid + 1, right); // sort right half
    merge(arr, left, mid, right);   // merge halves
}

// Binary Search
public static int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) return -1;  // base case
    
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binarySearch(arr, target, mid + 1, right);
    return binarySearch(arr, target, left, mid - 1);
}

Pattern 4: Backtracking

// Generate all subsets
public static void subsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) {
    if (index >= nums.length) {
        result.add(new ArrayList<>(current));  // base case
        return;
    }
    
    // Don't include nums[index]
    subsets(nums, index + 1, current, result);
    
    // Include nums[index]
    current.add(nums[index]);
    subsets(nums, index + 1, current, result);
    current.remove(current.size() - 1);  // backtrack
}

// Permutations
public static void permute(int[] nums, int start, List<List<Integer>> result) {
    if (start == nums.length) {
        result.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
        return;
    }
    
    for (int i = start; i < nums.length; i++) {
        swap(nums, start, i);
        permute(nums, start + 1, result);
        swap(nums, start, i);  // backtrack
    }
}

Pattern 5: Tree Recursion

// Tree node
class TreeNode {
    int val;
    TreeNode left, right;
}

// Tree traversals
public void inorder(TreeNode node) {
    if (node == null) return;  // base case
    inorder(node.left);
    System.out.print(node.val + " ");
    inorder(node.right);
}

// Tree height
public int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

// Check if tree is balanced
public boolean isBalanced(TreeNode node) {
    if (node == null) return true;
    int leftHeight = height(node.left);
    int rightHeight = height(node.right);
    return Math.abs(leftHeight - rightHeight) <= 1
        && isBalanced(node.left)
        && isBalanced(node.right);
}