Module 2: Recursion

Understanding Recursion

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller instances of the same problem. For recursion to work properly, it must have:

• Base case(s): Condition(s) that stop the recursion
• Recursive case(s): The function calls itself with a simplified version of the problem

Recursive solutions are often elegant and can clearly represent the problem structure, especially for tasks that have a natural recursive definition, like traversing tree structures or calculating factorial values.

Fibonacci Sequence Example

The Fibonacci sequence is a classic example for demonstrating recursion. Each number in the sequence is the sum of the two preceding ones, typically starting with 0 and 1.

The sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Recursive Implementation

public int fibonacciRecursive(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return n;
    }
    
    // Recursive case
    return fibonacciRecursive(n - 2) + fibonacciRecursive(n - 1);
}

Iterative Implementation

public int fibonacciIterative(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    
    int previousPreviousNumber = 0;
    int previousNumber = 1;
    int currentNumber = 0;
    
    for (int i = 2; i <= n; i++) {
        currentNumber = previousPreviousNumber + previousNumber;
        previousPreviousNumber = previousNumber;
        previousNumber = currentNumber;
    }
    
    return currentNumber;
}

Pros and Cons of Recursion

Advantages of Recursion

• Clarity and Elegance: Recursive solutions can be more readable and closely match the problem definition
• Complex Problems: Well-suited for problems with recursive structure (trees, graphs, divide-and-conquer algorithms)
• Code Simplicity: Often requires fewer lines of code than iterative solutions

Disadvantages of Recursion

• Stack Overflow: Risk of stack overflow for deep recursion due to function call overhead
• Memory Usage: Can use more memory than iterative solutions due to call stack requirements
• Performance: May be slower due to function call overhead
• Redundant Calculations: Simple recursive implementations (like Fibonacci) can lead to redundant calculations

When to Use Recursion

• When the problem has a natural recursive structure
• When traversing hierarchical data structures (trees, graphs)
• When implementing divide-and-conquer algorithms
• When code readability is more important than absolute performance

Optimizing Recursive Solutions

• Tail Recursion: Optimize by making the recursive call the last operation
• Memoization: Cache results to avoid redundant calculations
• Consider Iteration: If performance is critical, convert to iteration

Practical Recursion Examples

Factorial Calculation

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

Binary Tree Traversal

public void inOrderTraversal(TreeNode node) {
    // Base case
    if (node == null) {
        return;
    }
    
    // Recursive cases
    inOrderTraversal(node.left);  // Process left subtree
    System.out.println(node.value);  // Process current node
    inOrderTraversal(node.right);  // Process right subtree
}