Corrected exercises: recursion, and when a loop is the better answer, COMP 202

a) def factorial(n): if n == 0: return 1, then return n * factorial(n - 1). The base case is $n = 0$ and the answer there is 1, because the empty product is 1: it is the value that makes $1! = 1 \times 0!$ come out right, exactly as the starting value of a product accumulator is 1 in the loops set. Choosing $n = 1$ as the base case also works and is one case less general, since factorial(0) then has to be handled separately.

b) RecursionError, maximum recursion depth exceeded, after about a thousand calls, which is Python's default limit. It is not an infinite loop because each call consumes memory: a frame is pushed on the stack and never popped, so the program hits a wall instead of spinning for ever. That difference is useful in practice, since an infinite loop hangs silently while an infinite recursion reports itself with a traceback naming the function.

c) The same RecursionError, and the missing word is the subtraction: factorial(n) calls factorial(n) with the very same argument, so the problem never gets smaller and the base case is never reached. This is the second obligation failing rather than the first, and it is worth being able to tell the two apart, because the fix is in a different place: here the base case is present and correct, and it is unreachable.

d) It gives back None, for every n other than the base case. The multiplication is computed and thrown away, exactly as with a string method whose result is not assigned; the function falls off its end and returns None, and the caller then raises TypeError on the multiplication. This is the single most common recursion bug in a first course, and it is worth checking as a reflex: every branch of a recursive function must RETURN.

e) Every call decreases n, so from -1 it goes to -2, -3 and so on, moving AWAY from the base case n == 0: the result is RecursionError again. The guard belongs at the top of the function, before anything else, if n < 0: raise ValueError with a message. Testing n <= 0 in the base case instead would return 1 for a negative number, which is a wrong answer quietly returned, and the functions set already said which of the two is worse.

a) The sentence: sum_list returns the total of every number in the list. The base case: if values == []: return 0, since the total of nothing is zero, the neutral value again. The step: return values[0] + sum_list(values[1:]), which says the total is the first element plus the total of the rest, and the rest is a strictly shorter list, so the base case is reached after len(values) calls.

b) if len(values) == 1: return values[0], then the same step. It works on every non empty list and it BREAKS on the empty one: the recursion runs past the intended base case into a call on the empty list, where values[0] raises IndexError. Choosing the empty structure as the base case is almost always right, precisely because it is the smallest one the function can be handed, and it usually makes the base value the neutral element of the operation.

c) def count_char(text, c): if text == '': return 0, then return (1 if text[0] == c else 0) + count_char(text[1:], c). The sentence is the number of times c occurs in text; the base case is the empty string with the answer 0; the step counts the first character and trusts the call for the rest. Written with an explicit if instead of the conditional expression it is two branches, both of which must return.

d) The second: the call is made on the SAME list rather than on values[1:], so the problem never shrinks and the base case is never reached. RecursionError follows. It is the same failure as the factorial of the previous exercise wearing different clothes, and looking for the shrinking argument is the fastest way to find it: every recursive call must be handed something strictly smaller.

e) Induction proves a statement for every n by proving it for the smallest case and then proving that it holds for n whenever it holds for n - 1. A recursive function does the same thing in code: the base case is the first step of the proof, the recursive case is the second, and the assumption that the call returns the right answer is the induction hypothesis. That is why checking two lines is enough, and why unrolling the calls proves nothing beyond one particular argument.

a) Five: the calls on 4, 3, 2, 1 and 0 are all in progress at the moment the base case returns, since none of the outer calls can finish before the inner ones do. For a list of 100 numbers there are 101 frames, one per element plus the one for the empty list. The rule: the depth of the recursion IS the number of frames, and a function that recurses once per element of the data has a depth equal to the size of the data.

b) The limit is 1000 by default, and the exception is RecursionError, maximum recursion depth exceeded. It exists because the frames live on a stack of fixed size: without the limit, a runaway recursion would exhaust it and the interpreter would crash without a message. Python prefers to raise a clean exception naming the function, which is why the limit is a guard rail and not an arbitrary restriction. It can be raised with a call in the sys module, and raising it to survive a bug only postpones the crash.

c) It is not a tail call, and it would not help if it were. It is not one because the multiplication happens AFTER the call returns: the frame must stay alive to do it, so the call is not the last thing the function does. And Python does not eliminate tail calls even when they are genuine, deliberately, so that tracebacks keep every frame. A recursion in Python always costs its depth in stack, and that is a fact of the language rather than of the algorithm.

d) Each step copies the rest of the list: values[1:] on 100 elements builds a new list of 99, then 98, and so on, for about 5000 elements copied in total, which is quadratic in the length. The repair is to pass an INDEX rather than a slice, def sum_from(values, i) with the base case i == len(values), so that one single list is shared by every frame. The same reasoning applies to strings, where slicing copies just as eagerly.

e) Either rewrite it as a loop, which is always possible and usually short for a recursion that goes down one path, or raise the recursion limit and hope the stack holds. Defend the loop: it uses constant stack, it cannot hit a limit, and for a linear recursion like sum_list the loop is three lines. Raising the limit is for the rare case where the recursive shape really is the algorithm, a deep tree for instance, and even then the honest answer is to keep an explicit stack in a list and loop over it.

a) def reverse(text): if text == '': return '', then return reverse(text[1:]) + text[0]. On 'abc' the calls are reverse('abc'), then reverse('bc'), then reverse('c'), then reverse(''), which returns the empty string; the answers are then built on the way back up, 'c', then 'cb', then 'cba'. Note that the work happens AFTER the call returns, which is exactly why the frames have to stay alive.

b) def is_palindrome(text): if len(text) <= 1: return True, then return text[0] == text[-1] and is_palindrome(text[1:-1]). The two base cases hidden in that one condition are the empty string and the single character, and both are needed because the step removes TWO characters at a time: an even length string shrinks to the empty one and an odd length string shrinks to one character. A base case on the empty string alone would run past it and slice something that is already empty.

c) On a string of a million characters that is not a palindrome and differs at the second character, both stop almost at once, and the recursion still costs two frames and two slices of nearly a million characters each. On a string that IS a palindrome, the recursion needs half a million frames and dies with RecursionError long before finishing, while the loop walks it in a fraction of a second with no memory at all. The recursive version is the readable one for a first course and the loop is the one that runs.

d) text[0] + reverse(text[1:]) puts the first character in FRONT of the reversed rest, which rebuilds the string unchanged: on 'abc' it returns 'abc'. The first character of the original must end up LAST, so it goes after the recursive call, reverse(text[1:]) + text[0]. Both versions are legal, both terminate, and only one of them is the function asked for, which is why a single test on a two character string is worth writing.

e) def reverse_from(text, i): with the base case if i == len(text): return ''. The step is reverse_from(text, i + 1) + text[i]. It saves the copying: the slice version builds a new string at every level, about $n^2/2$ characters copied in all, while the index version shares one string between every frame and copies nothing. The frames are still there, so the depth limit is unchanged; only the quadratic copying goes away.

a) def digit_sum(n): if n < 10: return n, then return n % 10 + digit_sum(n // 10). On 1234: the units digit 4 plus digit_sum(123), which is 3 plus digit_sum(12), which is 2 plus digit_sum(1), which is the base case and returns 1. The total is $4 + 3 + 2 + 1 = 10$, in four calls, one per digit. The base case is n < 10 rather than n == 0 so that the last digit is returned rather than fetched by one more level, and both work.

b) def gcd(a, b): if b == 0: return a, then return gcd(b, a % b). On 48 and 18: $48 \bmod 18 = 12$, so gcd(18, 12); then $18 \bmod 12 = 6$, so gcd(12, 6); then $12 \bmod 6 = 0$, so gcd(6, 0), which is the base case and returns 6. The greatest common divisor of 48 and 18 is indeed 6.

c) Four calls, counting the first one and the base case. What shrinks is the SECOND argument: each step replaces b by a mod b, which is strictly smaller than b, so the sequence of second arguments strictly decreases and must reach zero. That is the whole termination argument, and it is worth stating in exactly those words, because the first argument does not decrease at all on the first step, which makes the function look as though it might not terminate.

d) The slow version: if n == 0: return 1, then return x * power(x, n - 1), which has depth $n$, so 1024 frames for $n = 1024$. The fast version: if n == 0: return 1, then half = power(x, n // 2), then return half * half if n is even, else x * half * half. Its depth is $\log_2 n$, so 11 frames for the same exponent, because each step halves the exponent instead of decreasing it by one. The variable half is not decoration: writing power(x, n // 2) * power(x, n // 2) calls the function twice and throws the saving away.

e) The digit sum and the slow power are clearly better as loops: both walk one path with a depth equal to the size of the input, and a loop does the same work with one frame. The fast power keeps its value as a recursion, since its shape, solve half the problem and combine, is exactly what a loop does not express naturally; the gcd sits in between, and its recursive form is so close to the mathematical rule that it is usually left as it is.

a) def search(values, target, lo, hi): if lo > hi: return -1, then mid = (lo + hi) // 2, then if values[mid] == target: return mid, then if values[mid] < target: return search(values, target, mid + 1, hi), else return search(values, target, lo, mid - 1). The two base cases are the empty interval, lo > hi, which means the value is absent, and the hit at the middle. Every recursive branch RETURNS the result of the call, which is the trap of exercise 1 d) in its most common disguise.

b) $(5 + 9) // 2 = 7$. The floor division is right because an index must be an integer and any consistent choice works: the interval of five values from 5 to 9 splits into two of two values each plus the middle one. Using round or a plain division would give a float, which the indexing refuses with TypeError. On a very large list, the safer form lo + (hi - lo) // 2 avoids an overflow in languages with fixed size integers, which Python does not have.

c) The interval stops shrinking and the function never ends. With hi = mid, the case lo == hi calls itself with the same pair for ever, since mid is then lo, and the same happens on the other side. The mid element has just been compared and is known not to be the target, so it must be EXCLUDED: mid + 1 on one side and mid - 1 on the other. That off by one is the whole difficulty of binary search, and it is the reason the empty interval test is written lo > hi rather than lo == hi.

d) Each call copies half of the remaining list, so the copying costs as much as scanning the list once, which cancels the very advantage the algorithm was chosen for. The caller also loses the INDEX: a search on a slice can only return a position inside that slice, so the answer has to be corrected by the offset at every level, and that correction is one more thing to get wrong. Indices are the right interface for anything that searches or sorts in place.

e) Ten steps for a thousand values, since $2^{10} = 1024$, and twenty for a million, since $2^{20}$ is just over a million. The rule is that each step halves the interval, so the number of steps is $\log_2 n$ rounded up. The comparison that makes the point: a linear scan of a million values does half a million comparisons on average, the binary search does twenty.

a) To move n disks from the source to the target, move the top n - 1 to the spare peg, move the largest disk to the target, then move the n - 1 back on top of it. In code: def move(n, source, target, spare): if n == 0: return, then move(n - 1, source, spare, target), then print('move a disk from', source, 'to', target), then move(n - 1, spare, target, source). Three lines, and no attempt to work out what the moves actually are.

b) The base case is n == 0, where the function returns without printing anything, since moving zero disks needs no move. Using n == 1 as the base case and printing one move there also works and duplicates the printing line. The empty case is the better base case here for the same reason as the empty list in exercise 2.

c) One disk needs 1 move, two need 3, three need 7 and five need 31. The formula is $2^n - 1$, and it comes straight out of the recursion: if $M(n)$ is the number of moves, the three lines give $M(n) = 2M(n-1) + 1$ with $M(0) = 0$, and that recurrence has $2^n - 1$ as its solution. Checking it on $n = 3$, $2 \times 3 + 1 = 7$, is enough for an examination answer.

d) Sixty four disks need $2^{64} - 1$ moves, more than eighteen billion billion, so the program prints for longer than the age of the universe at any rate a computer can print. The difference with the naive Fibonacci is worth naming: Fibonacci is slow because it recomputes the SAME subproblems again and again, and memoisation fixes it; Hanoi computes each move exactly once, and there are simply that many moves. No technique can help, because the output itself is exponential.

e) Because the roles change at every level: in the first recursive call the target peg becomes the spare, and in the second the source becomes the spare. Fixing the names would make the function work only from A to C at the top level and produce nonsense underneath. Passing the three roles as parameters is what lets the same function describe every subproblem, and it is the clearest small example of why a recursive function takes its context as arguments rather than reading it from outside.

a) False. It stops, with RecursionError, after about a thousand calls, because each call keeps a frame alive and the stack is finite. The counterexample: def f(n): return f(n - 1), called with 5, raises after roughly a thousand frames rather than running for ever. Correct version: an infinite LOOP runs for ever, an infinite RECURSION exhausts the stack and reports itself, which is why the second is easier to diagnose.

b) False as a rule. A recursion carries the cost of its frames, so a linear recursion is indeed slower than the equivalent loop, but the comparison is between algorithms and not between shapes: the recursive fast power of exercise 5 does eleven multiplications where a loop over the exponent does 1024. The counterexample is that pair. Correct version: prefer a loop when the recursion walks one path of the same depth as the data, and keep the recursion when the problem splits, or when the structure itself is nested.

c) False, and it is the most frequent recursion bug there is. The counterexample: def total(values): if values == []: return 0, then values[0] + total(values[1:]) with no return, called on [1, 2], gives None and then raises TypeError. Correct version: every branch of a recursive function must return, since a Python function that reaches the end of a branch returns None whatever the other branches do.

d) False. Decreasing by one gives a depth equal to n; halving gives a depth of $\log_2 n$. The counterexample: on $n = 1024$, one needs 1024 frames and the other 11. Correct version: the depth is the number of steps needed to reach the base case, and dividing gets there logarithmically while subtracting gets there linearly. That is the same difference as between a linear scan and a binary search.

e) False. Memoisation helps exactly when the SAME subproblem is solved more than once, which is the case for Fibonacci and not for the towers of Hanoi, where every call has different arguments and every move is printed once. The counterexample: memoising the Hanoi function saves nothing, because $2^n - 1$ moves really have to be made. Correct version: memoisation removes repeated work; it cannot remove work that is genuinely required.

a) def deep_sum(item): if isinstance(item, list): return sum([deep_sum(x) for x in item]), else return item. The test that separates the two cases is isinstance(item, list), and it is what makes the function work at every level: a list is handled by summing the results on its elements, a number is returned as it is. The base case here is not an empty structure but a LEAF, which is the shape every recursion on a tree takes.

b) The structure is [1, [2, [3, 4]], 5]. Its elements give 1, then deep_sum on [2, [3, 4]], then 5. That middle call gives 2 plus deep_sum on [3, 4], which is $3 + 4 = 7$, so the middle call returns 9. The total is $1 + 9 + 5 = 15$. Note that the answer is simply the sum of every number that appears, which is the sentence the function was written from.

c) A single for loop reaches the elements of the outer list only, so it would try to add the list [2, [3, 4]] to a number and raise TypeError. Two nested loops reach two levels and fail on the third, three reach three and fail on the fourth. The number of loops needed is the depth of the data, which is not known when the program is written, and that is exactly the situation recursion exists for: the function calls itself as many times as the data is deep, and nobody has to know that number in advance.

d) def deep_count(item): if isinstance(item, list): return sum([deep_count(x) for x in item]), else return 1, which gives 5 on the figure. def deep_depth(item): if not isinstance(item, list): return 0, then if item == []: return 1, then return 1 + max([deep_depth(x) for x in item]), which gives 3 on the figure. The three functions differ only in what they do at a leaf and in how they combine, which is the sign of a well chosen shape.

e) The leaf is a FILE and the branch is a DIRECTORY, which contains files and other directories, to an unknown depth. The base case becomes it is a file, answered with its size or with 1, and the recursive case walks the entries of the directory and combines. That is how a disk usage tool is written, and it is the same seven lines as deep_sum.

a) def fib(n, memo): if n in memo: return memo[n], then if n < 2: return n, then memo[n] = fib(n - 1, memo) + fib(n - 2, memo), then return memo[n]. The lookup goes FIRST, before the base case even, so that a remembered answer costs nothing; the store goes on the way back up, immediately before the return. Putting the lookup after the recursive calls would remember everything and save nothing.

b) Because a default value is evaluated once, at definition time, so one single dictionary would be shared by every call of the program, as the functions set showed with the list. Here the effect is subtle rather than fatal, since the remembered values stay correct, but the function then keeps a growing hidden state between unrelated calls, and it is no longer testable in isolation. The clean forms are to pass the dictionary in, or to write memo=None and create it inside.

c) The naive version recomputes: the call tree for n has $2F(n+1) - 1$ nodes, and with $F(31) = 1346269$ that is 2692537 calls. The memoised one computes each of the arguments from 0 to 30 exactly once and looks the rest up: there are $2n - 1$ calls, that is 59 for $n = 30$, because each of the 30 computed values makes two calls of which one is a lookup. The lesson: the tree has not changed shape, it has been cut down to a path plus its lookups.

d) prev, cur = 0, 1, then for k in range(n - 1): prev, cur = cur, prev + cur, then cur. It costs n additions, no dictionary, no frames and constant memory, so it beats the memoised recursion on every count. That is the honest conclusion of the chapter: Fibonacci is a linear problem, and the recursion is a teaching device rather than the right tool. Memoisation earns its place where the subproblems overlap in a way a loop cannot enumerate easily.

e) Hanoi, no: every call has different arguments, nothing repeats, and the $2^n - 1$ moves are the answer itself. Binary search, no: each call halves the interval and no interval is ever visited twice. Deep sum, no: every element of the structure is visited exactly once, and there is nothing to remember. The test to apply, in one sentence, is whether the same arguments reach the function more than once, and that is a property of the problem rather than of the code.