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

Pattern	Structure	Example	Complexity
Linear	Chain	Factorial, Sum	O(n) time, O(n) space
Binary	Tree	Fibonacci, Merge Sort	O(2^n) without memo
Tail	Chain with accumulator	Factorial, Reverse	O(n) time, O(1) if optimized
Tree	Tree	Tree traversal, Parse	O(n) time, O(h) space

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:

Recurrence	Solution	Example
T(n) = T(n-1) + O(1)	O(n)	Factorial
T(n) = T(n-1) + O(n)	O(n²)	Selection sort
T(n) = 2T(n/2) + O(n)	O(n log n)	Merge sort
T(n) = 2T(n-1) + O(1)	O(2^n)	Naive Fibonacci
T(n) = T(n/2) + O(1)	O(log n)	Binary search

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

Aspect	Recursion	Iteration
Code clarity	Cleaner for tree/graph	Can be complex
Stack space	O(depth) implicit	O(1) if no stack
Risk	StackOverflowError	Infinite loop
Debugging	Harder	Easier
Performance	Function call overhead	Generally faster

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;
}