Recursion

Hey there. I'm Saavi, and today we're tackling one of the most elegant (and sometimes mind-bending) concepts in programming: recursion. It might feel strange at first, but once it clicks, you'll see it as a powerful tool in your problem-solving toolkit.

What is Recursion?

At its heart, recursion is simple: a recursive method is a method that calls itself.

Instead of using a for or while loop to repeat an action, a recursive method repeats its logic by invoking another instance of itself. Think of it as a function passing a baton to... well, itself, but a slightly different version that's closer to the finish line.

Every recursive method needs two key ingredients. Miss either one, and it won't work.

1. 1
   A Base Case

   This is the condition that stops the recursion. It's a simple version of the problem that the method can solve directly, without calling itself again. In our nesting doll analogy, the base case was the tiny, solid doll.
2. 2
   A Recursive Call

   This is the part of the method that calls itself, but with modified arguments that move it closer to the base case. This is crucial—the problem must get smaller or simpler with each call. Opening a nesting doll reveals a smaller doll, not one the same size.

Let's look at a simple countdown example:

public void countdown(int n) {
    // Base Case: If n is zero, stop.
    if (n <= 0) {
        System.out.println("Blastoff!");
        return; // This ends this specific method call.
    }

    // The work for the current step
    System.out.println(n);

    // Recursive Call: Call the method again with a smaller number.
    countdown(n - 1);
}

// Calling it from main:
// countdown(3);

If you call countdown(3), it will print 3, then call countdown(2). countdown(2) will print 2, then call countdown(1). This continues until countdown(0) is called. It hits the base case, prints "Blastoff!", and stops.

How Java Keeps Track: The Call Stack

You might be wondering, "If the method keeps calling itself, how does it know where to return to?" This is where most students get a little lost, but the concept is very visual.

Java manages method calls using something called the call stack. Think of it like a stack of plates in a cafeteria.

1. When you call a method, Java places a "plate" on top of the stack. This plate holds all of the method's local variables, including its parameters.
2. If that method calls another method (even itself), a new plate for the new call is placed on top of the first one.
3. When a method finishes, its plate is taken off the top of the stack, and control returns to the method on the plate just below it.

Each recursive call gets its own separate set of variables. The n in countdown(3) is a completely different variable in memory from the n in countdown(2). The parameter n is what tracks the progress of our recursion, just like an int i variable tracks the progress of a for loop.

Let's trace countdown(3) with the call stack:

1. main calls countdown(3). A plate for countdown(3) is put on the stack. It prints 3.
2. countdown(3) calls countdown(2). A new plate for countdown(2) is put on top. It prints 2.
3. countdown(2) calls countdown(1). A plate for countdown(1) goes on top. It prints 1.
4. countdown(1) calls countdown(0). A plate for countdown(0) goes on top. It hits the base case, prints "Blastoff!", and finishes.
5. The countdown(0) plate is removed. Control returns to countdown(1).
6. countdown(1) has nothing left to do, so it finishes. Its plate is removed.
7. countdown(2) has nothing left to do. Its plate is removed.
8. countdown(3) has nothing left to do. Its plate is removed. The stack is empty.

The program prints: 3 2 1 Blastoff!

Recursion vs. Iteration

You might have noticed that our countdown method could easily be written with a for loop.

// Iterative version of countdown
public void countdownIterative(int n) {
    for (int i = n; i > 0; i--) {
        System.out.println(i);
    }
    System.out.println("Blastoff!");
}

This brings up a critical point: any problem you can solve with recursion, you can also solve with iteration (loops), and vice versa.

So why use recursion?

• Clarity
  For some problems, like navigating a family tree or a file system, the recursive solution is much cleaner and easier to read than a complicated loop-based one.
• Problem Structure
  It's a natural fit for problems that are defined in terms of themselves (like a factorial, which we'll see next).

However, recursion has a downside. Every method call uses memory on the call stack. If your recursion goes too deep (e.g., you forget a base case), you can run out of memory and get a StackOverflowError. Iterative solutions are often more memory-efficient. On the AP exam, you'll need to be able to read, trace, and understand both.

Let's walk through two classic examples to make this concrete. Tracing the calls is the single best way to get comfortable with recursion.

public int factorial(int n) {
    // Base Case: If n is 0 or 1, the factorial is 1.
    if (n <= 1) {
        return 1;
    }
    // Recursive Step: n times the factorial of (n-1).
    else {
        return n * factorial(n - 1);
    }
}

public int sumArray(int[] arr, int index) {
    // Base Case: If the index is out of bounds, we're done. Add 0.
    if (index >= arr.length) {
        return 0;
    }
    // Recursive Step: The element at this index plus the sum of the rest.
    else {
        return arr[index] + sumArray(arr, index + 1);
    }
}

// To start the process, you'd call it with index 0:
// int[] myNums = {5, 10, 2};
// int total = sumArray(myNums, 0);

Ready to try a couple on your own? Don't worry about writing perfect code. Focus on identifying the base case and the recursive step.

1. 1
   Power Function

   Write a recursive method power(base, exp) that calculates base raised to the power of exp (e.g., power(2, 3) should return 8). Assume exp is a non-negative integer.

   • Hint: How can you define base^exp in terms of base^(exp-1)? What's the simplest possible exponent you can calculate directly (this will be your base case)?
2. 2
   Count Character

   Write a recursive method countChar(String str, char c) that counts how many times the character c appears in the string str.

   • Hint: The problem for "hello" can be broken down into: check the first character ('h'), and then solve the rest of the problem for "ello". The substring() method will be very helpful here. What's the base case? Think about the simplest possible string.