# Python Code Example: tower of hanoi (recursive)

This code snippet implements a solution for the Tower of Hanoi problem using recursion. The Tower of Hanoi is a classic problem in computer science and mathematics. The goal is to move a stack of discs from one peg to another, using an auxiliary peg, following specific rules.

## Code Example

``````def move(disc, source, destination, aux):
if disc > 0:
move(disc - 1, source, aux, destination)
print("Disc " + str(disc) + ": move from " + str(source) + " to " + str(destination))
move(disc - 1, aux, destination, source)

move(4, "left", "middle", "rigth")``````

### Output

``````Disc 1: move from left to rigth
Disc 2: move from left to middle
Disc 1: move from rigth to middle
Disc 3: move from left to rigth
Disc 1: move from middle to left
Disc 2: move from middle to rigth
Disc 1: move from left to rigth
Disc 4: move from left to middle
Disc 1: move from rigth to middle
Disc 2: move from rigth to left
Disc 1: move from middle to left
Disc 3: move from rigth to middle
Disc 1: move from left to rigth
Disc 2: move from left to middle
Disc 1: move from rigth to middle``````

### Code Explanation

#### Function `move(disc, source, destination, aux)`

``````def move(disc, source, destination, aux):
if disc > 0:
move(disc - 1, source, aux, destination)
print("Disc " + str(disc) + ": move from " + str(source) + " to " + str(destination))
move(disc - 1, aux, destination, source)``````
• Purpose: This function recursively solves the Tower of Hanoi problem by moving discs from the source peg to the destination peg using an auxiliary peg.
• Parameters:
• `disc`: The number of discs to move.
• `source`: The peg from which discs are moved.
• `destination`: The peg to which discs are moved.
• `aux`: The auxiliary peg used for intermediate moves.
• Base Case: The function checks if `disc` is greater than 0. If `disc` is 0 or less, the function does nothing (implicitly returns `None`).
• Recursive Case:
• First Recursive Call: `move(disc - 1, source, aux, destination)`
• Moves `disc - 1` discs from the `source` peg to the `aux` peg, using the `destination` peg as auxiliary.
• Move Largest Disc: Prints the move of the current largest disc from the `source` peg to the `destination` peg.
• Second Recursive Call: `move(disc - 1, aux, destination, source)`
• Moves the `disc - 1` discs from the `aux` peg to the `destination` peg, using the `source` peg as auxiliary.

#### Main Program

``move(4, "left", "middle", "rigth")``
• Function Call: The `move` function is called with `4` discs, moving from the “left” peg to the “middle” peg, using the “right” peg as auxiliary.
• Typo: Note that “right” is misspelled as “rigth”. This should be corrected for clarity.

### Corrected Main Program

``move(4, "left", "middle", "right")``

### Explanation of the Tower of Hanoi

The Tower of Hanoi puzzle involves three pegs and a number of discs of different sizes. The rules are:

1. Only one disc can be moved at a time.
2. A disc can only be placed on top of a larger disc or on an empty peg.
3. All discs start on the source peg, and the goal is to move them to the destination peg.

### Example Execution

For `move(4, "left", "middle", "right")`, the function will:

1. Move the top 3 discs from “left” to “right” using “middle” as auxiliary.
2. Move the 4th disc from “left” to “middle”.
3. Move the 3 discs from “right” to “middle” using “left” as auxiliary.

This process involves multiple recursive calls to break down the problem into smaller subproblems until the base case is reached.