Chapter Review Questions

Note

Source: Adapted from the C# edition (recursion/recursion.rst). The C# chapter is a brief placeholder; these questions cover the full Python recursion content presented in this chapter.

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?