# Tower of Hanoi: Illustration of Recursion ## Moving 4 Discs From Peg 1 to Peg 3 1 2 3 4 - - - 1 2 3 1 2 4 3 - - - 1 2 3 1 2 3 4 - - - 1 2 3 1 2 3 4 - - - 1 2 3 ## Moving 3 Discs From Peg 1 to Peg 2 (First Recursion) 1 2 3 4 - - - 1 2 3 3 1 4 2 - - - 1 2 3 1 4 3 2 - - - 1 2 3 1 2 4 3 - - - 1 2 3 ## Moving 2 Discs From Peg 1 to Peg 3 (Second Recursion) 1 2 3 4 - - - 1 2 3 2 3 4 1 - - - 1 2 3 3 4 1 2 - - - 1 2 3 3 1 4 2 - - - 1 2 3 ## Moving 1 Discs From Peg 1 to Peg 2 (Third Recursion) 1 2 3 4 - - - 1 2 3 1 2 3 4 - - - 1 2 3 2 3 4 1 - - - 1 2 3 2 3 4 1 - - - 1 2 3 Note: In the above illustration we first moved 0 discs from peg 1 to peg 3, i.e., we did nothing. Then we moved 1 disc from peg 1 to peg 2. Then again we moved 0 discs from peg 3 to peg 2. Moving 0 discs becomes the base case in our recursion. We do nothing in the base case.