// recursion2.cpp			By: Aiman Hanna -  ©1993-2002 Aiman Hanna

// This program gives more examples of recursion. In specific the 
// example shows in this program gives a solution to the classical 
// problem "Tower of Hanoi".
// 
// Warning: Do Not enter a big value when you run this program! Why?


#include <iostream.h>


// move n disks from initNeedle to endNeedle, using tempNeedle
// for intermediate storage of the disks

void hanoi(int n, const char*& initNeedle,
           const char*& endNeedle, const char*& tempNeedle);


int main()
{
   // number of disks and the needle names
   int n;
   char *needleA = "A",
        *needleB = "B",
        *needleC = "C";

   // prompt for n and solve the puzzle for n disks
   cout << "Enter the number of disks: ";
   cin >> n;
   cout << "The solution for n = " << n << endl;
   hanoi(n,needleA, needleC, needleB);

   return 0;
}





void hanoi(int n, const char*& initNeedle,
           const char*& endNeedle, const char*& tempNeedle)
{
   // stopping condition: move one disk
   if (n == 1)
      cout  << "move " << initNeedle << " to "
            << endNeedle << endl;
   else
   {
      // block move takes n-1 disks from initNeedle to
      // tempNeedle using endNeedle for temporary storage
      hanoi(n-1,initNeedle,tempNeedle,endNeedle);

      // move largest disk to endNeedle
      cout  << "move " << initNeedle << " to "
            << endNeedle << endl;

      // block move takes n-1 disks from tempNeedle to
      // endNeedle using initNeedle for temporary storage
      hanoi(n-1,tempNeedle,endNeedle,initNeedle);
   }
}





/*
Run:

Enter the number of disks: 3
The solution for n = 3
move A to C
move A to B
move C to B
move A to C
move B to A
move B to C
move A to C
*/