Micro-questions over the recursion fundamentals module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why recursion
1. Why can’t you count files in a nested directory tree with loops?
Answer
A loop needs its nesting fixed when you write the code; this problem’s nesting is fixed only at runtime, because you do not know how deep the directories go.
2. State the recursive insight for that problem.
Answer
The number of files in a directory is the number of loose files in it, plus the number of files in each of its subdirectories — the second half is the same question, asked about something smaller.
3. When is the recursive insight available in general?
Answer
Whenever a problem’s answer can be phrased in terms of the same problem on a smaller input.
4. What do the mirror and Russian doll analogies each get right and wrong?
Answer
Both capture the self-similarity. Mirrors miss the shrinking — they recurse forever. A doll does not, because each is strictly smaller and the smallest is solid. The shrinking is what makes recursion a technique rather than a bug.
B. The vocabulary
5. What is a base case?
Answer
An input the function answers immediately without calling itself. A recursion with no reachable base case never terminates.
6. What is the recursive case?
Answer
The branch that reduces the problem and calls itself — e.g. n * factorial(n-1).
7. What is progress, and why does it matter?
Answer
The requirement that every recursive call moves strictly closer to a base case. It separates a recursion from an infinite loop, and it is the property easiest to get subtly wrong.
8. What is a stack frame?
Answer
Also an activation record — the block of memory holding one call’s locals, arguments, and return address. Every call in progress has one; it is released when that call returns.
9. What is recursion depth, and why is it a different quantity from call count?
Answer
The number of frames at the deepest point — the memory cost. Naive Fibonacci makes millions of calls at a depth of only .
10. What are winding and unwinding?
Answer
Winding is the descent, where calls are made and frames pile up. Unwinding is the return journey, where answers come back and frames are released. Work before the recursive call happens on the way down; work after it happens on the way up.
11. What is a tail call?
Answer
A recursive call where nothing happens after it returns — its result is returned directly. return helper(n-1, acc+n) is one; return n * factorial(n-1) is not, because the multiplication still has to happen.
12. Does Python optimise tail calls?
Answer
No — deliberately. Some languages reuse the frame and recurse in constant space; Python does not.
13. What is memoisation?
Answer
Caching the answer to each distinct subproblem the first time it is computed. The bridge from recursion to dynamic programming.
14. What are overlapping subproblems?
Answer
When the recursion tree contains the same subproblem many times. It is what makes memoisation worth doing, and its absence is why memoising merge sort achieves nothing.
C. The three questions
15. What should you not try to do when writing a recursion?
Answer
Picture the whole thing. Nobody can, and the attempt is what makes recursion feel hard.
16. State the three questions.
Answer
- What is the smallest input I can answer without thinking? → base case.
- Assuming the function already works for smaller inputs, how do I build the answer for
n? → recursive case. - Does every recursive call actually move toward the base case? → progress.
17. Apply the three questions to summing a list.
Answer
- Empty list → 0.
- First element plus the sum of the rest.
- The rest is one shorter, and length cannot go below zero. ✓
18. Which question requires a leap, and what is the leap?
Answer
Question 2. You are permitted to assume the recursive call returns the correct answer — that is exactly what you are in the middle of proving.
19. What is the three-question method actually an instance of?
Answer
Induction. The base case is the base step, the recursive case is the inductive step, and progress guarantees you reach the base.
20. What is wrong with list_sum(values[1:]) as an implementation?
Answer
values[1:] copies the rest of the list on every call, making it in both time and memory. Pass an index instead.
D. The call stack
21. Trace list_sum([3,1,4]) through both phases.
Answer
Winding: frames for [3,1,4], [1,4], [4], [] pile up. Unwinding: [] returns 0, [4] returns 4, [1,4] returns 5, [3,1,4] returns 8.
22. What has happened by the end of the winding phase?
Answer
No addition at all. Every frame is suspended mid-expression, holding its values[0], waiting. The additions all happen on the way back up, in reverse order.
23. Where does the memory go, when the function stores nothing?
Answer
The pending frames are the storage.
24. State the single most useful thing to know about recursion’s cost.
Answer
Its space complexity is the depth of the recursion, not the number of calls.
E. The three failures
25. Failure 1 — what is it, and what happens?
Answer
No base case. It runs until the stack is exhausted — RecursionError in Python.
26. Failure 2 — why is if n == 0 with n - 2 nastier?
Answer
It works for half the inputs. evens_down(10) is fine; evens_down(11) goes and never equals 0.
27. State the general rule that fixes it.
Answer
A base case should be a condition the argument cannot jump past, not a value it must land on exactly. Use if n <= 0.
28. Failure 3 — what is wrong with linear(100_000)?
Answer
Nothing is wrong with the logic. The machine simply cannot hold 100,000 frames at once.
29. Is that a Python quirk?
Answer
No — it is a real limit everywhere. Python merely reports it politely instead of segfaulting.
30. Give the three responses in order of preference.
Answer
- Rewrite it iteratively if the recursion is linear.
- Restructure so the depth is — what divide and conquer buys you.
- Raise the limit with
sys.setrecursionlimit(), only when you know the real depth is bounded. Last resort.
F. The cost of a recursion
31. How many calls does naive fib(30) make?
Answer
2,692,537.
32. Why, structurally?
Answer
Branches recompute identical answers. In the fib(5) tree, fib(3) appears twice, fib(2) three times, fib(1) five times. The tree roughly doubles per increase in , giving — close enough to .
33. How many distinct subproblems are there, and what follows?
Answer
Only — fib(0) through fib(n). If each is computed once, the total work is .
34. What is the memoised call count?
Answer
— 59 calls for , against 2.7 million.
35. What does the cache do to the shape?
Answer
It turns the exponential tree into a linear chain.
36. Why would memoising merge sort gain nothing?
Answer
Because merge sort never sorts the same sublist twice — there are no overlapping subproblems to cache.
G. Where recursion goes next
37. Give the routing table.
Answer
| If the recursion… | You have | Depth |
|---|---|---|
| shrinks by 1 | linear recursion — a loop in disguise | |
| splits into halves | divide and conquer | |
| revisits subproblems | dynamic programming | state count |
| explores and undoes choices | backtracking | often exponential |
| walks a structure with children | traversal |
38. What single question routes you between them?
Answer
Do the recursive calls overlap? If two branches ever solve the identical subproblem, memoise — you are in DP. If they never do, a cache is pure overhead.
H. Traps
39. What is wrong with def fib(n, memo={})?
Answer
The mutable default is shared across every call to the function for the lifetime of the program, including calls from unrelated code. Use memo=None and create it inside.
40. Why is setrecursionlimit dangerous rather than merely a last resort?
Answer
It converts a clean error into a possible interpreter crash — the C stack has its own limit that Python’s counter does not track.
41. What must you add when recursing on a cyclic structure?
Answer
A visited set. Directory traversal with symlinks, or a graph, loops forever no matter how correct your base case is.
42. Summarise the module in one sentence.
Answer
Answer three questions — base case, recursive case assuming it works, and progress — then stop thinking; the cost is calls in time and depth in memory, and they are unrelated.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Recursion Fundamentals — the module
- Recursion Trees & Recurrences — Question Bank — the next bank
- Memoisation and Tabulation
Software engineering
Infrastructure & security
Computer science
Hardware & engineering