Recursion Flashcards
6 cards from real AP CSA practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 Recursion flashcards as text
How many times is the base case reached when computing factorial(3) recursively?
Answer: 1
factorial(3) calls factorial(2) which calls factorial(1) which calls factorial(0) — the base case is reached exactly once.
What is the time complexity of a simple linear recursion that calls itself once per step from n down to 0?
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.
In the Fibonacci sequence defined recursively as fib(n)=fib(n-1)+fib(n-2), what are the base cases?
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.
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)?
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.
What is the output if `System.out.print(n+" ");` is moved AFTER `count(n-1);` in the previous question?
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.
Which concept does recursion naturally model when processing nested data structures like trees?
Answer: Divide and conquer
Recursion naturally models divide and conquer — splitting a problem into subproblems of the same type, as with tree traversal.