Java Programming Recursion Tutorial
Advanced Topic

Java Recursion - Complete Tutorial

Master Java Recursion: Learn recursive functions, base cases, recursion vs iteration comparison, factorial, Fibonacci, Tower of Hanoi, recursion tree visualization, and best practices.

Self-Calling

Functions calling themselves

Base Case

Stopping condition

Recursion vs Iteration

Comparison & Trade-offs

Recursion Tree

Visual representation

1. Introduction to Recursion

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. It's based on the principle of solving a complex problem by breaking it down into smaller, similar subproblems.

Key Components of Recursion
  • Base Case: Condition that stops recursion
  • Recursive Case: Function calls itself
  • Progress: Moves toward base case
  • Stack Usage: Uses call stack for state
  • Divide & Conquer: Breaks problem into subproblems
  • Backtracking: Returns to previous states
When to Use Recursion
  • Problems with recursive structure (tree, graph)
  • Mathematical sequences (factorial, Fibonacci)
  • Divide and conquer algorithms
  • Backtracking problems
  • Parsing nested structures (JSON, XML)
  • File system traversal

The Golden Rule of Recursion

Every recursive function must have: 1. A base case (stopping condition) and 2. A recursive case that moves toward the base case. Without a base case, recursion leads to infinite loops and StackOverflowError.

RecursionStructure.java
public class RecursionStructure {
    
    // Basic recursive function structure
    public static void recursiveFunction(parameters) {
        // 1. Base Case (stopping condition)
        if (baseCondition) {
            return baseValue;
        }
        
        // 2. Recursive Case (function calls itself)
        //    with modified parameters moving toward base case
        return recursiveFunction(modifiedParameters);
    }
    
    // Example: Countdown from n to 1
    public static void countdown(int n) {
        // Base case
        if (n <= 0) {
            System.out.println("Blastoff!");
            return;
        }
        
        // Recursive case
        System.out.println(n);
        countdown(n - 1);  // Move toward base case
    }
    
    // Example: Sum of numbers from 1 to n
    public static int sum(int n) {
        // Base case
        if (n <= 0) {
            return 0;
        }
        
        // Recursive case
        return n + sum(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("=== Countdown Example ===");
        countdown(5);
        
        System.out.println("\n=== Sum Example ===");
        System.out.println("Sum of 1 to 5: " + sum(5));
        
        // Visualizing the recursion
        System.out.println("\n=== Recursion Visualization for sum(3) ===");
        System.out.println("sum(3)");
        System.out.println("  = 3 + sum(2)");
        System.out.println("  = 3 + (2 + sum(1))");
        System.out.println("  = 3 + (2 + (1 + sum(0)))");
        System.out.println("  = 3 + (2 + (1 + 0))");
        System.out.println("  = 3 + (2 + 1)");
        System.out.println("  = 3 + 3");
        System.out.println("  = 6");
    }
}
Visualizing Recursion: Call Stack for sum(3)
sum(0) returns 0
sum(1) returns 1 + sum(0) = 1
sum(2) returns 2 + sum(1) = 3
sum(3) returns 3 + sum(2) = 6
main() calls sum(3)

Stack grows downward - Each recursive call creates a new stack frame

2. Recursion vs Iteration: Complete Comparison

Both recursion and iteration (loops) can solve the same problems, but they have different characteristics, advantages, and trade-offs.

FactorialIterative.java
public class FactorialIterative {
    // Iterative approach
    public static int factorialIterative(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Factorial undefined for negative numbers");
        }
        
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
    
    // Recursive approach
    public static int factorialRecursive(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Factorial undefined for negative numbers");
        }
        
        // Base case
        if (n == 0 || n == 1) {
            return 1;
        }
        
        // Recursive case
        return n * factorialRecursive(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("=== Factorial Comparison ===");
        
        int n = 5;
        System.out.println("Factorial of " + n + ":");
        System.out.println("Iterative: " + factorialIterative(n));
        System.out.println("Recursive: " + factorialRecursive(n));
        
        // Performance test
        System.out.println("\n=== Performance Test (n=20) ===");
        long startTime, endTime;
        
        startTime = System.nanoTime();
        int iterResult = factorialIterative(20);
        endTime = System.nanoTime();
        System.out.println("Iterative time: " + (endTime - startTime) + " ns");
        
        startTime = System.nanoTime();
        int recResult = factorialRecursive(20);
        endTime = System.nanoTime();
        System.out.println("Recursive time: " + (endTime - startTime) + " ns");
        
        // Memory test
        System.out.println("\n=== Memory Considerations ===");
        System.out.println("Iterative: Constant O(1) memory");
        System.out.println("Recursive: O(n) stack memory (risk of StackOverflowError)");
        
        // Try large n to see stack overflow
        System.out.println("\n=== Testing with large n (n=10000) ===");
        try {
            factorialIterative(10000);
            System.out.println("Iterative: Works fine");
        } catch (Exception e) {
            System.out.println("Iterative error: " + e.getMessage());
        }
        
        try {
            factorialRecursive(10000);
            System.out.println("Recursive: Works fine");
        } catch (StackOverflowError e) {
            System.out.println("Recursive: StackOverflowError!");
        }
    }
}
FibonacciComparison.java
public class FibonacciComparison {
    
    // Iterative Fibonacci (efficient)
    public static int fibonacciIterative(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        
        int prev1 = 0;
        int prev2 = 1;
        int current = 0;
        
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
        return current;
    }
    
    // Simple recursive Fibonacci (inefficient - O(2^n))
    public static int fibonacciRecursive(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        
        return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }
    
    // Memoized recursive Fibonacci (efficient - O(n))
    public static int fibonacciMemoized(int n) {
        int[] memo = new int[n + 1];
        return fibonacciMemoHelper(n, memo);
    }
    
    private static int fibonacciMemoHelper(int n, int[] memo) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        
        if (memo[n] != 0) {
            return memo[n];
        }
        
        memo[n] = fibonacciMemoHelper(n - 1, memo) + 
                  fibonacciMemoHelper(n - 2, memo);
        return memo[n];
    }
    
    public static void main(String[] args) {
        System.out.println("=== Fibonacci Sequence Comparison ===");
        
        int n = 10;
        System.out.println("Fibonacci(" + n + "):");
        System.out.println("Iterative: " + fibonacciIterative(n));
        System.out.println("Simple Recursive: " + fibonacciRecursive(n));
        System.out.println("Memoized Recursive: " + fibonacciMemoized(n));
        
        System.out.println("\n=== Performance Comparison (n=40) ===");
        long startTime, endTime;
        
        // Iterative
        startTime = System.nanoTime();
        int iterResult = fibonacciIterative(40);
        endTime = System.nanoTime();
        System.out.println("Iterative: " + (endTime - startTime) + " ns");
        
        // Memoized recursive
        startTime = System.nanoTime();
        int memoResult = fibonacciMemoized(40);
        endTime = System.nanoTime();
        System.out.println("Memoized Recursive: " + (endTime - startTime) + " ns");
        
        // Simple recursive (WARNING: Very slow!)
        System.out.println("\n=== Simple Recursive Warning ===");
        System.out.println("Simple recursive Fibonacci has O(2^n) time complexity");
        System.out.println("For n=40, it makes ~1 billion recursive calls!");
        System.out.println("Uncomment below to try (not recommended):");
        // startTime = System.nanoTime();
        // int recResult = fibonacciRecursive(40);
        // endTime = System.nanoTime();
        // System.out.println("Simple Recursive: " + (endTime - startTime) + " ns");
        
        System.out.println("\n=== Time Complexity Analysis ===");
        System.out.println("Iterative: O(n) time, O(1) space");
        System.out.println("Simple Recursive: O(2^n) time, O(n) space");
        System.out.println("Memoized Recursive: O(n) time, O(n) space");
        
        System.out.println("\n=== Recursion Tree for fibonacciRecursive(5) ===");
        System.out.println("                       fib(5)");
        System.out.println("                   /            \\");
        System.out.println("              fib(4)            fib(3)");
        System.out.println("            /        \\          /     \\");
        System.out.println("       fib(3)      fib(2)    fib(2)   fib(1)");
        System.out.println("      /     \\     /    \\    /    \\");
        System.out.println("  fib(2)  fib(1) fib(1)fib(0) fib(1)fib(0)");
        System.out.println("  /    \\");
        System.out.println("fib(1) fib(0)");
        System.out.println("\nTotal calls: 15 (exponential growth!)");
    }
}

Complete Comparison Table: Recursion vs Iteration

Aspect Recursion Iteration Winner Explanation
Definition Function calls itself Loops repeat code block Different paradigms Both achieve repetition differently
Termination Base case condition Loop condition false Similar Both need termination condition
Code Readability High for recursive problems Medium Recursion Recursive code often more elegant for recursive problems
Performance Slower (function call overhead) Faster Iteration Function calls have overhead (stack management)
Memory Usage High (stack frames) Low Iteration Each recursive call uses stack memory
Stack Overflow Risk High None Iteration Deep recursion causes StackOverflowError
Problem Suitability Tree/graph traversal, backtracking Simple repetition, arrays Context dependent Some problems naturally recursive
Debugging Difficulty Harder Easier Iteration Recursion has call stack to track
Code Length Shorter usually Longer sometimes Recursion Recursive solutions can be concise
State Management Implicit (call stack) Explicit (variables) Iteration Iteration gives more control
Time Complexity Can be exponential (Fibonacci) Usually linear/predictable Iteration Recursion can have poor time complexity
Compiler Optimization Tail recursion optimization Loop optimization Iteration Java doesn't optimize tail recursion well
Use Cases Trees, graphs, backtracking, divide & conquer Arrays, simple counting, linear processing Both Choose based on problem nature
When to Choose Recursion
  • Problems with recursive definition (tree, factorial)
  • When code clarity is more important than performance
  • Depth is limited and predictable
  • Backtracking algorithms
  • Divide and conquer algorithms
  • Parsing nested structures
When to Choose Iteration
  • Performance is critical
  • Memory is limited
  • Depth can be very large
  • Simple counting/repetition
  • Array/collection processing
  • When debugging ease is important
General Rule: Use iteration when possible, use recursion when it makes the code significantly clearer or when the problem is naturally recursive. Always consider converting recursive solutions to iterative ones for production code if performance matters.

3. Common Recursive Algorithms

1. Factorial (Mathematical)
public class FactorialExample {
    
    // Recursive factorial
    public static int factorial(int n) {
        // Base case
        if (n < 0) {
            throw new IllegalArgumentException("Negative input");
        }
        if (n == 0 || n == 1) {
            return 1;
        }
        
        // Recursive case
        return n * factorial(n - 1);
    }
    
    // Tail recursive factorial (optimized)
    public static int factorialTail(int n) {
        return factorialTailHelper(n, 1);
    }
    
    private static int factorialTailHelper(int n, int accumulator) {
        // Base case
        if (n < 0) {
            throw new IllegalArgumentException("Negative input");
        }
        if (n == 0) {
            return accumulator;
        }
        
        // Tail recursive call (last operation is recursive call)
        return factorialTailHelper(n - 1, n * accumulator);
    }
    
    public static void main(String[] args) {
        System.out.println("Factorial of 5:");
        System.out.println("Standard recursion: " + factorial(5));
        System.out.println("Tail recursion: " + factorialTail(5));
        
        System.out.println("\nRecursive call trace for factorial(4):");
        System.out.println("factorial(4)");
        System.out.println("  4 * factorial(3)");
        System.out.println("  4 * (3 * factorial(2))");
        System.out.println("  4 * (3 * (2 * factorial(1)))");
        System.out.println("  4 * (3 * (2 * 1))");
        System.out.println("  4 * (3 * 2)");
        System.out.println("  4 * 6");
        System.out.println("  24");
    }
}
2. Fibonacci Sequence
public class FibonacciExamples {
    
    // 1. Simple recursive (inefficient O(2^n))
    public static int fibonacciSimple(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        return fibonacciSimple(n - 1) + fibonacciSimple(n - 2);
    }
    
    // 2. Memoized recursive (efficient O(n))
    public static int fibonacciMemo(int n) {
        int[] memo = new int[n + 1];
        return fibonacciMemoHelper(n, memo);
    }
    
    private static int fibonacciMemoHelper(int n, int[] memo) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        
        if (memo[n] != 0) {
            return memo[n];
        }
        
        memo[n] = fibonacciMemoHelper(n - 1, memo) + 
                  fibonacciMemoHelper(n - 2, memo);
        return memo[n];
    }
    
    // 3. Tail recursive Fibonacci
    public static int fibonacciTail(int n) {
        return fibonacciTailHelper(n, 0, 1);
    }
    
    private static int fibonacciTailHelper(int n, int a, int b) {
        if (n == 0) return a;
        if (n == 1) return b;
        return fibonacciTailHelper(n - 1, b, a + b);
    }
    
    public static void main(String[] args) {
        System.out.println("Fibonacci Sequence (first 10 numbers):");
        for (int i = 0; i <= 10; i++) {
            System.out.println("F(" + i + ") = " + fibonacciMemo(i));
        }
        
        System.out.println("\nPerformance Comparison (n=40):");
        long start, end;
        
        // Memoized
        start = System.nanoTime();
        int memoResult = fibonacciMemo(40);
        end = System.nanoTime();
        System.out.println("Memoized: " + (end - start) + " ns");
        
        // Tail recursive
        start = System.nanoTime();
        int tailResult = fibonacciTail(40);
        end = System.nanoTime();
        System.out.println("Tail Recursive: " + (end - start) + " ns");
        
        // Simple (WARNING: Very slow!)
        System.out.println("\nSimple recursive for n=40 would take:");
        System.out.println("Time: ~1 second (O(2^40) operations)");
        System.out.println("Calls: ~1.1 billion recursive calls!");
    }
}
3. Tower of Hanoi (Classic Recursive Problem)
public class TowerOfHanoi {
    
    public static void solveHanoi(int n, char source, char auxiliary, char destination) {
        // Base case: Only one disk to move
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }
        
        // Step 1: Move n-1 disks from source to auxiliary
        solveHanoi(n - 1, source, destination, auxiliary);
        
        // Step 2: Move nth disk from source to destination
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        
        // Step 3: Move n-1 disks from auxiliary to destination
        solveHanoi(n - 1, auxiliary, source, destination);
    }
    
    public static void main(String[] args) {
        System.out.println("=== Tower of Hanoi Solution ===");
        int disks = 3;
        System.out.println("Solution for " + disks + " disks:");
        solveHanoi(disks, 'A', 'B', 'C');
        
        System.out.println("\n=== Algorithm Analysis ===");
        System.out.println("Number of moves: " + ((int)Math.pow(2, disks) - 1));
        System.out.println("Time Complexity: O(2^n)");
        System.out.println("Space Complexity: O(n) (recursion depth)");
        
        System.out.println("\n=== Recursive Breakdown for 3 Disks ===");
        System.out.println("solveHanoi(3, A, B, C)");
        System.out.println("  solveHanoi(2, A, C, B)");
        System.out.println("    solveHanoi(1, A, B, C) → Move disk 1: A to C");
        System.out.println("    Move disk 2: A to B");
        System.out.println("    solveHanoi(1, C, A, B) → Move disk 1: C to B");
        System.out.println("  Move disk 3: A to C");
        System.out.println("  solveHanoi(2, B, A, C)");
        System.out.println("    solveHanoi(1, B, C, A) → Move disk 1: B to A");
        System.out.println("    Move disk 2: B to C");
        System.out.println("    solveHanoi(1, A, B, C) → Move disk 1: A to C");
    }
}
4. Binary Search (Divide and Conquer)
public class BinarySearchRecursive {
    
    // Recursive binary search
    public static int binarySearch(int[] arr, int target) {
        return binarySearchHelper(arr, target, 0, arr.length - 1);
    }
    
    private static int binarySearchHelper(int[] arr, int target, int left, int right) {
        // Base case: element not found
        if (left > right) {
            return -1;
        }
        
        int mid = left + (right - left) / 2;
        
        // Base case: element found
        if (arr[mid] == target) {
            return mid;
        }
        
        // Recursive cases
        if (arr[mid] > target) {
            // Search left half
            return binarySearchHelper(arr, target, left, mid - 1);
        } else {
            // Search right half
            return binarySearchHelper(arr, target, mid + 1, right);
        }
    }
    
    // Iterative version for comparison
    public static int binarySearchIterative(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
        int[] sortedArray = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};
        int target = 23;
        
        System.out.println("=== Binary Search ===");
        System.out.println("Array: " + java.util.Arrays.toString(sortedArray));
        System.out.println("Target: " + target);
        
        int recursiveResult = binarySearch(sortedArray, target);
        int iterativeResult = binarySearchIterative(sortedArray, target);
        
        System.out.println("Recursive result: Index " + recursiveResult);
        System.out.println("Iterative result: Index " + iterativeResult);
        
        System.out.println("\n=== Recursive Call Trace (searching for 23) ===");
        System.out.println("Initial: left=0, right=10, mid=5 (arr[5]=23) → Found!");
        System.out.println("Only one recursive call needed in best case.");
        
        System.out.println("\n=== Time Complexity Analysis ===");
        System.out.println("Best case: O(1) - element at middle");
        System.out.println("Worst case: O(log n) - divide array in half each time");
        System.out.println("Space complexity:");
        System.out.println("  Recursive: O(log n) - recursion depth");
        System.out.println("  Iterative: O(1) - constant space");
        
        System.out.println("\n=== Divide and Conquer Pattern ===");
        System.out.println("1. Divide: Split problem into subproblems");
        System.out.println("2. Conquer: Solve subproblems recursively");
        System.out.println("3. Combine: Combine subproblem solutions");
    }
}

4. Recursion Tree & Call Stack Visualization

Recursion Tree for fibonacciRecursive(4)
fib(4)
fib(3)
fib(2)
fib(1)
fib(0)
fib(1)
fib(2)
fib(1)
fib(0)

Total calls: 9 (Exponential growth: ~O(2^n))

Call Stack Explanation
  • Each recursive call creates a stack frame
  • Stack frame contains: parameters, local variables, return address
  • Stack grows downward in memory
  • Base case returns, popping frames from stack
  • Stack overflow occurs when stack exceeds memory limit
  • Default stack size in Java: 1MB (can be increased with -Xss flag)
Call Stack for factorial(3)
Stack Frame 1: factorial(1)
n=1, return=1
Stack Frame 2: factorial(2)
n=2, waiting for factorial(1)
Will return: 2 * 1 = 2
Stack Frame 3: factorial(3)
n=3, waiting for factorial(2)
Will return: 3 * 2 = 6
Stack Frame 0: main()
calling factorial(3)
StackVisualization.java
public class StackVisualization {
    
    static int depth = 0;
    
    public static void recursiveMethod(int n) {
        depth++;
        System.out.println(indent(depth) + "Entering recursiveMethod(" + n + ")");
        System.out.println(indent(depth) + "Stack depth: " + depth);
        
        // Base case
        if (n <= 0) {
            System.out.println(indent(depth) + "Base case reached!");
            depth--;
            return;
        }
        
        // Recursive call
        recursiveMethod(n - 1);
        
        System.out.println(indent(depth) + "Exiting recursiveMethod(" + n + ")");
        depth--;
    }
    
    private static String indent(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("  ");
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        System.out.println("=== Visualizing Recursion Stack ===");
        System.out.println("Calling recursiveMethod(3):\n");
        recursiveMethod(3);
        
        System.out.println("\n=== Stack Overflow Demonstration ===");
        System.out.println("Default stack size: ~1MB (stores about 10000-20000 calls)");
        System.out.println("Uncomment below to cause StackOverflowError:");
        // recursiveMethod(10000);  // This will cause StackOverflowError
        
        System.out.println("\n=== Preventing Stack Overflow ===");
        System.out.println("1. Ensure base case is reachable");
        System.out.println("2. Convert to iteration for deep recursion");
        System.out.println("3. Increase stack size: java -Xss4m ProgramName");
        System.out.println("4. Use tail recursion optimization (if supported)");
    }
}

5. Tail Recursion & Optimization

Tail recursion is a special form of recursion where the recursive call is the last operation in the function. Some compilers can optimize tail recursion to avoid stack growth.

Type Definition Example Optimizable? Java Support
Regular Recursion Recursive call not last operation return n * fact(n-1); No Standard recursion
Tail Recursion Recursive call is last operation return factTail(n-1, n*acc); Yes (in theory) Not optimized by Java
TailRecursionExample.java
public class TailRecursionExample {
    
    // Regular recursion (NOT tail recursive)
    public static int factorialRegular(int n) {
        if (n <= 1) return 1;
        // Multiplication happens AFTER recursive call returns
        return n * factorialRegular(n - 1);  // NOT tail recursive
    }
    
    // Tail recursive version
    public static int factorialTail(int n) {
        return factorialTailHelper(n, 1);
    }
    
    private static int factorialTailHelper(int n, int accumulator) {
        if (n <= 1) return accumulator;
        // Recursive call is LAST operation
        return factorialTailHelper(n - 1, n * accumulator);  // Tail recursive
    }
    
    // Regular Fibonacci (NOT tail recursive)
    public static int fibonacciRegular(int n) {
        if (n <= 1) return n;
        // Addition happens AFTER both recursive calls
        return fibonacciRegular(n - 1) + fibonacciRegular(n - 2);
    }
    
    // Tail recursive Fibonacci
    public static int fibonacciTail(int n) {
        return fibonacciTailHelper(n, 0, 1);
    }
    
    private static int fibonacciTailHelper(int n, int a, int b) {
        if (n == 0) return a;
        if (n == 1) return b;
        // Recursive call is LAST operation
        return fibonacciTailHelper(n - 1, b, a + b);
    }
    
    public static void main(String[] args) {
        System.out.println("=== Tail Recursion Examples ===");
        
        System.out.println("Factorial of 5:");
        System.out.println("Regular: " + factorialRegular(5));
        System.out.println("Tail: " + factorialTail(5));
        
        System.out.println("\nFibonacci(10):");
        System.out.println("Regular: " + fibonacciRegular(10));
        System.out.println("Tail: " + fibonacciTail(10));
        
        System.out.println("\n=== Important Note about Java ===");
        System.out.println("Java does NOT optimize tail recursion!");
        System.out.println("Unlike functional languages (Scala, Haskell)");
        System.out.println("Java still creates stack frames for tail calls");
        System.out.println("However, writing tail recursive code is still good practice:");
        System.out.println("1. Easier to convert to iteration");
        System.out.println("2. Clearer intent for optimization");
        System.out.println("3. Works in languages that DO optimize it");
        
        System.out.println("\n=== Converting Tail Recursion to Iteration ===");
        System.out.println("Tail recursion can be easily converted to iteration:");
        System.out.println("while (condition) {");
        System.out.println("  accumulator = update(accumulator, n);");
        System.out.println("  n = n - 1;");
        System.out.println("}");
    }
}
RecursionToIteration.java
public class RecursionToIteration {
    
    // Original recursive factorial
    public static int factorialRecursive(int n) {
        if (n <= 1) return 1;
        return n * factorialRecursive(n - 1);
    }
    
    // Converted to iteration
    public static int factorialIterative(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
    
    // Tail recursive factorial
    public static int factorialTailRecursive(int n) {
        return factorialTailHelper(n, 1);
    }
    
    private static int factorialTailHelper(int n, int acc) {
        if (n <= 1) return acc;
        return factorialTailHelper(n - 1, n * acc);
    }
    
    // Tail recursion converted to iteration (easy!)
    public static int factorialTailToIterative(int n) {
        int acc = 1;
        while (n > 1) {
            acc = n * acc;  // Same as recursive parameter update
            n = n - 1;      // Same as recursive parameter update
        }
        return acc;
    }
    
    // Complex recursion: Tree traversal
    static class TreeNode {
        int value;
        TreeNode left, right;
        TreeNode(int value) { this.value = value; }
    }
    
    // Recursive tree traversal
    public static void traverseTreeRecursive(TreeNode node) {
        if (node == null) return;
        
        // Pre-order traversal
        System.out.print(node.value + " ");
        traverseTreeRecursive(node.left);
        traverseTreeRecursive(node.right);
    }
    
    // Iterative tree traversal (using stack)
    public static void traverseTreeIterative(TreeNode root) {
        if (root == null) return;
        
        java.util.Stack stack = new java.util.Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.value + " ");
            
            // Push right first so left is processed first (stack is LIFO)
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }
    
    public static void main(String[] args) {
        System.out.println("=== Converting Recursion to Iteration ===");
        
        System.out.println("Factorial(5):");
        System.out.println("Recursive: " + factorialRecursive(5));
        System.out.println("Iterative: " + factorialIterative(5));
        System.out.println("Tail to Iterative: " + factorialTailToIterative(5));
        
        System.out.println("\n=== Tree Traversal ===");
        TreeNode tree = new TreeNode(1);
        tree.left = new TreeNode(2);
        tree.right = new TreeNode(3);
        tree.left.left = new TreeNode(4);
        tree.left.right = new TreeNode(5);
        
        System.out.print("Recursive traversal: ");
        traverseTreeRecursive(tree);
        
        System.out.print("\nIterative traversal: ");
        traverseTreeIterative(tree);
        
        System.out.println("\n\n=== When to Convert ===");
        System.out.println("1. Performance critical code");
        System.out.println("2. Deep recursion risk");
        System.out.println("3. Memory constraints");
        System.out.println("4. Production systems");
        
        System.out.println("\n=== General Conversion Rules ===");
        System.out.println("Tail recursion → Simple loop");
        System.out.println("Tree recursion → Stack data structure");
        System.out.println("Multiple recursion → Multiple stacks/queues");
    }
}

6. Best Practices & Common Mistakes

Common Recursion Mistakes:
  1. Missing base case: Infinite recursion → StackOverflowError
  2. Base case never reached: Incorrect progress toward base case
  3. Exponential time complexity: Like naive Fibonacci O(2^n)
  4. Forgetting return statement: In recursive case or base case
  5. Modifying parameters incorrectly: Not moving toward base case
  6. Using recursion for simple loops: When iteration is better
Recursion Best Practices
  • Always define base case first
  • Ensure progress toward base case
  • Use memoization for overlapping subproblems
  • Consider tail recursion when possible
  • Limit recursion depth (use iteration for deep recursion)
  • Document recursion assumptions and limits
  • Test with edge cases (0, 1, negative, large numbers)
Performance Guidelines
  • Use iteration for performance-critical code
  • Memoize recursive functions with overlapping subproblems
  • Avoid recursion for O(2^n) time complexity
  • Set recursion depth limits
  • Consider converting recursion to iteration for production
  • Profile recursive code with realistic inputs

When to Use Recursion vs Iteration

Use Recursion when: Problem is naturally recursive, code clarity is priority, depth is limited
Use Iteration when: Performance matters, memory is limited, depth can be large, debugging ease needed

RecursionChecklist.java
public class RecursionChecklist {
    
    // Checklist for writing recursive functions
    public static void recursionChecklist() {
        System.out.println("=== Recursion Implementation Checklist ===\n");
        
        System.out.println("1. ✅ Identify the Base Case(s)");
        System.out.println("   - When does recursion stop?");
        System.out.println("   - Handle edge cases (0, 1, empty, null)");
        System.out.println("   - Example: if (n <= 1) return 1;");
        
        System.out.println("\n2. ✅ Define Recursive Case");
        System.out.println("   - How does problem break into subproblems?");
        System.out.println("   - Example: return n * factorial(n-1);");
        
        System.out.println("\n3. ✅ Ensure Progress Toward Base Case");
        System.out.println("   - Parameters must change in recursive call");
        System.out.println("   - Example: n-1 moves toward n <= 1");
        
        System.out.println("\n4. ✅ Check Time Complexity");
        System.out.println("   - Avoid exponential time (O(2^n))");
        System.out.println("   - Consider memoization for overlapping subproblems");
        
        System.out.println("\n5. ✅ Check Space Complexity");
        System.out.println("   - Each call uses stack memory");
        System.out.println("   - Default stack: ~10000-20000 calls max");
        
        System.out.println("\n6. ✅ Test with Edge Cases");
        System.out.println("   - Small inputs (0, 1)");
        System.out.println("   - Large inputs (check for stack overflow)");
        System.out.println("   - Invalid inputs (negative numbers)");
        
        System.out.println("\n7. ✅ Consider Alternatives");
        System.out.println("   - Would iteration be better?");
        System.out.println("   - Can tail recursion help?");
        System.out.println("   - Is memoization needed?");
    }
    
    // Example: Well-designed recursive function
    public static int power(int base, int exponent) {
        // 1. Base cases
        if (exponent < 0) {
            throw new IllegalArgumentException("Negative exponent not supported");
        }
        if (exponent == 0) {
            return 1;  // Base case 1
        }
        if (exponent == 1) {
            return base;  // Base case 2
        }
        
        // 2. Recursive case with optimization
        // Use divide and conquer: x^n = x^(n/2) * x^(n/2)
        int halfPower = power(base, exponent / 2);
        
        if (exponent % 2 == 0) {
            return halfPower * halfPower;  // Even exponent
        } else {
            return base * halfPower * halfPower;  // Odd exponent
        }
        // Time complexity: O(log n) instead of O(n)
    }
    
    public static void main(String[] args) {
        recursionChecklist();
        
        System.out.println("\n=== Example: Optimized Power Function ===");
        System.out.println("2^10 = " + power(2, 10));
        System.out.println("3^5 = " + power(3, 5));
        System.out.println("Time complexity: O(log n)");
        System.out.println("Space complexity: O(log n) - recursion depth");
        
        System.out.println("\n=== Final Recommendation ===");
        System.out.println("For interview questions: Show both recursive and iterative solutions");
        System.out.println("For production code: Prefer iteration unless recursion significantly");
        System.out.println("improves code clarity and depth is guaranteed to be small.");
    }
}
Next: Java OOP Basics