Our final example is the well known Hanoi Towers puzzle.

In this puzzle, we're given three sticks.

Two of them are initially empty.

On the first stick, we have n discs,

sorted by size as shown here on the slide.

Our goal is to move all n discs to some other stick,

to one of the two empty sticks.

This would be easy if not given two constraints.

First of all, we are allowed to move only one disc at a time, and naturally we need

to take the top most disc from one stick, and to put it to some other stick, right?

And also we are not allowed to put a larger disc onto a smaller disc, okay?

So the question is whether it is possible for, and if it is possible,

then for which values of n this is possible, okay?

So it is known to be possible for every value of n.

At the same time, it is not clear at this point how can we be sure

that it is possible for every possible value of n.

We can check that it is possible for one, for two, for three, for four, and so on.

But it is not so clear how to ensure that just for

every even very huge number, it is always possible.

And of course, we are going to use recursion again

to show how to do this for every possible value of n.

For this, we will first explain that it is possible when n is equal to 1,

and then we will show that if it is possible for n minus 1, for example,

then it is possible for n.

This will ensure that, if it is possible for one, then it is possible for two.

If it is possible for two, then it is possible for three.

If it is possible for three, then it is possible for four, and so on.

So our goal is basically to show that it is possible in the beginning,

when n is equal to 1.

And then we need to show some generic procedure of building a solution for

n discs using a recursive solution for n minus 1 discs, okay?

So let's start.

So the simplest possible case is indeed when there is just one disc.

So in this case, n is equal to 1, and

our goal is to move this disc to some other place, to some other stick,

and of course it is very easy to do this so we just move it to another stick.

Now let's also consider two discs just to get a feeling of how

to solve this problem.

Now in this case, we first move the smallest disc.

So we move it to this stick, then we move the larger disc to another stick.

And finally, we move the smaller one onto larger one, right?

So for two discs, it is also possible.

Now let's consider a general case, where we have n discs.

And let's focus on the larger discs, on the large disc, I'm sorry.

So what is the condition under which we can move it?

So first of all, if we are moving the large disc,

this actually means that all the remaining n minus 1

discs are already on some other stick.

So probably a part of them are on one disc, and

all the remaining of them on the third stick.

I'm sorry.

So if we are moving this large disc, so for which stick we can move it?

So I'm claiming that the only stick for

which we can move it is the empty stick, right?

Because if there are any discs on this stick then we will be allayed the rules.

If there is at least one stick, at least one disc, I'm sorry, on this stick then by

moving the largest disc to this stick, we will put a larger disc onto a smaller one.

So this means that when we are moving the largest disc,

we should move it to an empty stick.

Which in turn means that all the other discs at this point

should be put to the same stick.

And since we know that all the discs are always in increasing order,

we know that at this point, all the other discs should be located as follows, right?

So when we are moving the large disc,