Is there a way to program towers of hanoi without recursion/stacks?

Question

I recently wrote a program for solving towers of Hanoi using recursion. But is there a way to solve this puzzle without using stacks or recursion- preferably loops or something in that order.

Here's the code I wrote using recursion:

static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) 
    { 
        if (n == 1) 
        { 
            System.out.println("Move disk 1 from rod " + from_rod + " to rod " + to_rod); 
            return; 
        } 
        towerOfHanoi(n-1, from_rod, aux_rod, to_rod); 
        System.out.println("Move disk " + n + " from rod " + from_rod + " to rod " + to_rod); 
        towerOfHanoi(n-1, aux_rod, to_rod, from_rod); 
    } 

Thanks for any help in advance:)

Answer 1

Yes. It can be programmed without recursion and without stacks (or simulated stacks).

The Wikipedia page on Tower of Hanoi has a section on a binary solution where the steps for an N-disk Tower of Hanoi are encoded in the binary representation of the numbers 0 to 2^N.

I won't copy the full details here, but the core is a neat formula for translating move number m to the move to be made:

Move m is from peg (m & m - 1) % 3 to peg ((m | m - 1) + 1) % 3, where the disks begin on peg 0 and finish on peg 1 or 2 according as whether the number of disks is even or odd

There is another solution involving Gray codes.