Towers of Hanoi: Recursion In the Towers of Hanoi solution, we recurse on the la

Question

Towers of Hanoi: Recursion In the Towers of Hanoi solution, we recurse on the largest disk to be moved. That is, we will write a recursive function that takes as a parameter the disk that is the largest disk in the tower we want to move. Our function will also take three parameters indicating from which peg the tower should be moved (source), to which peg it should go (dest), and the other peg, which we can use temporarily to make this happen (spare). At the top level, we will want to move the entire tower, so we want to move disks 5 and smaller from peg A to peg B. We can break this into three basic steps. 1. Move disks 4 and smaller from peg A (source) to peg C (spare), using peg B (dest) as a spare. How do we do this? By recursively using the same procedure. After finishing this, we'll have all the disks smaller than disk 4 on peg C. (Bear with me if this doesn't make sense for the moment we'll do an example soon.) 2. Now, with all the smaller disks on the spare peg, we can move disk 5 from peg A (source)to peg B (dest) 3. Finally, we want disks 4 and smaller moved from peg C (spare)to peg B (dest). We do this recursively using the same procedure again. After we finish, we'll have disks 5 and smaller all on dest In pseudocode, this looks like the following. At the top level, we'll call MoveTower with disk 5, source dest B, and spares C. FUNCTION MoveTower disk, source, dest, spare): IF disk 0, THEN move disk from source to dest ELSE: MoveTower(disk-1, source, spare, dest) Step 1 above move disk from source to dest Step 2 above MoveTower(disk spare, dest, source) Step 3 above END IF Note that the pseudocode adds a base case: When disk is 0, the smallest disk. In this case we don't need to worry about smaller disks, so we can just move the disk directly. In the other cases, we follow the three-step recursive procedure we already described for disk 5.

Explanation / Answer

Here Initial Post: A; Final Post: B; Scratch post: C; N rings.

Time Complexity:

Complexity of tower of Hanoi can be found using this recursive relation
T(n) = T(n-1) + 1 + T(n-1) = 2 T(n-1) + 1

which can be viewed as to solve problem of n disks we need move n-1 disk to intermediate tower, then one disk from origin to destination and then again n-1 disk from intermediate to final tower

So by solving this recursion equation:

We get T(n) = 2n - 1

=> TIme Complexity is : O(2n)

Which is exponential.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.