Hanoi recursive algorithm

The Tower of Hanoi is a classic puzzle that involves moving a stack of discs from one peg to another, subject to the following rules:

1. Only one disc can be moved at a time.
2. A larger disc cannot be placed on top of a smaller disc.

One way to solve the Tower of Hanoi puzzle is to use a recursive algorithm. A recursive algorithm is an algorithm that solves a problem by breaking it down into smaller subproblems and solving those subproblems recursively.

Here's an example of a recursive algorithm for solving the Tower of Hanoi puzzle:

def tower_of_hanoi(n, source, auxiliary, target):
    if n == 1:
        print("Move disc 1 from source", source, "to target", target)
        return
    tower_of_hanoi(n - 1, source, target, auxiliary)
    print("Move disc", n, "from source", source, "to target", target)
    tower_of_hanoi(n - 1, auxiliary, source, target)

This algorithm works by dividing the problem into two subproblems: moving the top n-1 discs from the source peg to the auxiliary peg, and moving the bottom disc from the source peg to the target peg. The algorithm then solves these subproblems recursively, using the auxiliary peg as the intermediate step.

To solve the Tower of Hanoi puzzle with n discs, you can call the tower_of_hanoi() function with the appropriate arguments:

tower_of_hanoi(n, "A", "B", "C")

This will print the steps required to move the discs from the source peg "A" to the target peg "C", using the auxiliary peg "B" as the intermediate step.