Introduction to Recursion: Guided Project

Key Components of Recursion

Every recursive solution consists of two essential parts:

• Base Case: The condition that stops the recursion
• Recursive Case: The self-referential call that makes progress toward the base case

Without a proper base case, your recursion will continue indefinitely, causing a stack overflow error.

Implementation Steps

1. 1

   Identify Base Case

   Define the stopping condition

   // Example: Factorial base case
   if (n == 0) return 1;

2. 2

   Define Recursive Case

   Implement the self-referential step

   // Example: Factorial recursive case
   return n * factorial(n - 1);

3. 3

   Ensure Progress

   Verify the problem size decreases with each recursive call

   // Example: Each call reduces n by 1
   factorial(n) → factorial(n-1) → factorial(n-2) → ... → factorial(0)

Example: Factorial Implementation

public int factorial(int n) {
    // Base case: factorial of 0 is 1
    if (n == 0) {
        return 1;
    }
    
    // Recursive case: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Visual Execution Trace for factorial(4):

factorial(4)
└── 4 * factorial(3)
    └── 4 * (3 * factorial(2))
        └── 4 * (3 * (2 * factorial(1)))
            └── 4 * (3 * (2 * (1 * factorial(0))))
                └── 4 * (3 * (2 * (1 * 1)))
                └── 4 * (3 * (2 * 1))
                └── 4 * (3 * 2)
                └── 4 * 6
                └── 24

Example: Fibonacci Implementation

public int fibonacci(int n) {
    // Base cases: F(0) = 0, F(1) = 1
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }
    
    // Recursive case: F(n) = F(n-1) + F(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Visual Execution Trace for fibonacci(4):

fibonacci(4)
├── fibonacci(3) + fibonacci(2)
│   ├── fibonacci(2) + fibonacci(1) + fibonacci(1) + fibonacci(0)
│   │   ├── fibonacci(1) + fibonacci(0) + 1 + 0
│   │   │   ├── 1 + 0 + 1 + 0
│   │   │   └── 2
└── 3

Recursion vs. Iteration

Any recursive solution can be rewritten as an iterative solution, but recursive solutions are often more elegant and easier to understand for certain problems.

Factorial: Recursive vs. Iterative

// Recursive factorial
public int factorialRecursive(int n) {
    if (n == 0) return 1;
    return n * factorialRecursive(n - 1);
}

// Iterative factorial
public int factorialIterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

When to Use Recursion

• When the problem naturally breaks down into similar subproblems
• When working with recursive data structures (trees, graphs)
• When the solution is cleaner and more intuitive with recursion

When to Avoid Recursion

• When the recursion depth could be very large (risk of stack overflow)
• When performance is critical (recursive calls have overhead)
• When the solution can be easily expressed iteratively

Advanced Technique: Memoization

Improve recursive solutions by caching previously computed results to avoid redundant calculations.

Fibonacci with Memoization

public int fibonacciMemoized(int n) {
    Map memo = new HashMap<>();
    return fibMemo(n, memo);
}

private int fibMemo(int n, Map memo) {
    // Check if already computed
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    
    // Base cases
    if (n <= 0) return 0;
    if (n == 1) return 1;
    
    // Compute and store result
    int result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, result);
    
    return result;
}

Exercise 1: Factorial

Implement a recursive function to calculate the factorial of a number.

public int factorial(int n) {
    // Your implementation here
    // Remember: factorial(n) = n * factorial(n-1)
    // Base case: factorial(0) = 1
}

Exercise 2: Fibonacci

Write a recursive function to find the nth Fibonacci number.

public int fibonacci(int n) {
    // Your implementation here
    // Remember: F(n) = F(n-1) + F(n-2)
    // Base cases: F(0) = 0, F(1) = 1
}

Exercise 3: String Reversal

Create a recursive function to reverse a string.

public String reverseString(String str) {
    // Your implementation here
    // Base case: Empty string or single character
    // Recursive case: First character goes to the end
}

Hint: For a string "hello", think of it as the first character 'h' plus the rest "ello". The reversed string would be the reversed "ello" plus 'h'.

Exercise 4: Power Function

Implement a recursive function to calculate x raised to the power of n (x^n).

public double power(double x, int n) {
    // Your implementation here
    // Handle negative exponents too!
    // Consider that x^n = x * x^(n-1)
}

Exercise 5: Sum of Array

Write a recursive function to find the sum of all elements in an array.

public int sumArray(int[] arr) {
    return sumArrayHelper(arr, 0);
}

private int sumArrayHelper(int[] arr, int index) {
    // Your implementation here
    // Base case: index reaches the end of array
    // Recursive case: current element + sum of rest
}

Exercise 6: Advanced - Binary Search

Implement a recursive binary search algorithm to find an element in a sorted array.

public int binarySearch(int[] arr, int target) {
    return binarySearchHelper(arr, target, 0, arr.length - 1);
}

private int binarySearchHelper(int[] arr, int target, int low, int high) {
    // Your implementation here
    // Base case: element not found or found
    // Recursive case: search in left or right half
}

Exercise 7: Challenge - Tower of Hanoi

Implement the classic Tower of Hanoi problem using recursion. Move n disks from source to destination using an auxiliary tower.

public void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    // Your implementation here
    // Base case: Move one disk directly
    // Recursive case: Move n-1 disks to auxiliary, then one to destination, then n-1 from auxiliary to destination
}