How to understand recursive function - Tower of Hanoi

Tower of Hanoi

Let's realize how does tower of hanoi works and how to use recursive function to implement it!!!

The Tower of Hanoi is a mathematical game or puzzle, it's a classical problem during your CSIE studies.

First, the demonstration of process(3 disks and 3 rods) as below[1]: Second, moving the entire stack to another rod need to comply with the following rules: 1. Only one disk 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 rod. 3. No larger disk may be placed on top of a smaller disk.

Third, the solutions between 1 disks and 4 disks are shown as following:

1 disks	2 disks	3 disks	4 disks
			1 A->B
			2 A->C
			1 B->C
			3 A->B
		1 A->C	1 C->A
		2 A->B	2 C->B
	1 A->B	1 C->B	1 A->B
1 A->C	2 A->C	3 A->C	4 A->C
	1 B->C	1 B->A	1 B->C
		2 B->C	2 B->A
		1 A->C	1 C->A
			3 B->C
			1 A->B
			2 A->C
			1 B->C

we can find regular movement! In short, the pattern can be proposed: + Shift 'n-1' disks from 'A' to 'B'. + Shift last disk from 'A' to 'C'. + Shift 'n-1' disks from 'B' to 'C'.

Finally, we can get complicated solution by computing:

#include <iostream>
using namespace std;

void hanoi(int n, char start, char temp, char target, int &moved)
{
    if (n == 1){
        cout << "Move " << start << " -> " << target << endl;
        moved++;
    }else{
        hanoi(n - 1, start, target, temp, moved);
        hanoi(1, start, temp, target, moved);
        hanoi(n - 1, temp, start, target, moved);
    }
}

int main()
{   
   int n = 3, moved = 0;
   hanoi(n, 'A', 'B', 'C' , moved);
   cout << "Total moved " << moved << " steps" << endl;  
   return 0;
}

Explanation:
In the main(), I declare "n" is represented the number of dists and "moved" is a counter. At 19 line, call hanoi() function which consists 5 argument ('A', 'B' and 'C' are represented each rods).
At hanoi() function, it checks n whether it's equal to 1 at 6 line, but it's invalid at the first time. So, the program runs else part.
n = 3 - 1, A C B (recursive call at 10 line)
   n = 2, A C B
  => if statement is invalid, so do else part
  n= 2 - 1 , A B C (recursive call)
    n = 1, A B C
    => if statement is valid
    => print "Move A → C", moved ++
  n = 1, A C B (recursive call at 11 line)
  => print "Move A → B", moved ++
  n = 2 - 1, C A B (recursive call at 12 line)
    n = 1, C A B
    => if statement is valid
    => print "Move C → B", moved ++
n = 1, A B C (recursive call at 11 line)
=> if statement is valid
=> print "Move A → C", moved ++
n = 3 - 1, B A C (recursive call at 12 line)
  n = 2, B A C
  => if statement is invalid, so do else part
  n = 2 - 1, B C A (recursive call at 10 line)
    n = 1, B C A
    => if statement is valid
    => print "Move B → C", moved ++
  n = 1, B A C (recursive call at 11 line)
  => print "Move B → C", moved ++
n = 2 - 1, A B C (recursive call at 12 line)
=> if statement is valid
=> print "Move A → C", moved ++

Reference:
[1] André Karwath aka Aka, CC BY-SA 2.5 https://creativecommons.org/licenses/by-sa/2.5, via Wikimedia Commons