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!