Tower of Hanoi

Problem Statement (Wikipedia link):

Move N disks from one peg to another.

Analysis:
The Wikipedia page gives a pretty good explanation of the algorithm. Here we only consider recursive solution.

Suppose we have the following initial setup. Our goal is to move all disks from peg A to peg C.

Let's name the disk from 1, ..., N, where N corresponds to each disk's size.

Our goal is to move all disks from A to C, where A is the source and C is the destination. Thinking about this goal, the only situation that we could be successful is that all other 1, ..., N-1 disks are on peg B - spare, then we could move disk N from A to C. Hence, For these N-1 smaller disks, B is their source peg and C is destination peg. Recursively, the same logic applies to these N-1 disks.

With that, we have the following recursive logic:
1) Move N-1 disks from A to B;
2) Move disk N from A to C;
3) Move N-1 disks from B to C;

For a size N tower of hanoi problem, we need to perform 2^N - 1 movements. Hence, the time complexity is exponential.

Code:

void solveHanoi(int count, char src, char spare, char dest) {
    if (count==1)
        cout<<"Move disk from "<<src<<" to "<<dest<<endl;
    else {
        solveHanoi(count-1, src, dest, spare);
        solveHanoi(1, src, spare, dest);
        solveHanoi(count-1, spare, src, dest);
    }
}