Hanoi

Á gentle introduction to recursion. Plus how to solve the Hanoi's Tower problem.

Hi Friends,

Welcome to the 47th edition of the Polymathic Engineer newsletter. This week, we will talk about recursion.

Recursion is one of the strangest concepts to grasp while learning algorithms, and I know many people who still struggle to fully understand it.

First we will look at recursion from a beginner’s point of view. Then we will see a great example of how recursion can simplify the way solve problems.

The outline will be as follows:

• What is recursion

• How to apply recursion to solve the Hanoi’s Tower problem

• Interesting Tweets

Recursion

Recursion is the process of defining a problem in terms of itself, and it is a powerful tool in designing algorithms.

Consider the problem of counting the odd values in an array of integers A. Defining this problem as P(A[0,..,n]), we can write that:

• P(A[0,.,n]) = P(A[1,.,n]) + 1 if A[0] is odd 

• P(A[1,.,n]) = P(A[2,.,n]) + 1 if A[1] is odd 

• ...

• P(A[n]) = 1 if A[n] is odd 

The example shows that counting the odd values in an array can be defined as counting the odd values in a smaller array.

Understanding such a process is critical to write a recursive function that calls itself to solve a recursive problem.

Every recursive solution to a problem can be written as a function calling itself. Every recursive function is composed of two parts:

• Base case: compute an output value without making any subsequent recursive calls. This is done for one or more input values for which the function is evaluated without recursion. In the example, the base case is when the index i exceeds the array size and the function returns 0.

• Reduction step: relate the output value of the function at one (or more) input values to the value of the function at one (or more) other input values. In the example, the count of odd values in A[i,...,n] is related to that in A[i+1,...,n].

The sequence of inputs in the reduction steps must always converge to the base case. In the example, the index increases by 1 at each step and converges to the size of the array.

A recursive algorithm works because the computer holds the computation done in every reduction step on the function stack frame. So, the space complexity is usually proportional to the number of reduction steps plus any non-constant space used during every step. The time complexity is instead dependent on the number of calls executed at each step.

Hanoi’s Tower

The Tower of Hanoi is a famous mathematical puzzle, and it is ideal to show how powerful recursion to solve certain problems.

The problem consists of 3 pegs A, B and C, and n disks of different sizes.

At the beginning, all disks are placed on peg A. They are sorted from top to bottom for decreasing size and labeled from 1 to n.

The goal is to move all the disks from peg A to peg B following 2 rules:

• you can move only one disk at a time

• you can't move a disk over a smaller one

The problem looks intimidating, so starting with the simplest scenarios is worth it.

With only one disk, you can move the disk from A to B according to the rules.

With two disks, we you solve it in 3 steps:

• move disk 1 from A to C

• move disk 2 from A to B

• move disk 1 from C to B

What's about using 3 disks?

Since you already know how to move 2 disks, you can:

• move the upper 2 disks (1,2) to peg C

• move disk 3 to peg B

• move disk (1,2) from peg C to B

The analysis gives a generalized approach for n disks:

• move the upper n-1 disks to an intermediate peg using the destination peg

• move the bottom disk to the destination peg

• move the n-1 disks from the intermediate to the destination peg using the source peg

The first and last steps are the same instance of the original problem and can be solved using recursion. Two recursive calls decrease the number of remaining disks by 1. The recursion stops when you hit the base case with only one disk.

Here is an implementation of the algorithm in Python:

The time complexity of the algorithm is O(2ⁿ) where n is the number of disks. This is because at each step there are 2 recursive calls and the maximum depth of the recursion is n. The space complexity is O(n) since a maximum of n function calls are stored on the call stack.

For paid subscribers

I completed the first issue dedicated to Apache Cassandra and I’ll send to you all next week. Here is the outline to whet the appetite :)

Interesting Tweets

The first time I broke production, I've been blamed for that despite being able to fix it alone. But the problem was that there was no mechanism to avoid what I did, not me. It is critical to conduct blameless post mortems in order to determine why this occurred. And the subsequent process enhancements should help to avoid such problems in the future.

The most important part of my end-of-day routine is deciding which will be the first task I will do the next day. It gives me peace of mind in the evening and energy in the following day.

Coding skills are the prerequisite to be a successful developer. But if you want to make a real difference, you need to know why the code you write is important for the business. This will also help you write the easiest code that meets the needs.

A stack trace is like a pirate map representing the path to a treasure. It shows you the exact steps your code did up to the point where an exception has been raised.