Note: Click on "Kernel" > "Restart Kernel and Run All" in JupyterLab after finishing the exercises to ensure that your solution runs top to bottom without any errors. If you cannot run this file on your machine, you may want to open it in the cloud .

Chapter 4: Recursion & Looping (Coding Exercises)¶

The exercises below assume that you have read the first part of Chapter 4.

The ...'s in the code cells indicate where you need to fill in code snippets. The number of ...'s within a code cell give you a rough idea of how many lines of code are needed to solve the task. You should not need to create any additional code cells for your final solution. However, you may want to use temporary code cells to try out some ideas.

Towers of Hanoi¶

A popular example of a problem that is solved by recursion art the Towers of Hanoi .

In its basic version, a tower consisting of, for example, four disks with increasing radii, is placed on the left-most of three adjacent spots. In the following, we refer to the number of disks as $n$, so here $n = 4$.

The task is to move the entire tower to the right-most spot whereby two rules must be obeyed:

1. Disks can only be moved individually, and
2. a disk with a larger radius must never be placed on a disk with a smaller one.

Although the Towers of Hanoi are a classic example, introduced by the mathematician Édouard Lucas already in 1883, it is still actively researched as this scholarly article published in January 2019 shows.

Despite being so easy to formulate, the game is quite hard to solve.

Below is an interactive illustration of the solution with the minimal number of moves for $n = 4$.

Watch the following video by MIT's professor Richard Larson for a comprehensive introduction.

The MIT Blossoms Initiative is primarily aimed at high school students and does not have any prerequisites.

The video consists of three segments, the last of which is not necessary to have watched to solve the tasks below. So, watch the video until 37:55.

Video Review Questions¶

Q1: Explain for the $n = 3$ case why it can be solved as a recursion!

< your answer >

Q2: How does the number of minimal moves needed to solve a problem with three spots and $n$ disks grow as a function of $n$? How does this relate to the answer to Q1?

< your answer >

Q3: The Towers of Hanoi problem is of exponential growth. What does that mean? What does that imply for large $n$?

< your answer >

Q4: The video introduces the recursive relationship $Sol(4, 1, 3) = Sol(3, 1, 2) ~ \bigoplus ~ Sol(1, 1, 3) ~ \bigoplus ~ Sol(3, 2, 3)$. The $\bigoplus$ is to be interpreted as some sort of "plus" operation. How does this "plus" operation work? How does this way of expressing the problem relate to the answer to Q1?

< your answer >

Naive Translation to Python¶

As most likely the first couple of tries will result in semantic errors, it is advisable to have some sort of visualization tool for the program's output: For example, an online version of the game can be found here.

Let's first generalize the mathematical relationship from above and then introduce the variable names used in our sol() implementation below.

Unsurprisingly, the recursive relationship in the video may be generalized into:

$Sol(n, o, d) = Sol(n-1, o, i) ~ \bigoplus ~ Sol(1, o, d) ~ \bigoplus ~ Sol(n-1, i, d)$

$Sol(\cdot)$ takes three "arguments" $n$, $o$, and $d$ and is defined with three references to itself that take modified versions of $n$, $o$, and $d$ in different orders. The middle reference, Sol(1, o, d), constitutes the "end" of the recursive definition: It is the problem of solving Towers of Hanoi for a "tower" of only one disk.

While the first "argument" of $Sol(\cdot)$ is a number that we refer to as n_disks below, the second and third "arguments" are merely labels for the spots, and we refer to the roles they take in a given problem as origin and destination below. Instead of labeling individual spots with the numbers 1, 2, and 3 as in the video, we may also call them "left", "center", and "right". Both ways are equally correct! So, only the first "argument" of $Sol(\cdot)$ is really a number!

As an example, the notation $Sol(4, 1, 3)$ from above can then be "translated" into Python as either the function call sol(4, 1, 3) or sol(4, "left", "right"). This describes the problem of moving a tower consisting of n_disks=4 disks from either the origin=1 spot to the destination=3 spot or from the origin="left" spot to the destination="right" spot.

To adhere to the rules, an intermediate spot $i$ is needed. In sol() below, this is a temporary variable within a function call and not a parameter of the function itself.

In summary, to move a tower consisting of n_disks (= $n$) disks from an origin (= $o$) to a destination (= $d$), three steps must be executed:

1. Move the tower's topmost n_disks - 1 (= $n - 1$) disks from the origin (= $o$) to an intermediate (= $i$) spot (= Sub-Problem 1),
2. move the remaining and largest disk from the origin (= $o$) to the destination (= $d$), and
3. move the n_disks - 1 (= $n - 1$) disks from the intermediate (= $i$) spot to the destination (= $d$) spot (= Sub-Problem 2).

The two sub-problems themselves are solved via the same recursive logic.

Write your answers to Q5 to Q7 into the skeleton of sol() below.

sol() takes three arguments n_disks, origin, and destination that mirror $n$, $o$, and $d$ above.

For now, assume that all arguments to sol() are int objects! We generalize this into real labels further below in the hanoi() function.

Once completed, sol() should print out all the moves in the correct order. For example, print "1 -> 3" to mean "Move the top-most n_disks - 1 disks from spot 1 to spot 3."

Q5: What is the n_disks argument when the function reaches its base case? Check for the base case with a simple if statement and return from the function using the early exit pattern!

Hint: The base case in the Python implementation may be slightly different than the one shown in the generalized mathematical relationship above!

Q6: If not in the base case, sol() determines the intermediate spot given concrete origin and destination arguments. For example, if called with origin=1 and destination=2, intermediate must be 3.

Add one compound if statement to sol() that has a branch for every possible origin-destination-pair that assigns the correct temporary spot to a variable intermediate.

Hint: How many 2-tuples of 3 elements can there be if the order matters?

Q7: sol() calls itself two more times with the correct 2-tuples chosen from the three available spots origin, intermediate, and destination.

In between the two recursive function calls, use print() to print out from where to where the "remaining and largest" disk has to be moved!

Q8: Execute the code cells below and confirm that the moves are correct!

Pythonic Refactoring¶

The previous sol() implementation does the job, but the conditional statement is unnecessarily tedious.

Let's create a concise hanoi() function that, in addition to a positional n_disks argument, takes three keyword-only arguments origin, intermediate, and destination with default values "left", "center", and "right".

Write your answers to Q9 and Q10 into the subsequent code cell and finalize hanoi()!

Q9: Copy the base case from sol()!

Q10: Instead of conditional logic, hanoi() calls itself two times with the three arguments origin, intermediate, and destination passed on in a different order.

Figure out how the arguments are passed on in the two recursive hanoi() calls and finish hanoi().

Hint: Do not forget to use print() to print out the moves!

Q11: Execute the code cells below and confirm that the moves are correct!

We could, of course, also use numeric labels for the three steps like so.

Passing a Value "down" the Recursion Tree¶

The above hanoi() prints the optimal solution's moves in the correct order but fails to label each move with an order number. This is built in the hanoi_ordered() function below by passing on a "private" _offset argument "down" the recursion tree. The leading underscore _ in the parameter name indicates that it is not to be used by the caller of the function. That is also why the parameter is not mentioned in the docstring.

Write your answers to Q12 and Q13 into the subsequent code cell and finalize hanoi_ordered()! As the logic gets a bit "involved," hanoi_ordered() below is almost finished.

Q12: Copy the base case from the original hanoi()!

Q13: Complete the two recursive function calls with the same arguments as in hanoi()! Do not change the already filled in offset arguments!

Then, adjust the use of print() from above to print out the moves with their order number!

Q14: Execute the code cells below and confirm that the order numbers are correct!

Lastly, it is to be mentioned that for problem instances with a small n_disks argument, it is easier to collect all the moves first in a list object and then add the order number with the enumerate() built-in.

Open Question¶

Q15: Conducting your own research on the internet, what can you say about generalizing the Towers of Hanoi problem to a setting with more than three landing spots?

< your answer >