The last recursive example we're going to look at is the Tower of Hanoi.
And you may or may not be familiar with this, but this is a game where you have three stands.
This is stand, we'll say l four left center and right.
And what this game is, is you want to get all the disk from stand l all the way over to stand R And
there are a couple of rules you can only move.
One disk at a time.
And a larger disk.
Cannot.
Sit on a smaller.
Disk.
Right.
So we have two rules here.
So what we want to do is get one, two, three, four in this order all the way over to one, two,
three, four.
Over here.
So we quite literally want to replicate it to three.
And then four.
Right.
So we want right to eventually become left.
So for us to do this, we can start over here.
And we can say that this is block in.
Right.
And then we also have so this is left center.
And.
Right.
So these are always going to be in minus one because once we get this in over here.
Now the block above it becomes in.
So step one for us is going to be get these three blocks right here into the center, right, because
this is a a helper stand for us.
So we want to get these three blocks to the center.
And now when we have those three blocks in the center, we're going to take our in and plop it over
here.
And that's always going to be step two.
Take this in block and bring it over here, because now that is our biggest block and we now have it
over here.
And so now that we have these three blocks over here from our first step.
We now have to get all of the N minus one blocks over here, and that is step three.
So what you're seeing is a little bit of a pattern of in minus one.
This account is one and then in minus one again, Right.
So what our function is going to try to do is count how many steps it takes to get these blocks from
the left to the right.
Well, so we can have our function and we see that we have n minus one steps.
So now we can do our recursive call of the function of n minus one.
And then we know we always have one for sure step right here at step two, because this end block is
going to go all the way over to the right.
And then we also see that we have in minus one from the center.
So we can say F in of N minus one from here.
And simply put, this right here is going from left to center.
This right here is step two.
And then this right here is going from center.
To the right.
Right.
So step three.
So step three, Step two and step one.
So these two.
Calls are going to be our recursive function calls.
So now we have a general idea of how this needs to look, and we can implement this recursively using
the function return value that we have established right here.
So if we come over and I created a function called TIO for Tower of Hanoi, we're going to have a number.
And this is going to be how many blocks we contain, and then we're going to return an integer of type
32 because we want to see how many steps it took to get from the left stand all the way to the right.
So our base case is if N is equal to zero, then we want to return zero because there is nothing for
us to do.
Otherwise we're going to return that.
Formula that we found where it is.
N minus one for step one, plus one for step two, and then in minus one, again for step three.
And now we can come down here and we can print out a couple of tower of
inputs for.
So again, we want to test out zero and we expect zero to be returned.
We'll test out one and we expect one to be returned.
We'll test out two and we would expect two to be returned.
And then we'll test out three and see what gets returned there.
And then lastly, we'll also test out for.
And we see we have zero one, three, seven and 15.
So we can actually evaluate.
Blocks two and three pretty easily ourselves.
So let's go ahead and do that.
That way we can validate our results and make sure that our function is working correctly.
So if we come down here.
And we will say for this case, our test in is equal to two.
We have.
One, two.
Three.
So we have one.
So we're going to move this block here, right there.
So that is one.
So now we can.
Remove.
At block because it is here.
So let's just label them to keep them simple A and B, So now we're going to move A over here.
And that's another move.
And then we will move B.
On top of it.
So our output of three four in equals two is correct.
Now if we do test in equals three.
We will do the same thing where we go a.
Be.
See have our.
Walks here.
So we will move.
See?
All the way over.
We will move, be all the way over and then we will take C and put it back on top of B so we can get
rid of that and we can get rid of that and now we can move a.
All the way over.
So we can get rid of a here.
And now we have C here, which means that we can remove.
See from here.
We can now put be here.
And we can now put see here.
And we successfully moved it over.
And that was seven moves, just like our program outputted.
So we can see that we do have a correctly functioning Tower of Hanoi recursive function.
So that concludes all of the recursive examples that I'm going to show you.
If you have any questions regarding recursion, please ask them in the Q&A section and I will respond
to you very quickly to provide you with clarification as to what your question might entail.