Counting the minimum number of moves in Tower of Hanoi using recursion in java

Question

I've been working on a method that returns the minimum number of moves that can be made in the Tower of Hanoi game complacently based on the number of rings. So far I have the basic code that can calculate 2^n (n being the number of rings). However, when I go to subtract 1 the method behaves as if their are no rings.

    static int countHanoiMoves(int n)
{   
    int unSubtrctAnswer = 0;        

    if(n == 0) 
    {
        return  1;
    }

    int halfPower = countHanoiMoves(n / 2);

    if (n % 2 == 1)
    {
        unSubtrctAnswer = (2 * halfPower * halfPower);
    }
    else
    {
        unSubtrctAnswer = (halfPower * halfPower);
    }

    return unSubtrctAnswer - 1;
}

Answer 1

As suggested by Andreas in comments, your algorithm is not correct. The recursive solution is actually quite a bit simpler.

Consider: To move n rings, you first need to move all of the rings on top of the bottom one (n - 1), then move the bottom one (+ 1), then move all the others back on top (n - 1 again).

So...

static int countHanoiMoves(int n) {

    if (n == 0) return 0;

    if (n < 0) throw new RuntimeException("What? A negative number of rings?");

    // count(n-1) + 1 + count(n-1)... since we aren't actually moving
    // the rings, but merely counting the number of moves, we can do
    // it a little more cheaply by just multiplying by 2 rather than
    // calling the recursive method twice

    return 2 * countHanoiMoves(n - 1) + 1;
}

Note that you will fast overrun the limitations of int, so if you need to figure the count for a larger number of rings, changing the return type to long will buy you a little more breathing room.