Unit 4.16: Recursion

What is Recursion?

Recursion is a programming technique where a method calls itself to solve a problem. It is another form of repetition, similar to loops. A recursive method must have two main components:

Base Case

A base case is a condition that stops the recursion. It returns a value directly without making further recursive calls. Without a base case, recursion results in a StackOverflowError.

Recursive Step

The recursive step is where the method calls itself with a modified argument that moves the process closer to the base case.

Task: Calculating the factorial of a number recursively.

// In the main method ...
public static int factorial(int n) {
    if (n <= 1) {
        return 1; // Base Case
    } else {
        return n * factorial(n - 1); // Recursive Step
    }
}

Recursion Factorial

The Call Stack

Each recursive call has its own set of local variables and parameters. This "state" is stored in a stack frame on the computer's call stack.

Independent State

Every time a method calls itself, a new frame is added to the stack. The variables in one call do not interfere with the variables in another call, even if they have the same name.

Recursion vs. Iteration

Any recursive solution can be replicated through the use of an iterative approach (using loops), and vice versa.

Choosing an Approach

Recursion is often more elegant for naturally recursive structures (like trees), while iteration is typically more memory-efficient because it doesn't create new stack frames for every repetition.

Exclusion Statement: Writing recursive code is outside the scope of the AP Computer Science A course and exam. You are only required to trace and determine the result of calling recursive methods.