How many recursive calls are made when evaluating fib(4) using the function below?
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
```
- 5 recursive calls are made
- 7 recursive calls are made (correct answer)
- 9 recursive calls are made
- 4 recursive calls are made
Explanation: This question tests AP Computer Science A skills in understanding recursion, specifically counting recursive calls in tree-like recursive structures. Recursion involves solving a problem by solving smaller instances of the same problem, using base cases to terminate the recursion and recursive cases to reduce the problem size. In this problem, the recursive function fib(n) makes two recursive calls for each non-base case, creating a binary tree of calls. Choice B is correct because fib(4) makes 7 total recursive calls: fib(4) calls fib(3) and fib(2); fib(3) calls fib(2) and fib(1); the first fib(2) calls fib(1) and fib(0); the second fib(2) also calls fib(1) and fib(0) - counting all recursive calls gives 7. Choice C is incorrect because it overcounts the calls. To help students: Draw the complete call tree for small examples, labeling each node with its argument. Teach them to count all nodes except the root, and emphasize how exponential growth occurs in naive Fibonacci recursion.