Recursion

Recursion is a technique where a function calls itself to solve a smaller version of the same problem.

Real-World Analogy

Imagine you're in a line at a coffee shop and want to know your position. You ask the person ahead: "What position are you?" They ask the person ahead of them. This continues until someone at the front says "I'm first!" Then the answer propagates back: "I'm second," "I'm third," until you learn your position.

That's recursion — solving a problem by breaking it into smaller instances of itself.

How It Works in Memory

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

When factorial(4) is called:

Call Stack Growth:

factorial(4)     →  n=4, waits for factorial(3)
  factorial(3)   →  n=3, waits for factorial(2)
    factorial(2) →  n=2, waits for factorial(1)
      factorial(1) → n=1, returns 1  ← Base case hit!
    returns 2 * 1 = 2
  returns 3 * 2 = 6
returns 4 * 6 = 24

Two Essential Components

1. Base Case: The condition that stops the recursion. Without it, you get a StackOverflowError.
2. Recursive Case: The part where the function calls itself with a smaller input.

public int sum(int n) {
    if (n <= 0) return 0;     // Base case: stops recursion
    return n + sum(n - 1);    // Recursive case: smaller problem
}

Why Recursion Matters

Many problems are naturally recursive:

• Trees: Every subtree is a smaller tree
• Graphs: Visiting neighbors is exploring a smaller graph
• Divide and Conquer: Splitting a problem in half
• Dynamic Programming: Breaking into subproblems

Without recursion, you'd need explicit stacks and complex loop logic for these problems.

Every recursive function follows this template:

ReturnType solve(problem) {
    // Step 1: Base case
    if (problem is small enough) {
        return direct solution;
    }
    
    // Step 2: Recursive case
    smallerProblem = reduce(problem);
    recursiveResult = solve(smallerProblem);
    
    // Step 3: Combine results
    return combine(current, recursiveResult);
}

Example: Power Function

public double myPow(double x, int n) {
    // Base case
    if (n == 0) return 1.0;
    
    // Handle negative exponents
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    
    // Recursive case: x^n = x * x^(n-1)
    return x * myPow(x, n - 1);
}
// Time: O(n), Space: O(n) for call stack

Example: Sum of Digits

public int digitSum(int n) {
    // Base case: single digit
    if (n < 10) return n;
    
    // Recursive case: last digit + sum of rest
    return (n % 10) + digitSum(n / 10);
}
// digitSum(1234) → 4 + digitSum(123) → 4 + 3 + digitSum(12) → 4 + 3 + 2 + digitSum(1) → 4 + 3 + 2 + 1 = 10

Example: Reverse String

public String reverse(String s) {
    if (s.length() <= 1) return s;
    return reverse(s.substring(1)) + s.charAt(0);
}
// reverse("hello") → reverse("ello") + "h" → "olle" + "h" → "olleh"

The Call Stack Visualization

reverse("hello")
  reverse("ello")
    reverse("llo")
      reverse("lo")
        reverse("o")
          returns "o"
        returns "o" + "l" = "ol"
      returns "ol" + "l" = "oll"
    returns "oll" + "e" = "olle"
  returns "olle" + "h" = "olleh"

Key Insight

The base case is the most important part. Always ask: "What is the smallest version of this problem that I can solve directly?"

Pattern 1: Linear Recursion

One recursive call per function invocation.

// Factorial: f(n) = n * f(n-1)
public int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
// Call tree: linear chain
// factorial(5) → 5 * factorial(4) → 5 * 4 * factorial(3) → ...

Use when: Problem reduces by a constant amount each step.

Pattern 2: Binary Recursion

Two recursive calls per function invocation.

// Fibonacci: f(n) = f(n-1) + f(n-2)
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
// Call tree: binary tree
//           fib(5)
//          /       \
//      fib(4)     fib(3)
//      /    \\     /    \
//  fib(3) fib(2) fib(2) fib(1)

Warning: Without memoization, this is O(2^n). See DP topic for optimization.

Pattern 3: Tail Recursion

The recursive call is the last operation.

// Tail-recursive factorial
public int factorialHelper(int n, int accumulator) {
    if (n <= 1) return accumulator;
    return factorialHelper(n - 1, n * accumulator);  // Last operation
}
public int factorial(int n) {
    return factorialHelper(n, 1);
}

Advantage: Can be optimized to iteration by the compiler (Java doesn't do this, but it's good practice).

Pattern 4: Tree Recursion

Recursive calls mirror tree structure.

// Traverse a binary tree
public void traverse(TreeNode root) {
    if (root == null) return;
    
    System.out.println(root.val);  // Process current
    traverse(root.left);            // Recurse left
    traverse(root.right);           // Recurse right
}

Use when: Problem has hierarchical structure (trees, graphs, partitions).

Pattern Selection Guide

Time Complexity

Count the number of recursive calls and work done per call.

Example: Factorial

public int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // One call, O(1) work
}
// Total calls: n
// Work per call: O(1)
// Time: O(n)

Example: Fibonacci (Naive)

public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // Two calls
}
// Total calls: O(2^n) — exponential!
// Why? Each call branches into two, creating a binary tree of calls

Space Complexity

Space = maximum depth of recursion stack.

factorial(5) → depth 5
  factorial(4) → depth 4
    factorial(3) → depth 3
      factorial(2) → depth 2
        factorial(1) → depth 1 (base case)

Maximum depth = n → Space = O(n)

Recurrence Relations

For complex recursion, use recurrences:

Mastering the Recursion Tree

Draw the tree to count calls:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2)
│       ├── fib(1) = 1
│       └── fib(0) = 0
└── fib(3)
    ├── fib(2)
    │   ├── fib(1) = 1
    │   └── fib(0) = 0
    └── fib(1) = 1

Total nodes: 15 = O(2^5)

Common Mistakes

1. Missing base case → StackOverflowError
2. Wrong base case → Incorrect results
3. Not making progress → Infinite recursion
4. Redundant computation → Use memoization (see DP)

Converting Recursion to Iteration

Every recursive solution can be converted to iteration using an explicit stack.

Recursive:

public void dfs(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    dfs(root.left);
    dfs(root.right);
}

Iterative (using explicit stack):

public void dfs(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.println(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

When to Use Which

When Recursion is Better

• Trees: Natural recursive structure
• Graphs: DFS is naturally recursive
• Divide and Conquer: Splitting problems
• Backtracking: Exploring all possibilities

When Iteration is Better

• Simple loops: For, while, do-while
• Tail recursion: Can be optimized
• Deep recursion: Risk of stack overflow
• Performance critical: Avoid function call overhead

Java Tail Call Optimization

Java does NOT optimize tail recursion. For deep recursion, convert to iteration:

// Bad: O(n) stack space
public int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Good: O(1) space
public int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}