Why does these extra lines of code cause the "Towers of Hanoi" number of moves to increase?

Question

My lecturer asked us the following in a test:

"Given the following code:

int count=0;
static void towersOfhanoi(int n, char source, char target, char spare)
    {    
        count++;
        if (n==1)
            System.out.println("move a disk from "+source+" to "+target);
         else
         {  
            towersOfhanoi(n-1, source, spare, target); 

            System.out.println("move a disk from "+source+" to "+target);

            towersOfhanoi(n-1, spare, target, source); 
            towersOfhanoi(1, spare, source, target); 
            towersOfhanoi(n-1, source, spare, target); 

What are the value of moves after towersofhanoi(11, A,B,C) has been executed?"

I went home and programmed this and the number of moves have increased, before I plugged these lines of code, I'll call it A (using 11 disks, produced 118097 moves!) :

            towersOfhanoi(n-1, spare, target, source); 
            towersOfhanoi(1, spare, source, target); 
            towersOfhanoi(n-1, source, spare, target); 

I had these lines of code in its place before I plugged those in. I'll call it B (using 11 disks, produced 2047 moves) :

            towersOfhanoi(n-1, spare, target, source); 

My question is, what did the 3 lines of code do in A? Why did the number of moves change, and is there a formula to work out the number of moves? I know that the amount of moves can be worked out using "(2^11) -1" for B. Any feedback would be helpful.

Answer 1

Well, the B line is the correct solution for a Tower of Hanoi problem. The three lines of A instead of B do exactly what they say they do: they call the function recursively with those arguments. The first line is the same of B, so that is correct. The other two lines do not make sense in terms of the problem. You put them in there, so the question is more: why did you do that?

I am guessing that you wanted to do the following instead:

   if (n==1) {
        System.out.println("move a disk from "+source+" to "+target);
   } else {
        towersOfhanoi(n-1, source, spare, target); 
        towersOfhanoi(1, source, target, spare); 
        towersOfhanoi(n-1, spare, target, source); 
   }

Which would another correct expression of the Towers of Hanoi problem, with the same number of moves as the original B.

As for formulas: if we define the number of moves for n disks as N(n), then original solution solution as the number of moves (following the source code):

N(n) = N(n-1) + 1 + N(n-1) 
     = 2 * N(n-1) + 1
     = 2 * (2 * (2 * ... (2 * 1 + 1) ... + 1) + 1) + 1)
     = 2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 1
     = (1 - 2^n) / (1 - 2)
     = 2^n - 1

Along a similar reasoning for your A code:

N(n) = N(n-1) + 1 + N(n-1) + 1 + N(n-1)
     = 3 * N(n-1) + 2
     = 3^(n-1) + 2 * (3^(n-2) + ... + 1)
     = 3^(n-1) + 2 * (1-3^(n-1)) / (1-3)
     = 2 * 3^(n-1) - 1