Exam practice

• Recursion: solving a problem by solving smaller copies of the same problem. Example: the people ahead of you in a queue are 1 + the people ahead of the person in front.
• Recursive function: a function that calls itself. Example: factorial, which calls factorial(n - 1).
• Base case: the smallest copy, answered without calling the function again; it stops the recursion. Example: if n == 0: return 1 in factorial.
• Recursive case: the rule that builds the answer from a smaller copy. Example: return n * factorial(n - 1).
• Call stack: the pile of calls that have started and not finished, newest on top, each waiting for the call it made; the last call made finishes first. Example: factorial(4), (3), (2), (1) waiting while factorial(0) runs.

• i.Base case: the sum from 1 to 0 is 0 (or the sum from 1 to 1 is 1). Recursive case: the sum from 1 to n is n + the sum from 1 to n − 1.
• ii.Base case: a number less than 10 has 1 digit. Recursive case: otherwise, the digits of the number are 1 + the digits of the number with its last digit taken off (n // 10).
• iii.Base case: x⁰ = 1. Recursive case: xⁿ = x × xⁿ⁻¹.

The calls are made top to bottom and give back bottom to top: 2, then 2, then 10, then 13. The function adds up the digits of a number: 2 + 0 + 8 + 3 = 13. n % 10 is the last digit, and n // 10 the number without it.

def power(x, n):    if n == 0:        return 1    return x * power(x, n - 1) print(power(2, 10), power(3, 4))

1024 81

power(2, 10) calls power(2, 9), and so on down to power(2, 0): 11 calls in all, each multiplying by 2 on the way back.

It prints 5, 4, 3, 2, 1, then “Go!”, then 0, −1, −2, … until about a thousand calls are open and Python stops it with a RecursionError. The base case prints “Go!” but doesn’t stop: there is no return, so the call goes on to print 0 and call countdown(−1), and n never reaches 0 again. The fix is to return in the base case:

def countdown(n):    if n == 0:        print("Go!")        return    print(n)    countdown(n - 1) countdown(5)

54321Go!

To move the biggest disk from A to C, all the other disks must be out of the way on B. So: (1) move the top n − 1 disks from A to B, using C as the spare peg; (2) move the biggest disk from A to C; (3) move the n − 1 disks from B onto it on C, using A as the spare. Steps 1 and 3 are the same puzzle with one disk fewer, solved the same way; the base case is 0 disks, which need no moves.

Moves: M(n) = M(n − 1) + 1 + M(n − 1) = 2M(n − 1) + 1, with M(0) = 0. This gives 1, 3, 7, 15, …, one less than a power of 2: if M(n − 1) = 2ⁿ⁻¹ − 1, then M(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1.

For 12 disks: 2¹² − 1 = 4096 − 1 = 4,095 moves.

Coloring first marks the square as done. When a neighbor’s fill looks back at this square, it finds the new color, not the old one, and stops (a base case). If the coloring came after the calls, the square would still have the old color while its neighbors were being filled: the square above would fill back down into it, which would fill back up, and so on, two calls asking each other for ever, until the recursion limit stops the program with a RecursionError.

family = {    "Hari": ["Sita", "Ram"],    "Sita": ["Asha"],    "Ram": ["Bina", "Kiran", "Dipak"],    "Asha": [],    "Bina": [],    "Kiran": ["Maya"],    "Dipak": [],    "Maya": [],} def descendants(name):    count = 0    for child in family[name]:        count = count + 1 + descendants(child)    return count print(descendants("Hari"), descendants("Ram"))

7 4

Hari has 7 descendants: Sita, Ram, Asha, Bina, Kiran, Dipak and Maya. Each child counts 1, plus that child’s own descendants. The base case is a person with no children: the loop doesn’t run, and the function gives back 0, as size did for a folder with no folders inside.

Each call makes two more calls, so the calls form a tree that branches at almost every call, and the same small questions are worked out again and again in different branches: ways(38) twice, ways(37) three times, and so on. Nothing remembers an answer once it is given back. ways(40) makes 331,160,281 calls for only 41 different questions.

Two fixes: (1) a loop that works upwards from ways(0) and ways(1), keeping only the last two answers, 39 times round the loop; (2) keep the recursion but remember each answer the first time it is worked out (in a dictionary), and look it up next time instead of working it out again; that is dynamic programming (Grade 12).

Alike: both color exactly the same squares, stop at the same places (the edge, an outline, a square already colored), and color them in the same order, depth first: the newest square first.

Different: the recursive version keeps its waiting work as open calls, one per square on its current path; the loop keeps it as a list of squares still to do, used as a stack (append and pop from the same end).

For a photo editor: the loop. An area of a photo can have millions of pixels, so the recursive version would need far more open calls than Python’s recursion limit (about 1,000) allows and would stop with a RecursionError, while a list can grow as long as the computer’s memory allows.

• i.31 calls. The call for 16 makes 2 calls for 8, which make 4 for 4, then 8 for 2, then 16 for 1: 1 + 2 + 4 + 8 + 16 = 31.
• ii.16 base cases, one for each number: the calls for lists of 1 item. (The other 15 calls each merge two halves.)
• iii.5 calls: one at each level, for 16, 8, 4, 2 and 1 items, all open while the first single item is being given back. That is log₂ 16 + 1 = 5; merge sort’s depth grows only with log₂ n, so even a million items need only about 21 open calls.