AP Computer Science A:: Recursion

What is a RECURSIVE method?

- **A)** A method that calls ITSELF, either directly or indirectly, as part of its own execution
- **B)** A synonym for a method with no parameters
- **C)** A method that always runs exactly once and then never again
- **D)** A method that can never call any other method

What is a BASE CASE in a recursive method, and why is it essential?

- **A)** A synonym for a recursive method's parameter list
- **B)** The very FIRST time a recursive method is ever called
- **C)** A base case is optional and can safely be omitted from any recursive method
- **D)** A condition under which the method STOPS calling itself and returns a result DIRECTLY, without further recursion -- without a base case, a recursive method would call itself FOREVER, leading to infinite recursion

What is the RECURSIVE CASE in a recursive method?

- **A)** The recursive case is only relevant to loops, not recursive methods
- **B)** A synonym for the base case
- **C)** A case that never actually involves calling the method again
- **D)** The part of the method where it CALLS ITSELF, typically with a SMALLER or SIMPLER version of the original problem, making progress toward eventually reaching the base case

Given \(int\ factorial(int\ n)\ \{\ if\ (n\ ==\ 0)\ \{\ return\ 1;\ \}\ else\ \{\ return\ n\ *\ factorial(n\ -\ 1);\ \}\ \}\), what is the BASE CASE of this method?

- **A)** This method has no base case at all
- **B)** The entire method is a base case with no recursive part
- **C)** \(n\ ==\ 0\), which returns \(1\) directly without any further recursive call
- **D)** \(n\ *\ factorial(n - 1)\), the recursive call itself

What would happen if the \(factorial\) method's BASE CASE (\(n\ ==\ 0\)) were REMOVED entirely, leaving only the recursive case?

- **A)** This would cause a compile-time error
- **B)** INFINITE RECURSION would occur -- the method would keep calling itself with smaller and smaller values of \(n\) forever (going negative, since nothing stops it), eventually causing a \(StackOverflowError\)
- **C)** The method would return \(0\) immediately
- **D)** The method would work exactly the same as before, with no functional difference

What is a \(StackOverflowError\), and what commonly causes it in the context of recursion?

- **A)** \(StackOverflowError\) indicates the program finished successfully
- **B)** A compile-time error indicating a syntax mistake
- **C)** A runtime error that occurs when TOO MANY method calls are stacked up without returning (e.g., from missing or incorrect base cases causing excessive or infinite recursion), exhausting the memory reserved for tracking active method calls
- **D)** An error that only occurs in loops, never in recursive methods

Trace through \(factorial(4)\) using \(int\ factorial(int\ n)\ \{\ if\ (n\ ==\ 0)\ \{\ return\ 1;\ \}\ else\ \{\ return\ n\ *\ factorial(n\ -\ 1);\ \}\ \}\). What value does it return?

- **A)** \(4\)
- **B)** \(10\)
- **C)** \(24\), since \(4! = 4 \times 3 \times 2 \times 1 \times 1 = 24\)
- **D)** \(0\)

What is the general STRATEGY behind recursion for solving a problem?

- **A)** Solve the entire problem in a single step with no sub-problems involved at all
- **B)** Break the ORIGINAL problem down into ONE OR MORE SMALLER, SIMPLER versions of the SAME problem, solve those smaller versions (often via further recursive calls), and then COMBINE their results to solve the original problem
- **C)** Recursion always requires solving a completely unrelated, different problem first
- **D)** Recursion strategy is identical to writing a single \(if\) statement with no repetition of any kind