Quiz: Recursion

Test your understanding before moving on. Target: 70% or higher to proceed confidently.

Section 1: Multiple Choice (1 point each)

1. What are the two essential components of every recursive function?

  • A) A loop and a conditional
  • B) A base case and a recursive case
  • C) A return statement and a print statement
  • D) An input parameter and a default argument
Answer **B)** A base case and a recursive case. *Why B:* Every recursive function needs a base case (to stop the recursion) and a recursive case (to call itself with a smaller problem). *Why not A:* Recursive functions typically don't use loops; the recursion replaces the loop. *Why not C:* While return statements are common, print statements are not required. *Why not D:* Parameters are needed, but default arguments are not essential. *Reference:* Section 18.1

2. What happens if a recursive function has no base case?

  • A) It returns None
  • B) It runs forever in an infinite loop
  • C) Python raises a RecursionError when the stack overflows
  • D) Python automatically detects the missing base case and adds one
Answer **C)** Python raises a `RecursionError` when the stack overflows. *Why C:* Without a base case, the function calls itself indefinitely. Python's default recursion limit (~1,000 calls) catches this and raises `RecursionError`. *Why not B:* It's not technically an infinite loop — it's infinite recursion, which Python halts. *Why not D:* Python has no mechanism to detect or fix missing base cases. *Reference:* Section 18.8

3. What is the output of the following code?

def f(n):
    if n <= 0:
        return 0
    return n + f(n - 2)

print(f(7))
  • A) 7
  • B) 12
  • C) 16
  • D) 28
Answer **C)** 16 *Trace:* f(7) = 7 + f(5) = 7 + 5 + f(3) = 7 + 5 + 3 + f(1) = 7 + 5 + 3 + 1 + f(-1) = 7 + 5 + 3 + 1 + 0 = 16 *Reference:* Sections 18.2-18.3

4. In the recursive factorial function, what does factorial(0) return?

  • A) 0
  • B) 1
  • C) None
  • D) It raises an error
Answer **B)** 1 *Why B:* 0! = 1 by mathematical convention, and this is the base case of the recursive factorial: `if n == 0: return 1`. *Reference:* Section 18.2

5. What is the default recursion limit in Python?

  • A) 100
  • B) 500
  • C) 1,000
  • D) 10,000
Answer **C)** 1,000 *Why C:* Python's default `sys.getrecursionlimit()` returns approximately 1,000 (the exact value may vary slightly by platform, but 1,000 is the standard). *Reference:* Section 18.8

6. What is memoization?

  • A) Converting a recursive function to an iterative one
  • B) Caching the results of function calls to avoid redundant computation
  • C) Adding print statements to trace recursive calls
  • D) A technique for increasing the recursion limit
Answer **B)** Caching the results of function calls to avoid redundant computation. *Why B:* Memoization stores the result of each unique function call so that if the same arguments are used again, the cached result is returned immediately. *Why not A:* That's iteration conversion, a separate technique. *Why not C:* That's call tracing for debugging. *Why not D:* That would be `sys.setrecursionlimit()`. *Reference:* Section 18.6

7. The naive recursive Fibonacci function has what time complexity?

  • A) O(n)
  • B) O(n log n)
  • C) O(2^n)
  • D) O(n^2)
Answer **C)** O(2^n) *Why C:* Each call branches into two sub-calls, creating a tree of calls that grows exponentially. The number of calls roughly doubles with each increment of n. *Why not A:* That's the complexity of the memoized version. *Reference:* Section 18.6

8. Which Python module provides the @cache decorator for automatic memoization?

  • A) collections
  • B) functools
  • C) itertools
  • D) sys
Answer **B)** `functools` *Why B:* `functools.cache` (Python 3.9+) and `functools.lru_cache` provide automatic memoization decorators. *Reference:* Section 18.6

9. Which of the following is NOT a good use case for recursion in Python?

  • A) Traversing a directory tree
  • B) Summing numbers from 1 to 1,000,000
  • C) Processing nested JSON data
  • D) Generating fractal patterns
Answer **B)** Summing numbers from 1 to 1,000,000 *Why B:* With Python's default recursion limit of ~1,000, this would cause a `RecursionError`. A simple `for` loop or `sum(range(1, 1_000_001))` is far better. *Why not A, C, D:* These all involve naturally recursive structures or self-similar patterns where recursion is the natural approach. *Reference:* Section 18.5

10. What does "tree recursion" mean?

  • A) A recursive function that processes tree data structures
  • B) A recursive function that makes more than one recursive call per step
  • C) A recursive function with more than one base case
  • D) A recursive function that uses a tree to track its calls
Answer **B)** A recursive function that makes more than one recursive call per step. *Why B:* Tree recursion occurs when a function calls itself multiple times (e.g., `fib(n-1) + fib(n-2)`), creating a tree-shaped call graph. *Why not A:* While tree recursion can be used on tree structures, the term refers to the shape of the call graph, not the data being processed. *Reference:* Section 18.6

Section 2: Short Answer (2 points each)

11. Explain the "leap of faith" in recursive thinking. Why is it a useful strategy?

Answer The "leap of faith" means trusting that the recursive call correctly solves the smaller problem without tracing through every recursive call. Instead of mentally simulating each call, you verify three things: (1) the base case is correct, (2) the recursive call works on a smaller problem, and (3) the current step correctly combines the recursive result to solve the full problem. This is useful because tracing every call is impractical for large inputs and unnecessary — verifying the structure is more reliable and scalable than step-by-step simulation. *Reference:* Section 18.9

12. What is the difference between a stack overflow and a RecursionError in Python?

Answer A stack overflow occurs when the call stack exhausts available memory, which can crash the entire program or process. Python prevents this by imposing a recursion limit (default ~1,000). When a function exceeds this limit, Python raises a `RecursionError` — a catchable exception — before a true stack overflow occurs. So `RecursionError` is Python's safety net that halts runaway recursion gracefully. *Reference:* Section 18.8

13. A classmate writes this function and says it computes the sum of all integers from 1 to n. Is it correct? If not, fix it.

def total(n):
    return n + total(n - 1)
Answer **Not correct** — it's missing a base case. Without one, it will recurse forever (and raise `RecursionError`). Even if it had a base case, calling `total` with a negative number or zero would also be problematic. **Fix:** 
def total(n):
    if n <= 0:
        return 0
    return n + total(n - 1)
The base case `if n <= 0: return 0` ensures the recursion stops when n reaches 0. *Reference:* Sections 18.2, 18.8

14. Why does Python not implement tail call optimization? Name one practical consequence.

Answer Python's creator Guido van Rossum chose not to implement tail call optimization (TCO) because it would obscure stack traces, making debugging harder, and it conflicts with Python's emphasis on readability and transparent execution. A practical consequence is that even tail-recursive functions in Python use O(n) stack space and are subject to the recursion limit — so deep recursion must be rewritten iteratively. *Reference:* Section 18.11

Section 3: Code Analysis (3 points each)

15. What is the output of this code?

def mystery(s):
    if len(s) <= 1:
        return s
    return mystery(s[1:]) + s[0]

print(mystery("abcd"))
  • A) "abcd"
  • B) "dcba"
  • C) "bcda"
  • D) "dabc"
Answer **B)** `"dcba"` *Trace:* - mystery("abcd") = mystery("bcd") + "a" - mystery("bcd") = mystery("cd") + "b" - mystery("cd") = mystery("d") + "c" - mystery("d") = "d" (base case) - Unwinding: "d" + "c" = "dc", "dc" + "b" = "dcb", "dcb" + "a" = "dcba" The function reverses the string by moving the first character to the end after reversing the rest. *Reference:* Section 18.4

16. How many times is fib(2) called when computing fib(5) using the naive recursive implementation (no memoization)?

  • A) 1
  • B) 2
  • C) 3
  • D) 5
Answer **C)** 3 The call tree for fib(5) shows that fib(2) is computed three separate times: - Once as a child of fib(4) → fib(3) → fib(2) - Once as a direct child of fib(4) → fib(2) - Once as a child of fib(3) on the right branch of fib(5) → fib(3) → fib(2) This redundant computation is why naive recursive Fibonacci is O(2^n). *Reference:* Section 18.6

17. What is wrong with this recursive function?

def power(base, exp):
    if exp == 1:
        return base
    return base * power(base, exp - 1)
Answer The function doesn't handle `exp == 0`. Mathematically, any number raised to the power 0 equals 1, but `power(5, 0)` would call `power(5, -1)`, then `power(5, -2)`, and so on — infinite recursion leading to `RecursionError`. **Fix:** Change the base case to `if exp == 0: return 1` (or add it as an additional base case). *Reference:* Section 18.8

18. What is the maximum depth of the call stack when computing factorial(5)?

  • A) 4
  • B) 5
  • C) 6
  • D) 10
Answer **C)** 6 The call chain is: factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0). That's 6 active frames on the stack at the point when the base case factorial(0) is reached. *Reference:* Section 18.3

Section 4: Application (4 points each)

19. Write a recursive function replace_all(s, old, new) that replaces all occurrences of a single character old with character new in string s. Do not use any built-in string replace methods.

# Should work for:
# replace_all("hello", "l", "r") → "herro"
# replace_all("aaa", "a", "b") → "bbb"
# replace_all("xyz", "a", "b") → "xyz"
Answer 
def replace_all(s, old, new):
    if s == "":
        return ""
    first = new if s[0] == old else s[0]
    return first + replace_all(s[1:], old, new)
Base case: empty string returns empty string. Recursive case: check if the first character matches `old`; if so, use `new`; otherwise keep the original. Then concatenate with the recursive result of the rest of the string. *Reference:* Section 18.4

20. A student claims that the following memoized Fibonacci is "just as good" as using @functools.cache. Evaluate this claim — is it correct, and are there any differences?

memo = {}

def fib_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        result = n
    else:
        result = fib_memo(n - 1) + fib_memo(n - 2)
    memo[n] = result
    return result
Answer The student's implementation is **functionally equivalent** to `@functools.cache` for basic usage — both achieve O(n) time complexity by caching results. However, there are differences: 1. **Global state:** The student uses a module-level dictionary `memo`, which persists across calls and could cause issues in testing or if the function is used in multiple contexts. `@cache` encapsulates the cache within the decorated function. 2. **Cache management:** `@functools.cache` provides a `.cache_info()` method to inspect hits/misses and a `.cache_clear()` method to reset. The student's version requires manual management of the `memo` dict. 3. **Thread safety:** `@functools.lru_cache` has some built-in thread safety considerations; a bare dictionary does not. 4. **Code cleanliness:** `@cache` requires no changes to the function's logic — you write the clean recursive version and add one line. The manual approach mixes caching logic with the algorithm. So the performance is equivalent, but `@functools.cache` is the better practice for production code. *Reference:* Section 18.6