C++ Code Example: tower of hanoi (recursive)

The code is a solution to the classical problem of the Towers of Hanoi. The goal of the problem is to move a stack of discs from one peg to another, with the following constraints:

  1. Only one disc can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.
  3. No disk may be placed on top of a smaller disk.

The solution to this problem is implemented using recursion. The move function takes in four parameters:

  • disc: represents the number of discs in the stack
  • from: represents the peg where the stack of discs is located
  • to: represents the peg where the stack of discs will be moved to
  • aux: represents the auxiliary peg that can be used to temporarily store the discs

The function works by first moving the disc-1 stack to the aux peg. Then, it prints the message “Disc disc: move from from to to“. Finally, it moves the disc-1 stack from the aux peg back to the to peg.

The process continues until the disc is equal to 0, at which point the recursion will stop.

In the main function, the move function is called with the parameters 4, "left", "middle", and "right". This means that the solution will start with a stack of 4 discs and move it from the left peg to the middle peg using the right peg as the auxiliary peg. The output will show the steps required to solve the Towers of Hanoi problem with 4 discs.

#include <iostream>
using namespace std;

void move(int disc,
          string from,
          string to,
          string aux) {
    if (disc > 0) {
        move(disc - 1, from, aux, to);
        cout << "Disc " << disc << ": move from " << from << " to " << to << endl;
        move(disc - 1, aux, to, from);
    }
}

int main() {
    move(4, "left", "middle", "rigth");

    return 0;
}
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