10.1 Recursion

Recursion is like a programmer's magic trick - a method that calls itself to solve problems. While it might seem confusing at first, recursion offers an elegant approach to solving complex problems by breaking them down into smaller, similar subproblems. This study guide will help you understand what recursion is, how it works, and when to use it.

What is Recursion?

Recursion occurs when a method calls itself during its execution. Instead of using loops to repeat actions, recursion achieves repetition through repeated method calls.

public void recursiveMethod() {
    // Some code here
    recursiveMethod(); // Method calling itself!
    // More code here
}

Anatomy of a Recursive Method

Every properly designed recursive method has two essential components:

1. Base Case

The base case is the condition that stops the recursion. Without it, your method would call itself forever (causing a StackOverflowError).

• Acts as the "exit condition"
• Typically handles the simplest version of the problem
• Does NOT make a recursive call

2. Recursive Case

The recursive case is where the method calls itself with a modified argument that moves toward the base case.

• Makes the recursive call
• Must move toward the base case (by getting "smaller" or "closer" to the solution)
• Combines results from recursive calls to solve the original problem

public int factorial(int n) {
    // Base case
    if (n <highlight> 0 || n </highlight> 1) {
        return 1;
    }
    // Recursive case
    else {
        return n * factorial(n - 1);
    }
}

How Recursion Works: The Call Stack

When you call a method in Java, the system creates a new frame on the call stack containing:

• The method's parameters
• Local variables
• Return address

With recursion, each recursive call adds a new frame to the call stack:

Once the base case is reached, each call completes and returns a value to the previous call until the original call returns the final result.

Understanding Recursive Execution: Tracing

Let's trace through a recursive method to see how it executes:

public static int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);

}

If we call factorial(4):

Local Variables in Recursion

Each recursive call has its own set of local variables, including the formal parameters. This is crucial to understand when tracing recursive code:

public static void countdown(int number) {
    System.out.println(number); // Each call has its own 'number'
    if (number > 1) {
        countdown(number - 1);
    }
}

If we call countdown(3):

• First call: number is 3
• Second call: number is 2
• Third call: number is 1

These are separate variables in separate stack frames, not the same variable changing value.

Parameters: Tracking Progress

In recursion, parameter values capture the progress of the recursive process, similar to how loop control variables track progress in a loop.

// Loop version
public int sum(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

// Recursive version
public int sum(int n) {
    if (n <= 0) return 0;
    return n + sum(n - 1);

}

In the recursive version, the parameter n tracks the progress, much like the loop variable i does in the iterative version.

Recursion vs. Iteration

Any recursive solution can be rewritten using iteration (loops). The choice between them depends on:

Recursive Traversal of Data Structures

Recursion is particularly useful for traversing nested structures like strings, arrays, and an ArrayList:

// Count characters in a String
public int countChars(String str) {
    if (str.isEmpty()) return 0;
    return 1 + countChars(str.substring(1));
}

// Sum an array recursively
public int sumArray(int[] arr, int index) {
    if (index >= arr.length) return 0;
    return arr[index] + sumArray(arr, index + 1);
}

// Process an ArrayList recursively
public void processList(ArrayList<Integer> list, int index) {
    if (index >= list.size()) return;
    // Process current element
    System.out.println(list.get(index));
    // Process rest of list
    processList(list, index + 1);
}

Common Recursive Patterns

1. Linear Recursion: Each method makes one recursive call

   factorial(n) = n * factorial(n-1)
   

2. Binary Recursion: Each method makes two recursive calls

   fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
   

3. Tail Recursion: The recursive call is the last operation in the method

   public void countdown(int n) {
       if (n <= 0) return;
       System.out.println(n);
       countdown(n-1); // Tail recursive call
   }
   

Summary

Recursion is a powerful technique in programming where a method calls itself to solve problems by breaking them down into smaller instances of the same problem. Every recursive solution requires at least one base case to stop the recursion and at least one recursive call that moves toward that base case. Each recursive call creates its own set of local variables, allowing the method to track its progress through the parameters. While any recursive solution can be implemented iteratively, recursion often provides more elegant solutions for certain types of problems, particularly those involving nested or hierarchical data structures.