In need of explanation of how my Tower of Hanoi Recursion code works

Question

I am just getting into recursion and I think I have a basic understanding of how it works. I have this code for a Tower of Hanoi problem and I have been staring at it for an hour trying to figure out exactly what it is doing. The method 'moveDisks' is confusing to me. I was hoping someone could help explain what's going on in the method. I didn't write it.

To try to understand I ran the code and put 2 for the number of disks. Here is what printed out:

The moves are: Move disk 1 from A to C, Move disk 2 from A to B, Move disk 1 from C to B

So, if I understand it right, the 2 brings us to the 'else' block which means that 2-1 is going to move from A to C. And then it subtracts 1 again to do another move? I don't understand what happens next or why the need to alternate towers.

import java.util.Scanner; 

public class TowersOfHanoi {
  /** Main method */
  public static void main(String[] args) {
    // Create a Scanner
    Scanner input = new Scanner(System.in);
    System.out.print("Enter number of disks: ");
    int n = input.nextInt();

    // Find the solution recursively
    System.out.println("The moves are:");
    moveDisks(n, 'A', 'B', 'C');
  }

  /** The method for finding the solution to move n disks
      from fromTower to toTower with auxTower */

  public static void moveDisks(int n, char fromTower,
      char toTower, char auxTower) {
    if (n == 1) // Stopping condition
      System.out.println("Move disk " + n + " from " +
        fromTower + " to " + toTower);
    else {
      moveDisks(n - 1, fromTower, auxTower, toTower);
      System.out.println("Move disk " + n + " from " +
        fromTower + " to " + toTower);
      moveDisks(n - 1, auxTower, toTower, fromTower);
    }
  }
}

use a debugger to step through your program and become enlightened — wero, Feb 12 '16 at 18:01
Possible duplicate of [Tower of Hanoi: Recursive Algorithm](http://stackoverflow.com/questions/1223305/tower-of-hanoi-recursive-algorithm) — Tennyson H, Feb 12 '16 at 18:03

Will Ness · Accepted Answer · 2017-12-15T21:58:20.653

Recursion is a leap of faith. The point to it is, you don't need to try to control every little detail. You just assume you've already written your function, and it works properly. Then you use it. That's all.

So, it's induction in reverse.

Eith the Towers, you assume it's already at your disposal. So, to move n disks from A to B, you move (n-1) disks from A to C. You now have the biggest disk still at A, and neatly ordered (n-1) disks at C. The B is empty. Just move your one last disk from A to B, and move the (n-1) disks from C to B. You're done.

It's OK to move n-1 disks even when the disk n is lying around, because all the n-1 disks are smaller than n, and so the disk n can be safely ignored. Same goes for any m, 0 < m < n.

Moving 0 disks is even easier, and doesn't break any laws either.

To your specific question,

And then it subtracts 1 again to do another move?

no, the n is still the same, so (n-1) is the same in both cases.

You alternate towers to land on the right one in the end.

That is a great way to explain recursion. – Claudiu Feb 12 '16 at 18:20 — Claudiu, Feb 12 '16 at 18:20
@Chap glad to be of help. :) – Will Ness Feb 13 '16 at 11:02 — Will Ness, Feb 13 '16 at 11:02

In need of explanation of how my Tower of Hanoi Recursion code works

1 Answers1

Linked