Unit 10 Notes

Unit 10: Recursion – AP Computer Science A

🔑 Key Concepts

• Recursive methods
• Base case and recursive step
• Stack memory and method calls
• Tracing recursion
• Comparing recursion to iteration

---

🔁 What is Recursion?

Recursion is when a method calls itself to solve a smaller version of the problem.

---

🧩 Anatomy of a Recursive Method

public static int factorial(int n) {
    if (n == 0) return 1; // base case
    return n * factorial(n - 1); // recursive step
}

• Base case stops the recursion.
• Recursive step breaks down the problem into smaller pieces.

---

🔄 Example: String Reversal

public static String reverse(String s) {
    if (s.length() <= 1) return s;
    return reverse(s.substring(1)) + s.charAt(0);
}

---

⚙️ How Java Handles Recursion

Each recursive call is added to the call stack. Once the base case is reached, the stack unwinds.

---

🔃 Recursion vs Iteration

Feature	Recursion	Iteration
Uses method calls	Yes	No
Uses loop	No	Yes
Stack memory	Yes (can overflow)	Minimal
Readability	Often more elegant	Often faster and simpler

---

⚠️ Common Mistakes

• No base case → infinite recursion
• Base case not reachable
• Forgetting to return recursive result

---

🧪 Practice Multiple Choice (5 Questions)

1. What must every recursive method have?
(A) A loop
(B) A return statement
(C) A base case
(D) A variable
✅ Answer: (C)

---

2. What does this method do?

public static int sumTo(int n) {
    if (n == 1) return 1;
    return n + sumTo(n - 1);
}

(A) Prints numbers
(B) Returns sum 1 to n
(C) Returns factorial
(D) Always returns 1
✅ Answer: (B)

---

3. What is the output of this call?

System.out.println(factorial(3));

Using:

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

(A) 3
(B) 6
(C) 0
(D) 1
✅ Answer: (B)

---

4. When does recursion stop?
(A) When the return type is void
(B) When a loop breaks
(C) When the stack overflows
(D) When the base case is reached
✅ Answer: (D)

---

5. What is printed by this method?

public static void countdown(int n) {
    if (n == 0) return;
    System.out.println(n);
    countdown(n - 1);
}

Call: countdown(3);
(A) 3 2 1
(B) 1 2 3
(C) 3 3 3
(D) 0 1 2
✅ Answer: (A)

---