Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 3
Recursion · data structures and classes in Python (Lecture 03, Lab 03)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
Every correct recursive function needs:
A base case that answers directly, and progress towards it. A loop (b) is not needed; one recursive call (c) is enough; a global counter (d) is a debugging aid, not a requirement.
-
With
def factorial(n): return 1 if n == 0 else n * factorial(n - 1), what doesfactorial(-1)do?−1, −2, −3, … moves away from the base case 0, so the calls never stop until Python's depth limit.
ValueError(c) is what the exercise version should raise — by checkingn < 0explicitly. -
By default, CPython stops a recursion at a depth of about:
sys.getrecursionlimit()is 1,000 by default. -
How much stack space does
factorial(n)use?n + 1 frames are on the stack at the deepest point (n down to 0). Space is decided by the depth, not by the answer's size (d).
-
T(n) = T(n/2) + c solves to:
Unroll: c is added once per halving, log2 n times.
-
T(n) = 2T(n-1) + c solves to:
The number of calls doubles at every level: 1 + 2 + 4 + … + 2n-1.
-
T(n) = T(n-1) + cn solves to:
cn + c(n-1) + … + c = c n(n+1)/2.
-
How many moves does Towers of Hanoi need for 5 disks?
25 - 1 = 31.
-
How many subsets does a set of 4 items have (including the empty set and the whole set)?
Each item is either in or out: 24 = 16. (24 (c) is 4!, the number of permutations.)
-
How many orderings (permutations) do 4 distinct items have?
4! = 4 × 3 × 2 × 1 = 24.
-
How many calls in total does the naive
fib(5)make (counting the first)?fib(5) calls fib(4) and fib(3), and so on: the recursion tree has 15 nodes. (In general 2 fib(n+1) - 1.) 8 (b) is the value fib(6).
-
Fast power written as
half = power(x, n // 2) * power(x, n // 2)(then × x if n is odd). Its cost is:Two calls on n/2: T(n) = 2T(n/2) + c = O(n). Compute the half power once, store it, and square the variable: O(log n).
-
list_max(values)recurses onvalues[1:]. Its running time is:Each call copies the rest of the list: (n-1) + (n-2) + … = O(n2) — the hidden loop from Lecture 02.
-
Memoisation means:
Solve each subproblem once, store its answer (for Fibonacci, in an
Arrayindexed by n), and look it up afterwards. -
hanoi(20)makes over a million calls. At most how many frames are on the call stack at the same time?Frames are popped as calls return; the deepest chain is hanoi(20) → hanoi(19) → … → hanoi(1): about 20 frames. The total number of calls is exponential; the depth is linear.
-
What does
f(3)print?def f(n): if n == 0: return print(n, end=" ") f(n - 1) print(n, end=" ")Each call prints n on the way down, then again on the way back up, after the inner call has returned:
3 2 1then1 2 3. -
What should
subsets([])return?The empty set has exactly one subset — itself. Returning
[](b) means "no subsets", and every result built from it is then empty too. -
Tail-call optimisation in Python:
Python deliberately keeps every frame (it keeps tracebacks complete). Deep recursion should become a loop.
-
marks = [3, 1, 2]; result = marks.sort(). What isresult?sort()sorts in place and returnsNone.sorted(marks)returns the new list. -
What is
type({})?{}is an empty dictionary; an empty set isset(). -
The average cost of
x in sfor a Pythonsetof n items is:A set is a hash table: average O(1) membership. A list would be O(n).
-
What is wrong with this class?
class Dog: tricks = [] def __init__(self, name): self.name = name def add_trick(self, trick): self.tricks.append(trick)tricksis a class variable: one list shared by every instance. Create per-object data in__init__:self.tricks = []. -
Calling a function that contains
yield:The body only starts running when
next()is called — by aforloop,list()and so on. -
Why should a queue not be a Python list used with
pop(0)?Every remaining item shifts one place left. Use
collections.dequein plain Python — or, in this course, your ownCircularQueue(Week 7). -
What is
countsafter this?counts = {} for w in "a b a".split(): counts[w] = counts.get(w, 0) + 1get(w, 0)supplies 0 for a missing key, so noKeyError. -
The recurrence of naive Fibonacci, T(n) = T(n-1) + T(n-2) + c, grows like:
Each call spawns two subtrees almost as large as itself; the call count grows by a factor of about the golden ratio, 1.618, per step of n.
-
Lecture 03's
to_binary:def to_binary(n): if n < 2: return str(n) return to_binary(n // 2) + str(n % 2)What does
to_binary(6)return?to_binary(6) = to_binary(3) + "0" = (to_binary(1) + "1") + "0" = "110". The leading digits come from the recursive call, and the last digit is added on the way back up. (a) is the digits in the order they are computed, last first, which is what you would get by putting
str(n % 2)before the call; (c) adds a digit too many; (d) is the decimal number unchanged. -
With the course
gcd(return aifb == 0, elsereturn gcd(b, a % b)), how many calls doesgcd(48, 18)make in total, counting the first?gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0), which returns 6: four calls. (b) forgets the last call, the one that reaches the base case b == 0; (c) confuses the number of calls with the size of b. Euclid's algorithm is O(log min(a, b)), so the count stays small.
-
In
binary_strings, the base case is changed fromreturn [""]toreturn []. What doesbinary_strings(2)return now?def binary_strings(n): if n == 0: return [] shorter = binary_strings(n - 1) return ["0" + s for s in shorter] + ["1" + s for s in shorter]binary_strings(0)now returns[], so both comprehensions inbinary_strings(1)loop over nothing and return[], and so does every call above it. There is exactly one string of length 0, the empty string, which is why the base case must be[""]. There is no infinite recursion (d): n still goes down to 0. (c) is the correct answer with the original base case. -
flattendescends only into items for whichisinstance(item, list)is true, not into everything that is iterable. Why?The string
"ab"is iterable; its item"a"is also a string, and the item of"a"is"a"again, so the recursion never shrinks and ends inRecursionError. (a) is true of strings but has nothing to do with it; (b) is not the reason; (d) is false, since strings, tuples, sets, dicts and ranges are all iterable. -
With the course's fast
power(one call onexponent // 2, base caseexponent == 0), at most how many frames ofpowerare on the call stack at once duringpower(2, 1000)?The exponents are 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1 and 0: one frame each, 11 at the deepest point, about log₂ n. (b) and (d) describe an O(n)-deep power; (c) ignores the frames that are waiting for their recursive call to return.
-
The memoised
fib_memo(30)of Lecture 03 (memo in anArray) makes how many calls in total, counting the first?Each
fib_memo(k)for k from 2 to 30 computes its value once, making two calls; after that it is looked up. That is 29 × 2 calls plus the first one: 59, against 2,692,537 for the naivefib(30)(c). (a) and (d) count the values computed, not the calls; a call that only looks up a stored answer still counts. -
The course
merge_sortedis called on two sorted lists of 600 numbers each, and raisesRecursionError. Why?Every call outputs one item and makes one nested call on the rest, so the depth is len(left) + len(right) = 1,200, past CPython's limit of about 1,000 frames. (a) is a real cost, but it makes the merge slow, not crash; (b) equal values are fine; (c) lists can hold millions of items. This is why merge sort's real merge, in Week 10, is a loop.
-
merge_sortedcompares the heads withleft[0] <= right[0]. What would change if it used<instead?With
<, a tie takes the head ofrightfirst, so two equal keys swap their original order: the merge is still correct but not stable, and the test with(1, "L")and(1, "R")catches it. No value is lost (a), because one of the two heads is always taken; the cost is unchanged (b); equal values compare without error (d). -
sum_digits(n)makes one call onn // 10and does O(1) work besides. Its running time, in terms of the number n, is:T(d) = T(d-1) + c in the number of digits d, so O(d), and a number n has about log₁₀ n digits: O(log n). (b) would be right for a recursion on n − 1, not on n // 10; (c) forgets that there is one call per digit.
-
With Lecture 03's
depth(0 for a non-list; otherwise 1 + the deepest item, where an empty list has depth 1), what isdepth([1, [2, [3]], []])?depth(1) = 0, depth([2, [3]]) = 1 + depth([3]) = 1 + 1 = 2, and depth([]) = 1 + 0 = 1. The outer list is 1 + max(0, 2, 1) = 3. (a) forgets to count the outer list; (b) counts the empty list as if it were nested inside the deepest one.
-
In the recursive solution of Towers of Hanoi with n disks, how many times does the largest disk move?
The largest disk moves once, in the middle: before that move all n − 1 smaller disks go to the spare peg, and after it they come back on top. (c) is how often the smallest disk moves (W3-M38); (d) would mean the largest disk is moved off its target, which the algorithm never does.
-
In the moves returned by
hanoi(n), how many times does the smallest disk move?Disk k (1 is the smallest) moves 2n-k times, so the smallest disk moves 2n-1 times: on every other move, every odd-numbered one. For n = 4 the counts are 8, 4, 2, 1, which add up to 24 - 1 = 15. (c) is the total number of moves; (a) is the largest disk.
-
Why is
gcdeasy to rewrite as a plainwhileloop, whilehanoiwould need an explicit stack?In
gcd, the callreturn gcd(b, a % b)is the last thing done, so nothing has to be remembered: overwrite a and b and go round again.hanoimakes two calls and has work left after the first (move the largest disk, then the second call), and the call stack is what remembers it; a loop version must keep that stack itself. (b) is reversed; (c) is false, since any recursion can be a loop with a stack; (d) is false, since Python does no tail-call optimisation at all. -
Lecture 03's
array_max(arr, i=0)recurses oni + 1and never slices. What happens when it is called on a courseArrayof 5,000 numbers?No slicing means no copying, so the time is O(n), but each element still costs a frame: the depth is n, and 5,000 frames is past the limit. That is why (a) is wrong: the space is O(n), not O(1). (b) is the cost of the slicing version,
list_max. -
The course
subsets:def subsets(items): if not items: return [[]] rest = subsets(items[1:]) return rest + [[items[0]] + subset for subset in rest]What does
subsets([1, 2])return, in this order?subsets([2])isrest + [[2] + s for s in rest]withrest = [[]], so[[], [2]]. Thensubsets([1, 2])is[[], [2]](the subsets without 1) followed by[[1], [1, 2]](the same with 1 in front). (a) is the same subsets in another order, which the tests would also accept after sorting, but it is not what this code returns. -
Which of these can be used as a
dictkey or asetmember?A key must be hashable, and the hash must not change: a tuple of hashable values is immutable, so it qualifies. A list (a), a dict (b) and a set (c) are mutable, and Python raises
TypeError: unhashable type. Usefrozensetif you need a set as a key. -
What does this print?
t = (1, [2]) t[1].append(3) print(t)The tuple stores two references, and these cannot change: you cannot write
t[1] = [9]. But the list thatt[1]refers to is itself mutable, andappendchanges it in place, with no error (b). (c) would be true only if the list had been copied into the tuple; (d) confuses the list with its items. -
What does this print?
def countdown(n): while n > 0: yield n n -= 1 g = countdown(3) next(g) print(list(g))Calling
countdown(3)runs nothing yet.next(g)runs the body as far as the firstyieldand returns 3, which is thrown away.list(g)resumes from there and collects the rest: 2 and 1. (a) forgets that 3 has already been used; (b) would be the answer ifnexthad used up the whole generator.
36 marks
Written questions
10 written questions (36 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 36
-
Draw the call stack at every step of
factorial(3), from the first call until the final value is returned. Label winding, the base case, and unwinding, and show the value each frame returns.Model answer and marking points
— writing f for
factorial, the stack at each step, bottom → top (Lecture 03's figure draws the same thing forfactorial(4)):Step Stack What happens 1 f(3) calls f(2) 2 f(3) f(2) calls f(1) 3 f(3) f(2) f(1) calls f(0) 4 f(3) f(2) f(1) f(0) base case: f(0) returns 1 5 f(3) f(2) f(1) 1 × 1 = 1; f(1) returns 1 6 f(3) f(2) 2 × 1 = 2; f(2) returns 2 7 f(3) 3 × 2 = 6; f(3) returns 6 Marking points: each call pushes a frame with its own
n; nothing is multiplied during winding; the base case stops the growth; each return pops a frame and the frame below finishes its multiplication; maximum depth 4 = n + 1. -
Explain why the naive recursive Fibonacci takes exponential time, using a recursion tree. Show how memoisation fixes it, and state the new time and space costs.
Model answer and marking points
fib(n)callsfib(n-1)andfib(n-2); the recursion tree roughly doubles with each increase in n, because each node has two children almost as large as itself.- The same subproblems are recomputed many times: in fib(5), fib(2) is computed 3 times, fib(3) twice. Total calls 2 fib(n+1) - 1 — exponential, about 1.618n; fib(30) makes 2,692,537 calls.
- Memoisation: store each fib(k) in a memo
Arraythe first time it is computed; later calls look it up. Each value is computed once. - New cost: O(n) time (2n − 1 calls — 59 for n = 30), O(n) space for the memo plus O(n) stack depth.
-
When should you prefer recursion, and when a loop? Include two concerns that are specific to Python.
Model answer and marking points
- Recursion when the data or the problem is recursive: trees, nested lists, grammars; divide and conquer (binary search, merge sort); branching searches (subsets, Hanoi, backtracking) — where it is clearer and the depth is small.
- A loop when the recursion would be one call per element of flat data, or the depth could be large.
- Python concerns, any two: the ~1,000-frame recursion limit (
RecursionError); no tail-call optimisation, so every call costs a frame; a function call is relatively slow in CPython; slicing inside recursion silently adds O(n) per call.
-
Describe the recursive strategy for Towers of Hanoi. Write its recurrence, solve it, and explain why no algorithm can use fewer moves.
Model answer and marking points
- Strategy for n disks from A to C: move n − 1 disks A → B (recursively, using C as spare); move the largest disk A → C; move the n − 1 disks B → C (recursively, using A as spare). Base case: one disk, one move.
- Recurrence: T(1) = 1, T(n) = 2T(n-1) + 1.
- Solution: T(n) = 2n - 1 (unroll: 1, 3, 7, 15, …; or the induction proof in W3-R5).
- Minimum: the largest disk must move at least once. At that moment all the other n − 1 disks must be on the spare peg — which takes at least T(n-1) moves — and afterwards they must all be moved back on top, at least T(n-1) more. So any solution needs at least 2T(n-1) + 1 moves: the exponential cost is in the problem, not the algorithm.
-
Explain "trust the recursion" and how it relates to mathematical induction.
Model answer and marking points
- When writing the recursive case, assume the recursive call correctly solves the smaller problem, and only ask how to build this answer from that one. Do not trace every call.
- This is induction: the base case is the induction base; "if the smaller call is right then this call is right" is the inductive step. Together they prove the function correct for every input the measure reaches.
- It only works if the base case is right and the recursive case really makes progress towards it.
-
For each job, choose
list,tuple,setordictand justify by cost: (a) the marks of a class, in the order entered; (b) checking whether a student ID has already been registered; (c) looking up a student's name by ID; (d) one student's (ID, name, mark), used as a key elsewhere.Model answer and marking points
- (a) list — ordered, grows by
appendin amortised O(1), allows duplicates (two students can have the same mark). - (b) set — "have I seen this ID?" is O(1) on average against O(n) for a list; duplicates are exactly what it prevents.
- (c) dict — ID → name, O(1) average lookup by key.
- (d) tuple — a fixed record of related values of different types; immutable, therefore hashable, so it can be a dictionary key or set member (a list cannot).
- (a) list — ordered, grows by
-
hanoi(20)makes over a million calls, yet it never has more than about 20 frames on the call stack. Explain why the space a recursion needs is set by its depth and not by its number of calls. Give the depth offactorial(n), of the fastpower(x, n)and ofhanoi(n), and explain why raisingsys.setrecursionlimitis not the right fix for a recursion that must go 100,000 deep.Model answer and marking points
- A frame exists only while its call is running. When a call returns, its frame is popped, so frames do not accumulate. At any moment the stack holds only one chain of calls, from the first down to the current one, and the longest such chain, the depth, sets the space.
hanoi(20)makes 221 - 1 calls, but each chain goes 20, 19, …, 0 and returns before the next branch starts, so its stack space is O(n).- Depths:
factorial(n)n + 1 frames, O(n); fastpower(x, n)about log₂ n frames, O(log n);hanoi(n)about n frames, O(n). - Raising the limit does not make the real stack underneath bigger, so a deep enough recursion then crashes the interpreter. The fix is a different design: a loop, or a recursion that is only O(log n) deep.
-
Three versions of
power(x, n): (i)x * power(x, n - 1); (ii)half = power(x, n // 2), thenhalf * half(× x if n is odd); (iii)power(x, n // 2) * power(x, n // 2)(× x if n is odd). For each, write the recurrence and its solution, and say what happens for n = 4,096.Model answer and marking points
- (i) T(n) = T(n-1) + c → O(n) calls and multiplications, and n + 1 frames deep:
power(2, 4096)raisesRecursionError. - (ii) T(n) = T(n/2) + c → O(log n): for n = 4,096 it makes 14 calls (exponents 4096, 2048, …, 1, 0) and 14 multiplications, 14 frames deep.
- (iii) T(n) = 2T(n/2) + c → O(n): two calls on half the input undo the halving. For n = 4,096 it makes 16,383 calls. It is only about 14 deep, so it does not crash, but it is no faster than (i).
- The lesson: count the recursive calls and their size. Calling once and keeping the result in a variable is what makes (ii) logarithmic.
- (i) T(n) = T(n-1) + c → O(n) calls and multiplications, and n + 1 frames deep:
-
Rewrite
gcdas a loop, and explain why that rewrite is easy. Explain why rewritinghanoiwithout recursion is harder, and what the loop version must keep for itself.Model answer and marking points
- Loop version:
def gcd_loop(a, b): while b != 0: a, b = b, a % b return a- It is easy because
gcdis tail-shaped: one call, as its very last action, with nothing to do after it. The arguments of the next call can simply replace the current ones. hanoibranches: after the first recursive call it still has to move the largest disk and make the second call. That pending work is what the call stack remembers, so a loop version must push it onto its own stack (Lecture 06'sStack) and pop it later. This is more code, and harder to read.
-
Explain why
binary_strings(0)must return[""], andsubsets([])must return[[]], rather than[]. What goes wrong with[], and how many results dobinary_strings(n)andsubsetsof n items return?Model answer and marking points
- The base case is the answer for the smallest input, and it must be right. There is exactly one bit string of length 0 (the empty string
"") and one subset of the empty set (the empty set), so each answer is a list holding one item:[""]and[[]]. - With
[]there is nothing to build on: the recursive case makes every result by extending a result of the smaller call, so every level returns[]and the final answer is empty, with no error to warn you. binary_strings(n)returns 2n strings andsubsetsof n items returns 2n lists: each of the n decisions (0 or 1; out or in) doubles the count, and the count for n = 0 is 20 = 1, which is why the base case holds one item.
- The base case is the answer for the smallest input, and it must be right. There is exactly one bit string of length 0 (the empty string