Chapter Review Questions

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

2. Python’s recursion limit.

   1. What error does Python raise when the recursion limit is exceeded?

   2. What is the default limit?

3. Trace factorial(3) step by step, showing each recursive call and its return value.

4. Naive recursive Fibonacci.

   1. Why is the naive recursive Fibonacci slow for large n?

   2. What is the time complexity in terms of the number of calls made?

5. Memoization with lru_cache.

   1. What does functools.lru_cache do?

   2. How does it improve the performance of recursive Fibonacci?

6. Write a recursive function sum_list(lst) that returns the sum of all integers in a list, without using sum().

7. Recursive GCD.

   1. In the recursive GCD algorithm, what is the base case?

   2. Why does the algorithm always terminate?

8. The call stack.

   1. What is a call stack?

   2. What happens to it as recursive calls are made?

   3. What happens to it as those calls return?

9. When is recursion a better choice than an iterative loop? Give one concrete example.

10. The recursive binary search splits the problem in half at each step. What is the maximum recursion depth for a list of 1024 elements?

11. Inner helper pattern.

    1. What is the advantage of putting the recursive helper function inside the outer binary_search function instead of using default parameters like lo=0 and hi=None?

    2. Can the caller accidentally pass a wrong value for low or high when using the inner helper pattern? Why or why not?

12. Property-based testing with Hypothesis.

    1. What does @given(st.lists(st.integers()), st.integers()) tell Hypothesis to do?

    2. Name two properties that the binary search test verifies for every generated input.

    3. Why is property-based testing more thorough than writing a fixed set of example inputs by hand?

13. Filesystem walker — observer pattern.

    1. What four events does FileSystemEventWalker fire during a traversal?

    2. What does returning False from enter_dir do?

    3. Write a handler class that counts the total number of files visited, without printing anything.

14. DFS vs BFS filesystem traversal.

    1. In what order does depth-first traversal (DFS) visit entries compared to breadth-first traversal (BFS)?

    2. DFS uses the call stack; BFS uses an explicit deque. What practical consequence does this have for very deep directory trees?

    3. Give one scenario where BFS is the better choice over DFS.

15. Recursive descent parser — grammar mapping.

    1. In the arithmetic grammar, why does expr call term rather than handling multiplication itself?

    2. Each grammar rule becomes one method in the Parser class. Which method handles parenthesised sub-expressions, and how does it re-enter the grammar?

    3. What is mutual recursion, and where does it appear in the parser?

16. Associativity in the recursive descent parser.

    1. Why does expr use a while loop but power uses a single if with a recursive call?

    2. Evaluate 2 ^ 3 ^ 2 by hand, showing how right-associativity groups the operands.

    3. What would change in the output of calc("8 / 4 / 2") if division were accidentally made right-associative?

17. Structural recursion in the evaluator.

    1. What does it mean for recursion to be structural?

    2. The eval_expr function uses Python match statements. What are the three cases it handles?

    3. Trace the evaluation of BinOp(Number(2), '+', Number(3)) through eval_expr, showing each recursive call and its return value.