Recursion — Test 1

Correct Answer: A. 10
Explanation: f(4) = 4 + 3 + 2 + 1 + 0 = 10.

Correct Answer: A. RecursionError (maximum recursion depth exceeded)
Explanation: Each call adds a stack frame. CPython stops at its recursion limit, which defaults to about 1000.

Correct Answer: B. No; tail calls still consume stack frames
Explanation: Python intentionally omits TCO to keep tracebacks complete. Scala has @tailrec; Python does not.

Correct Answer: B. 123
Explanation: The print comes after the recursive call, so output happens as the calls unwind: 1, 2, 3. ALSO KNOW (related points): • Given int f(int n){ return n == 0 ? 0 : n + f(n-1); }, what is f(4)? → 10

Correct Answer: C. Exponential, O(2^n)
Explanation: The same subproblems are recomputed many times. Memoization reduces the cost to O(n). ALSO KNOW (related points): • What happens when a recursive Python function has no reachable base case? → RecursionError (maximum recursion depth exceeded) • Does CPython optimize tail-recursive calls (tail-call optimization)? → No; tail calls still consume stack frames • Which statement about recursion compared with iteration is correct? → Any recursive algorithm can be rewritten iteratively, typically by using an explicit stack

Correct Answer: C. Any recursive algorithm can be rewritten iteratively, typically by using an explicit stack
Explanation: Recursion and iteration are equally expressive. Recursion usually uses more memory because of the call stack.