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:* Many recursive functions contain no loop at all (the recursion does the repeating), and a conditional alone isn't enough: without a self-call there's no recursion. *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:* In CPython, the standard Python interpreter, `sys.getrecursionlimit()` returns 1000 unless something has changed it with `sys.setrecursionlimit()`. Your module-level code occupies one of those frames, so a recursive function gets slightly fewer than 1,000 nested calls. *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. Each increment of n multiplies the number of calls by about 1.6 (the golden ratio), so O(2^n) is a simple upper bound; either way, the growth is exponential. *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, `total(3)` calls `total(2)`, `total(1)`, `total(0)`, `total(-1)`, and so on until Python raises `RecursionError`. **Fix:** 
def total(n):
    if n <= 0:
        return 0
    return n + total(n - 1)
The base case `if n <= 0: return 0` stops the recursion when n reaches 0. Using `<=` rather than `==` also means a negative argument returns 0 right away instead of recursing forever. *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) mainly because the eliminated frames would disappear from tracebacks, making debugging harder, and because code that relied on TCO would break on Python implementations that didn't provide it. 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:** Both caches persist between calls, but the student's `memo` is a module-level global that any code can modify or replace by accident (handy for a test to clear, risky in a large program). `@cache` keeps its cache hidden inside 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:** The `functools` documentation guarantees that the cache stays coherent when several threads call the function at once. With a hand-rolled dictionary, getting that right is your job. 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