Question Bank
Recursion Trace Challenge
Difficulty: Medium
Five Python tracing prompts on recursive call counts, return values, stack-frame depth, and a base-case bug hunt.
Recursion Trace Challenge
Five Python tracing prompts on recursive call counts, return values, stack-frame depth, and a base-case bug hunt.
470 views
6
What does f(4) return for the function below? Walk the call tree.
Examples
Example 1:
Input: f(4)
Output: 3
Explanation: f(4) -> f(3) + f(2). f(3) -> f(2) + f(1) = 1 + 1 = 2. f(2) -> f(1) + f(0) = 1 + 0 = 1. Final: 2 + 1 = 3 (the 4th Fibonacci number). Note f(2) is computed twice, motivating memoization.Implement count_calls(n) that counts how many calls a naive recursive fib(n) makes. Verify your implementation by printing the count for n = 10.
Examples
Example 1:
Input: count_calls(10)
Output: 177
Explanation: Each call issues two child calls except at the base case, so C(n) = C(n - 1) + C(n - 2) + 1 with C(0) = C(1) = 1. The closed form is 2 * fib(n + 1) - 1, exponential in n.Trace mystery([1, 2, 3, 4]). List every value that gets print-ed and explain what the function computes.
Examples
Example 1:
Input: mystery([1, 2, 3, 4])
Output: prints '4 0', '3 4', '2 7', '1 9' in order; returns 10
Explanation: The recursion descends to the empty list (returning 0), then unwinds, printing each head paired with the running sum of the tail. mystery is a recursive sum: head + rest at every frame.What is the maximum stack depth reached by count_down(900) below in CPython, and what happens if you call count_down(2000) (or even count_down(1000)) with default settings?
Examples
Example 1:
Input: count_down(900) on a default CPython interpreter
Output: completes normally; peak depth around 901 frames
Explanation: CPython's default sys.getrecursionlimit() is 1000, but interpreter wrapper frames consume a handful, leaving headroom around 900.Example 2:
Input: count_down(2000)
Output: raises RecursionError: maximum recursion depth exceeded
Explanation: Even count_down(1000) typically raises because of the wrapper frames. The robust fix is iteration or trampolining.Spot the bug. This factorial(n) is meant to return n! but enters infinite recursion for n = 0.
Examples
Example 1:
Input: factorial(0)
Output (buggy version): infinite recursion until RecursionError
Output (fixed version): 1
Explanation: The bug only catches n == 1. factorial(0) recurses to factorial(-1), then -2, etc. The fix is base case n <= 1 (which also handles 0! = 1 correctly) and an explicit guard for negative input.