AP CSA Recursion 2 — Questions and Answers
Question 1: How many times is the base case reached when computing factorial(3) recursively?
- 1 (Correct answer)
- 3
- 4
- 0
Correct answer: 1
factorial(3) calls factorial(2) which calls factorial(1) which calls factorial(0) — the base case is reached exactly once.
Question 2: What is the time complexity of a simple linear recursion that calls itself once per step from n down to 0?
- O(n) (Correct answer)
- O(n²)
- O(log n)
- O(1)
Correct answer: O(n)
A recursion that makes one call per level and counts down from n to 0 executes n+1 calls, giving O(n) time complexity.
Question 3: In the Fibonacci sequence defined recursively as fib(n)=fib(n-1)+fib(n-2), what are the base cases?
- fib(0)=0 and fib(1)=1 (Correct answer)
- fib(0)=1 and fib(1)=1
- fib(1)=1 only
- fib(0)=0 only
Correct answer: fib(0)=0 and fib(1)=1
The standard recursive Fibonacci has two base cases: fib(0)=0 and fib(1)=1, terminating the recursion.
Question 4: What is the output of: `public void count(int n){ if(n==0) return; System.out.print(n+" "); count(n-1); }` called with count(3)?
- 3 2 1 (Correct answer)
- 1 2 3
- 3 2 1 0
- 0 1 2 3
Correct answer: 3 2 1
count(3) prints 3, then calls count(2) which prints 2, then count(1) which prints 1, then count(0) returns.
Question 5: What is the output if `System.out.print(n+" ");` is moved AFTER `count(n-1);` in the previous question?
- 1 2 3 (Correct answer)
- 3 2 1
- 0 1 2
- 3 2 1 0
Correct answer: 1 2 3
When the print is after the recursive call, execution prints on the way back up the call stack, giving ascending order.
Question 6: Which concept does recursion naturally model when processing nested data structures like trees?
- Divide and conquer (Correct answer)
- Parallel processing
- Iteration
- Linear search
Correct answer: Divide and conquer
Recursion naturally models divide and conquer — splitting a problem into subproblems of the same type, as with tree traversal.
AP CSA Recursion 2
How many times is the base case reached when computing factorial(3) recursively?