Legend has it that in a temple in the Far East, priests are attempting to move a stack of disks from one peg to another. The initial stack had 64 disks threaded onto one peg and arranged from bottom to top by decreasing size. The priests are attempting to move the stack from this peg to a second peg under the constraints that exactly one disk is moved at a time, and at no time may a larger disk be placed above a smaller disk. A third peg is available for temporarily holding the disks. According to the legend, the world will end when the priests complete their task.

Consider three pegs numbered 1 through 3. Let us assume that the priests are attempting to move the 64 disks from peg 1 to peg 2, using peg 3 as a temporary holding peg. The problem is to design an algorithm that that will print the precise sequence of disk peg-to-peg transfers.

If you were to approach this problem with conventional methods, you would rapidly find yourself hopelessly knotted up in managing the disks. Instead, if you attack the problem with recursion in mind, it immediately becomes tractable. If we assume that we have a function that can move n - 1 disks from one peg to another using a third peg as a temporary holding peg, then we can easily formulate an algorithm to move n disks from peg 1 to peg 2 by using the function that moves n - 1 disks as follows:

1. Move n - 1 disks from peg 1 to peg 3, using peg 2 as a temporary holding peg.

2. Move the last disk (the largest) from peg 1 to peg 2.

3. Move the n - 1 disks from peg 3 to peg 2, using peg 1 as a temporary holding disk.

Write a recursive program that solves the Towers of Hanoi problem.

Your program must accept a single command line argument, a positive integer. This integer n will represents the number of disks to move. Number the disks from 1 (the smallest disk) to n (the largest disk). You should always start with all the disks on peg 1 with pegs 2 and 3 empty. Your program should then produce the sequence of disk peg-to-peg moves to move all the disks from peg 1 to peg 2.

Your output should print one move per line. Each move must be in the following format,

1 2->3

which is interpreted as "move disk 1 from peg 2 to peg 3." Assuming that the name of your program is hanoi, below is an example of what an execution of your program should look like:

z123456@turing:~$ ./hanoi 2 1 1->3 2 1->2 1 3->2