Strategy: split the problem, then trust the smaller call (free preview) | StemPy Lab
Free previewCourse: Standard
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.
This is the first lesson of Recursion: Puzzle Workshop, free for everyone to read.
What you will be able to do
After this lesson you can
use the four questions to design a recursive function,
trust the smaller call and check only one step,
write a recursive function on a list, and
solve the Tower of Hanoi, and say how many moves it needs.
The hardest step is to trust
You know what a recursive function is. The hard part is to write one. Many learners try to follow every call in their head, and they get lost, like a person who tries to count every doll inside a set of Russian dolls at once. Good programmers do something else: they trust the smaller call. They say, "Suppose that the function already works for a smaller problem. What is the one step that I add?"
This is how mathematicians prove things too: if it is true for the smallest case, and true for n whenever it is true for n−1, then it is true for all n.
The four questions
Ask them in this order. Write the answers before you write any code.
What is the smaller problem? For a list, it is the list without its first item. For a number, it is n−1 or n÷2.
What is the base case? The smallest problem, with an answer that you know.
What do I do with the answer of the smaller problem? This is the one new step.
Does every call get closer to the base case? If not, the calls never stop.
Example: the biggest item
Let us find the biggest number in a list. Ask the four questions.
The smaller problem: the rest of the list, items[1:].
The base case: a list of one item. Its biggest item is itself.
The step: compare the first item with the biggest of the rest.
Closer? Each call has a list that is one item shorter, so yes.
Predict first, then run it. We trust that biggest(items[1:]) gives the biggest of the rest. Then there is only one thing to do: is the first item bigger than that? The first list gives 9. A list of one item gives that item, 5. A list of negative numbers gives −1, the biggest of them.
Check one step by hand, for a small list. For [3, 9]: rest is biggest([9]), which is 9 (the base case). Then 3 is not more than 9, so the answer is 9. Right. If the base case is right, and the step is right, you do not need to check any more.
When the base case does not fit
The lesson: make sure that every possible input reaches the base case. Think of the smallest input, and the strange ones.
Splitting in two
Sometimes the smaller problem needs two calls. The Tower of Hanoi is the famous example. There are three pegs, A, B and C, and n discs on peg A, the biggest at the bottom. You must move the whole tower to peg C. You move one disc at a time, and you never put a bigger disc on a smaller one.
A dark code panel with a recursive function countdown of n. If n equals 0, it prints Go and stops: this is the base case, a problem so small that the answer is known, which stops the calls. Otherwise it prints n and calls countdown of n minus 1: this is the recursive case, where the function calls itself on a smaller problem. A note says that countdown of 3 shows 3, 2, 1 and Go, and that each call is one step closer to the base case.
Ask the four questions.
The smaller problem: a tower of n−1 discs.
The base case: 0 discs, and there is nothing to move.
The new step: move the biggest disc.
The plan: move the n−1 discs out of the way (to B), move the big disc (to C), then move the n−1 discs on top of it.
We do not know how the small tower is moved, and we do not need to. We trust that the call does it.
How many moves?
The function never lists the moves. It only trusts that the smaller tower can be moved, and counts.
Mistakes to avoid
Following every call in your head. Trust the smaller call and check only one step.
A base case that does not fit. The base case of biggest is one item. An empty list never reaches it, so the calls never stop.
A smaller problem that is not smaller.biggest(items) calling itself with the same list never stops.
Forgetting to use the answer. A call that is not returned is lost.
Mixing up the pegs in Hanoi. Say the three lines of the function aloud.
Practice
Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.
Then the labs and the problems:
Warm-up. Open the problem The biggest in a list and the problem A base case that is missing.
Build. Open the lab The biggest, recursively. You write the function, and the checker tries it on many lists.
Stretch. Open the lab The Tower of Hanoi and the problem How long does the legend take?
Remember these
Four questions: the smaller problem, the base case, the new step, and getting closer.
Trust the smaller call. Check only one step.
Two calls in one function are fine: the Tower of Hanoi needs 2n−1 moves.
Make sure that every input reaches the base case.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
What is the smaller problem when you add up the items of a list?
How many moves does the Tower of Hanoi need for 4 discs?
A function calls itself with the same list. What happens?
Liked this lesson? There is more
Recursion: Puzzle Workshop is a Standard course. It adds 4 more lessons, practice and tests on top of the free chapter.
13Problems6Python Labs1Question Set1Mock Test
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.
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.
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.
Project: the puzzle book: In this project we make a puzzle book: a small set of recursive functions, each with a clear job, and a table of tests that runs all of them and shows PASS or FAIL. The functions find the biggest item of a list, write a number in binary, find the gcd, flatten a list of lists, and count the subsets of a list. We plan the table of expected answers first, build the functions with the four questions, run the tests, and extend the book with a puzzle of our own. The project shows that a recursive function is as easy to test as any other, and that a table of tests is the best friend of a puzzle.