The Tower of Hanoi is a famous mathematical problem.
It's a great example of how recursion can be applied to algorithms design.
How to figure out its recursive solution: ↓ {1/9}
It's a great example of how recursion can be applied to algorithms design.
How to figure out its recursive solution: ↓ {1/9}
The puzzle consists of the following pieces:
• 3 pegs A, B and C
• 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 labelled from 1 to n.
{2/9}
• 3 pegs A, B and C
• 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 labelled from 1 to n.
{2/9}
The goal is to move all the disks from peg A to peg B following 2 rules:
• only one 1 disk at a time can be moved
• it's forbidden to move a disk over a smaller one
The problem looks intimidating, so it's worth to start with the simplest scenarios.
{3/9}
• only one 1 disk at a time can be moved
• it's forbidden to move a disk over a smaller one
The problem looks intimidating, so it's worth to start with the simplest scenarios.
{3/9}
With only 1 disk, we can just move the disk from A to B according to the rules.
With 2 disks we can solve it in 3 steps:
• move disk 1 from A to C
• move disk 2 from A to B
• move disk 3 from C to B
{4/9}
With 2 disks we can solve it in 3 steps:
• move disk 1 from A to C
• move disk 2 from A to B
• move disk 3 from C to B
{4/9}
Let's now consider the case of 3 disks.
Since we already know how to move 2 disks, we can:
• move the upper 2 disks (1,2) to peg C
• move disk 3 to peg B
• move disks 1,2 from peg C to B
{5/9}
Since we already know how to move 2 disks, we can:
• move the upper 2 disks (1,2) to peg C
• move disk 3 to peg B
• move disks 1,2 from peg C to B
{5/9}
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
{6/9}
• 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
{6/9}
The first and last steps are a same instance of the original problem and can be solved recursively.
There are 2 recursive calls that decrease the number of remaining disks by 1.
The recursion stop when we hit the base case with only 1 disk.
{7/9}
There are 2 recursive calls that decrease the number of remaining disks by 1.
The recursion stop when we hit the base case with only 1 disk.
{7/9}
The time complexity of the algorithm is O(2ⁿ) where n is the number of disks.
This is because the branching factor is 2 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.
{8/9}
This is because the branching factor is 2 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.
{8/9}
Here an implementation of the algorithm in Python.
{9/9}
{9/9}
Thanks for reading!
I'm Franco Fernando and I often write about algorithms and data structures.
If you enjoyed this thread:
✓ drop a comment
✓ leave a like or retweet
✓ follow me (@franc0fernand0) for similar content
I'm Franco Fernando and I often write about algorithms and data structures.
If you enjoyed this thread:
✓ drop a comment
✓ leave a like or retweet
✓ follow me (@franc0fernand0) for similar content
Loading suggestions...