Standard content

A monk moves a tower of discs, one at a time, and the legend says the world ends when he is done. How many moves is that? Why is the simple Fibonacci function so slow, and how does a dictionary fix it? In this workshop you learn a way to think recursively with four questions, solve puzzles on lists, numbers and towers, keep a memory of answers, learn the limits of recursion and when to use a loop, and meet puzzles where every step has a choice, such as all the subsets of a set and all the arrangements of letters. A puzzle book of tested functions is the project at the end, and a timed test follows. The practice runs your functions on many inputs and tells you which ones fail.

What's inside

1. Strategy: split the problem, then trust the smaller call: Recursion is easier when you trust the smaller call and do not follow every call in your head. Four questions help, and you answer them before you write any code: what is the smaller problem, what is the base case, what do I do with the answer of the smaller problem, and does every call get closer to the base case. The biggest item of a list is the first item compared with the biggest of the rest. The Tower of Hanoi needs two calls in one function: move the smaller tower out of the way, move the biggest disc, and move the smaller tower back on top. The number of moves follows M of n equals 2 times M of n minus 1, plus 1, which gives 2 to the power n, minus 1.
2. Remembering answers with a dictionary: The simple Fibonacci function works out the same values again and again, so its calls grow like 1.6 to the power n: about 2.7 million calls for n equal to 30. The fix is a memory: a dictionary outside the function keeps each answer that is worked out, and the function looks there first. This idea is called memoisation, and it brings the calls down to about 2n. The function lru_cache from functools does it for you. A memory helps when the same smaller problem comes again and again, and does not help when each smaller problem comes once. It must not be used for a function whose answer can change for the same input.
3. Recursion or a loop? Depth and limits: Python allows about a thousand nested calls, and a deeper recursion stops with a RecursionError, which can be caught with try and except. A loop has no such limit and uses less memory, so a very deep or simple repeat is better as a loop. Many recursive functions have a loop version, such as the binary form of a number, which builds the answer from the remainders of repeated division by 2, and Euclid's gcd. A recursion is the clearer choice when the problem is made of smaller copies of itself, such as folders in folders or the subsets of a set. A recursive function can be changed into a loop by keeping the changing values in variables.
4. Puzzles with choices: subsets and arrangements: Some puzzles have a choice at every step. The subsets of a list are found by asking, for the first item, whether it is in or out: the subsets of the rest, and the same subsets with the first item added. A list of n items has 2 to the power n subsets. The arrangements of a text are found by choosing the first letter in every possible way and arranging the rest, and n letters have n factorial arrangements. These puzzles grow very fast, so they are only for small inputs. A recursive function that tries every choice and collects the results is a first look at a method called backtracking. A list inside a list to any depth is also solved by recursion, by flattening each inner list.