Recursion - Comprehensive Study Guide

🎯 What is Recursion?

Definition

Recursion occurs when a method calls itself. It's a powerful programming technique where a problem is solved by breaking it down into smaller instances of the same problem.

Content of a Recursive Method

1. Base Case(s) 🛑

Values of input variables for which we perform no recursive calls
There should be at least one base case
Every possible chain of recursive calls must eventually reach a base case
When we stop the loop - the method must stop calling itself

2. Recursive Calls 🔄

Calls to the current method
Each recursive call should be defined so that it makes progress towards a base case
The method must update parameters to eventually reach the base case

⚠️ Critical Requirements

Must have a base case (or the recursion never stops!)
Must make progress toward the base case
Must call itself (that's what makes it recursive)

🔢 The Recursion Pattern: Factorial

Classic Example: Factorial Function

Mathematical Definition: n! = 1 · 2 · 3 · ... · (n-1) · n

Recursive Definition:

f(n) = { 1 if n = 0
n · f(n-1) else

Java Implementation

public static int factorial(int n) throws IllegalArgumentException {
    if (n < 0)
        throw new IllegalArgumentException();  // argument must be nonnegative
    else if (n == 0)
        return 1;                              // base case
    else
        return n * factorial(n-1);          // recursive case (must update n)
}
                

Execution Trace: factorial(4)

factorial(4)
    ↓ call                    → return 4*6 = 24 (final answer)
factorial(3)
    ↓ call                    → return 3*2 = 6
factorial(2)
    ↓ call                    → return 2*1 = 2
factorial(1)
    ↓ call                    → return 1*1 = 1
factorial(0)
    → return 1 (base case)

How it Works:

Forward calls: Methods keep calling themselves with decreasing n
Base case reached: When n = 0, return 1
Backward returns: Each call returns its result to the caller
Final result: 4! = 24

Runtime: O(n) - Makes n+1 calls

📝 Common Recursion Examples

1. Binary Search

Problem: Search for an integer in an ordered array

Strategy: Check middle element, then recur on appropriate half

public static boolean binarySearch(int[] data, int target, int low, int high) {
    if (low > high)
        return false;                      // interval empty; no match
    else {
        int mid = (low + high) / 2;
        if (target == data[mid])
            return true;                   // found a match
        else if (target < data[mid])
            return binarySearch(data, target, low, mid - 1);    // recur left
        else
            return binarySearch(data, target, mid + 1, high);   // recur right
    }
}
                

Runtime: O(log n)

Each recursive call divides the search region in half, so there can be at most log n levels.

2. Linear Sum (Array Summation)

Problem: Add all numbers in an integer array

Strategy: Sum first n-1 elements, then add the nth element

public static int linearSum(int[] A, int n) {
    if (n == 0)
        return 0;                          // base case
    else
        return linearSum(A, n - 1) + A[n - 1];  // recursive case
}
                

Trace: linearSum(data, 5) for data = [4, 3, 6, 2, 8]

linearSum(data, 5) → return 15 + data[4] = 15 + 8 = 23
    ↓
linearSum(data, 4) → return 13 + data[3] = 13 + 2 = 15
    ↓
linearSum(data, 3) → return 7 + data[2] = 7 + 6 = 13
    ↓
linearSum(data, 2) → return 4 + data[1] = 4 + 3 = 7
    ↓
linearSum(data, 1) → return 0 + data[0] = 0 + 4 = 4
    ↓
linearSum(data, 0) → return 0 (base case)

3. Reversing an Array

public static void reverseArray(int[] data, int low, int high) {
    if (low < high) {                     // if at least two elements in subarray
        int temp = data[low];             // swap data[low] and data[high]
        data[low] = data[high];
        data[high] = temp;
        reverseArray(data, low + 1, high - 1);   // recur on the rest
    }
}
                

Runtime: O(n)

Each recursive call swaps two elements and moves indices closer to the middle.

4. Computing Powers

❌ Slow Approach: O(n)

int power(int x, int n) {
    if (n == 0)
        return 1;
    else
        return x * power(x, n-1);
}
                        

Makes n recursive calls

✅ Fast Approach: O(log n)

int power(int x, int n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        int y = power(x, (n-1)/2);
        return x * y * y;
    } else {
        int y = power(x, n/2);
        return y * y;
    }
}
                        

Uses repeated squaring!

How Recursive Squaring Works:

2⁴ = (2²)² = 4² = 16
2⁵ = 2 · (2²)² = 2 · 16 = 32
2⁸ = (2⁴)² = 16² = 256

Key Insight: Halve the exponent each time → logarithmic complexity!

5. Fibonacci Numbers

Definition:

F₀ = 0
F₁ = 1
Fᵢ = Fᵢ₋₁ + Fᵢ₋₂ for i > 1

❌ Binary Recursion (SLOW)

int binaryFib(int k) {
    if (k <= 1)
        return k;
    else
        return binaryFib(k-1) 
             + binaryFib(k-2);
}
                        

Runtime: O(2ⁿ) - EXPONENTIAL!

Makes redundant calculations

✅ Linear Recursion (FAST)

Pair linearFib(int k) {
    if (k == 1)
        return (k, 0);
    else {
        (i, j) = linearFib(k-1);
        return (i+j, i);
    }
}
                        

Runtime: O(n) - LINEAR!

Returns pair (Fₖ, Fₖ₋₁)

6. English Ruler (Drawing Ticks)

Problem: Draw tick marks on a ruler with varying lengths

Pattern: For a tick of length L, draw smaller ticks (L-1) on both sides

public static void drawInterval(int centralLength) {
    if (centralLength > 0) {
        drawInterval(centralLength - 1);     // draw top interval
        drawLine(centralLength);              // draw center tick line
        drawInterval(centralLength - 1);     // draw bottom interval
    }
}
                

Note: This is an example of binary recursion (two recursive calls per invocation)

🎭 Types of Recursion

1. Linear Recursion

Definition: Makes at most one recursive call per invocation

Characteristics:

Test for base cases first
Perform a single recursive call (may have conditionals to decide which call)
Each recursive call makes progress toward base case

Examples:

Factorial
Linear sum
Binary search
Array reversal

2. Tail Recursion

Definition: A special case of linear recursion where the recursive call is the last step of the method

⚡ Special Property:

Tail recursive methods can be easily converted to iterative (loop-based) implementations, which are often more efficient.

Tail Recursive Version

void reverseArray(int[] A, 
                  int i, int j) {
    if (i < j) {
        swap(A[i], A[j]);
        reverseArray(A, i+1, j-1);
    }
}
                        

Iterative Equivalent

void reverseArray(int[] A, 
                  int i, int j) {
    while (i < j) {
        swap(A[i], A[j]);
        i = i + 1;
        j = j - 1;
    }
}
                        

3. Binary Recursion

Definition: Makes two recursive calls for each non-base case

Examples:

Binary sum (divide array in half, sum each half)
English ruler drawing
Binary Fibonacci (inefficient)

int binarySum(int[] A, int i, int n) {
    if (n == 1)
        return A[i];
    return binarySum(A, i, n/2) + binarySum(A, i + n/2, n/2);
}
                

4. Multiple Recursion

Definition: Makes potentially many recursive calls (more than two)

Example: Puzzle Solving

Generate all possible combinations/permutations

void puzzleSolve(int k, List S, Set U) {
    for all e in U do
        Remove e from U
        Add e to the end of S
        if k == 1 then
            Test whether S solves the puzzle
        else
            puzzleSolve(k-1, S, U)
        Add e back to U
        Remove e from the end of S
}
                

Recursion Tree for PuzzleSolve(3, [], {a,b,c})

                        []
          ┌─────────┼─────────┐
         [a]       [b]       [c]
       ┌──┴──┐   ┌──┴──┐   ┌──┴──┐
      [ab][ac] [ba][bc] [ca][cb]
       ↓   ↓    ↓   ↓    ↓   ↓
      abc acb  bac bca  cab cba

⏱️ Complexity Analysis

Time Complexity Comparison

Algorithm	Type	Time Complexity	Explanation
Factorial	Linear	O(n)	Makes n recursive calls
Binary Search	Linear	O(log n)	Halves search space each time
Linear Sum	Linear	O(n)	Processes each element once
Array Reversal	Tail	O(n)	Swaps n/2 pairs
Power (naive)	Linear	O(n)	Multiplies n times
Power (squaring)	Linear	O(log n)	Halves exponent each time
Binary Sum	Binary	O(n)	Processes each element in tree
Binary Fibonacci	Binary	O(2ⁿ)	Exponential - very inefficient!
Linear Fibonacci	Linear	O(n)	Makes n-1 calls

Understanding Call Counts

Binary Fibonacci Analysis

Let nₖ = number of recursive calls for BinaryFib(k):

n₀ = 1
n₁ = 1
n₂ = n₁ + n₀ + 1 = 3
n₃ = n₂ + n₁ + 1 = 5
n₄ = n₃ + n₂ + 1 = 9
n₈ = 67

Notice: nₖ at least doubles every other time → nₖ > 2^(k/2)

This is exponential growth - very bad!

Key Insights for Efficiency

Avoid redundant calculations: Binary Fibonacci recalculates same values multiple times
Use clever math: Recursive squaring reduces O(n) to O(log n)
Consider iterative alternatives: Tail recursive methods can often be converted to loops
Store intermediate results: Dynamic programming (memoization) can help

📋 Summary & Study Tips

Key Concepts to Remember

1. Three Requirements for Recursion:

✅ Must have a base case
✅ Must make progress toward base case
✅ Must call itself

2. Types of Recursion:

Linear: One recursive call per invocation
Tail: Recursive call is the last operation (easily converted to loops)
Binary: Two recursive calls per invocation
Multiple: Many recursive calls (used for enumeration/combinations)

3. When to Use Recursion:

✅ Problem can be broken into smaller subproblems of the same type
✅ Natural recursive structure (trees, divide-and-conquer)
✅ Code is clearer/simpler than iterative version
❌ Avoid when efficiency is critical and recursion adds overhead
❌ Avoid when iterative solution is equally clear

Common Pitfalls to Avoid

🚫 Missing base case: Results in infinite recursion (stack overflow)
🚫 Not making progress: Recursive call doesn't move toward base case
🚫 Redundant calculations: Like binary Fibonacci - use dynamic programming instead
🚫 Too many recursive calls: Can cause stack overflow for large inputs
🚫 Modifying wrong parameters: Ensure you update parameters correctly

Study Strategies

To Master Recursion:

Draw recursion trees: Visualize how calls are made and returned
Trace execution: Follow the values step by step
Count recursive calls: Understand time complexity
Identify base cases: Always start here when analyzing recursive code
Practice converting: Try converting recursive to iterative and vice versa
Solve problems: Write your own recursive solutions from scratch

Practice Problems

Try implementing these recursively:

Calculate the nth Fibonacci number (both ways)
Find the maximum element in an array
Check if a string is a palindrome
Calculate the Greatest Common Divisor (GCD)
Generate all permutations of a string
Implement merge sort
Traverse a binary tree
Solve the Tower of Hanoi puzzle

Quick Reference Card

Concept	Key Points
Base Case	Simplest case that can be solved directly without recursion
Recursive Case	Breaks problem into smaller subproblems and calls itself
Progress	Each recursive call must move closer to the base case
Stack Space	Each recursive call uses stack memory; deep recursion can overflow
Tail Recursion	Last operation is the recursive call; can be optimized to iteration
Time Complexity	Count how many times the function is called and work per call

🎓 Final Tip

"To understand recursion, you must first understand recursion." 😊

Practice is key! Start with simple examples and gradually work your way up to more complex problems. Draw diagrams, trace executions, and don't be afraid to experiment!

🎓 Practice Questions

Question 1: Three Requirements for Correct Recursion

Q: State the three necessary conditions for a correct recursive method and explain what goes wrong if each one is missing.

A: 1. Base case: Without it, the method calls itself forever → stack overflow (StackOverflowError in Java).
2. Progress toward base case: Without it, the recursion may never terminate even if a base case exists (e.g., factorial(n) that calls factorial(n) instead of factorial(n-1)).
3. Self-call (recursive case): Without it, the method is simply iterative/direct and does not use recursion. The combination of all three ensures the recursion terminates and produces a correct result.

Question 2: Trace factorial(4)

Q: Trace the execution of factorial(4) showing the call stack at maximum depth and the return values unwinding back.

A: Call stack builds up (forward phase): factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0). At maximum depth: 5 frames on the call stack. Return values unwind (backward phase): factorial(0) returns 1 → factorial(1) returns 1×1=1 → factorial(2) returns 2×1=2 → factorial(3) returns 3×2=6 → factorial(4) returns 4×6=24. Total: n+1 = 5 method calls, O(n) time, O(n) call stack space.

Question 3: Binary Fibonacci Is Exponential — Why?

Q: Explain why naive binary Fibonacci (two recursive calls per level) has O(2^n) complexity. Show the redundant computation for fib(5).

A: In naive binary recursion, binaryFib(5) calls binaryFib(4) and binaryFib(3). binaryFib(4) calls binaryFib(3) and binaryFib(2). Notice binaryFib(3) is computed twice. Similarly, binaryFib(2) is computed 3 times, binaryFib(1) is computed 5 times. In general, the number of calls for fib(k) grows faster than 2^(k/2), giving exponential complexity. The fix is linear recursion that returns a pair (Fₖ, Fₖ₋₁), computing each Fibonacci number exactly once — reducing time to O(n).

Question 4: Tail Recursion and Conversion to Iteration

Q: Define tail recursion. Show that the array reversal recursion is tail recursive and convert it to an iterative version.

A: A method is tail recursive if the recursive call is the very last operation before returning — no work is done with the return value. For array reversal: if (low < high) { swap(A[low], A[high]); reverseArray(A, low+1, high-1); } — the call is the last statement, so this is tail recursive.
Iterative equivalent: while (low < high) { swap(A[low], A[high]); low++; high--; }
The while loop replaces the recursive call, and the parameters become mutable loop variables. The iterative version uses O(1) stack space vs. O(n/2) for the recursive version.

Question 5: Recursive Squaring vs. Linear Power

Q: Compute 2^10 using the recursive squaring approach, showing each recursive call and demonstrating that only O(log n) multiplications are needed.

A: power(2, 10): n=10 (even) → y = power(2, 5), return y*y.
power(2, 5): n=5 (odd) → y = power(2, 2), return 2*y*y.
power(2, 2): n=2 (even) → y = power(2, 1), return y*y.
power(2, 1): n=1 (odd) → y = power(2, 0), return 2*y*y.
power(2, 0): base case → return 1.
Unwinding: power(2,1) = 2*1*1 = 2. power(2,2) = 2*2 = 4. power(2,5) = 2*4*4 = 32. power(2,10) = 32*32 = 1024. Only 4 recursive calls (log₂ 10 ≈ 3.3) vs. 10 for the naive approach.

Question 6: Types of Recursion Classification

Q: Classify each of the following as linear, tail, binary, or multiple recursion, and state the time complexity: (a) factorial, (b) binary search, (c) binary sum, (d) puzzle solver generating permutations.

A: (a) Factorial: Linear recursion (one call per invocation, result used after return so NOT tail recursive). O(n).
(b) Binary search: Linear recursion (one call per invocation, last operation — actually tail recursive). O(log n).
(c) Binary sum: Binary recursion (two calls per invocation). O(n) — despite binary recursion, all n elements are processed once total.
(d) Puzzle solver: Multiple recursion (up to |U| calls per invocation, where U is the remaining unused set). O(n!) for generating all n! permutations.

Question 7: Call Stack and Stack Overflow

Q: What is the call stack, why does deep recursion risk a StackOverflowError, and which recursion type from this chapter is most dangerous for large inputs?

A: The call stack is a region of memory where each method invocation creates a stack frame storing local variables, parameters, and the return address. Frames are pushed on entry and popped on return. Java's call stack has a fixed maximum depth (typically ~5,000–10,000 frames, depending on frame size and JVM settings). If recursion goes deeper than this limit, a StackOverflowError is thrown.
The most dangerous type is linear/tail recursion with large n — e.g., factorial(100000) creates 100,001 frames. Binary recursion on large inputs also creates deep stacks (depth = log₂ N for balanced recursion). Tail recursion can be optimized by compilers to reuse the same frame (tail call optimization), but Java does NOT perform this optimization.

Question 8: Design a Recursive Solution

Q: Write a recursive method to check if a string is a palindrome (reads the same forwards and backwards). Identify the base case(s), recursive case, and its time complexity.

A: Base cases: (1) Empty string → true (2) Single character → true.
Recursive case: Check if first and last characters match AND the substring between them is a palindrome.
boolean isPalindrome(String s, int lo, int hi) {
  if (lo >= hi) return true; // base cases
  if (s.charAt(lo) != s.charAt(hi)) return false;
  return isPalindrome(s, lo+1, hi-1); // tail recursive
}
Time complexity: O(n/2) = O(n) — makes n/2 recursive calls. Space: O(n) call stack (or O(1) if compiler performs tail call optimization). This is a tail-recursive method and can be directly converted to a while loop.