Recursion Quiz: AP Computer Science A (Java)

🧠 Quick Study Guide: Recursion in Java

• 🔍 Definition: Recursion is a programming technique where a method calls itself to solve a problem. Think of it like a set of Russian nesting dolls!
• 🛑 Base Case: Every recursive method MUST have a base case. This is the condition that stops the recursion, preventing an infinite loop (StackOverflowError). Without it, your program will crash!
• 🔄 Recursive Step: This is where the method calls itself, usually with a modified (smaller) version of the original problem. It moves closer to the base case.
• 🧩 Call Stack: Each recursive call creates a new frame on the call stack. When a base case is hit, frames are popped off the stack as results are returned.
• ⚖️ Iteration vs. Recursion: Any problem solvable with recursion can also be solved with iteration (loops). Recursion can lead to more elegant code for certain problems (e.g., tree traversals, fractals) but can be less efficient in terms of memory (due to stack frames).
• 🔢 Common Examples: Factorial ($n! = n \times (n-1)!$), Fibonacci sequence ($F_n = F_{n-1} + F_{n-2}$), Tower of Hanoi, binary search.
• ⚠️ Debugging: Tracing recursive calls can be tricky. Use print statements or a debugger to visualize the call stack and parameter changes.

📝 Practice Quiz: Recursion Challenge

1. Which of the following is essential for a recursive method to terminate correctly?

A) A while loop
B) A return statement
C) A base case
D) An else if statement

2. Consider the following recursive method:

public int mystery(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * mystery(n - 1);
    }
}

What is the result of mystery(4)?

A) 4
B) 10
C) 24
D) 120

3. What happens if a recursive method lacks a base case?

A) It compiles with a warning but runs correctly.
B) It results in an infinite loop, eventually causing a StackOverflowError.
C) It automatically converts to an iterative solution.
D) It returns null for all inputs.

4. Which of the following problems is often elegantly solved using recursion?

A) Iterating through an ArrayList
B) Calculating the sum of numbers in a simple array
C) Tree traversals (e.g., inorder, preorder, postorder)
D) Finding the maximum value in an array

5. In a recursive method, the recursive step typically involves:

A) Calling an entirely different method.
B) Calling itself with a modified input that moves closer to the base case.
C) Looping through an array.
D) Printing a message to the console.

6. What is the primary disadvantage of recursion compared to iteration for some problems?

A) It is always slower.
B) It uses more memory due to the call stack.
C) It is impossible to debug.
D) It makes the code less readable.

7. Given the method:

public void printStars(int n) {
    if (n > 0) {
        System.out.print("*");
        printStars(n - 1);
    }
}

What is printed by printStars(3)?

A) *
B)
C) *
D) Nothing