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.