Нуждается в объяснении того, как работает мой рекурсивный код Ханойской башни

Question

Я только начинаю рекурсию и думаю, что у меня есть общее представление о том, как это работает. У меня есть этот код для проблемы Ханойской башни, и я целый час смотрю на него, пытаясь понять, что именно он делает. Метод 'moveDisks' сбивает меня с толку. Я надеялся, что кто-нибудь сможет помочь объяснить, что происходит в методе. Я не писал это.

Чтобы попытаться понять, я запустил код и поставил 2 для количества дисков. Вот что распечатано:

Это следующие шаги: Переместить диск 1 из A в C, Переместить диск 2 из A в B, Переместить диск 1 из C в B.

Итак, если я правильно понимаю, 2 приводит нас к блоку 'else', что означает, что 2-1 будет перемещаться из A в C. И затем он снова вычитает 1, чтобы сделать еще один ход? Я не понимаю, что будет дальше или почему нужно чередовать башни.

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);
    }
  }
}

Answer 1

Рекурсия - это прыжок веры. Дело в том, что вам не нужно пытаться контролировать каждую мелочь. Вы просто предполагаете, что уже написали свою функцию, и она работает правильно. Тогда вы используете это. Это все.

Итак, это индукция в обратном порядке.

Эйт Тауэрс, вы предполагаете, что это уже в вашем распоряжении. Итак, чтобы двигаться n диски от А до Б, ты двигаешься (n-1) диски от А до С. Теперь у вас есть самый большой диск все еще в А, и аккуратно упорядочены (n-1) диски на C. В пусто. Просто переместите свой последний диск от A до B, и переместите (n-1) диски от C до B. Все готово.

Нормально двигаться n-1 диски, даже когда диск n валяется, потому что все n-1 диски меньше чем nи так диск n может быть безопасно проигнорировано. То же самое касается любого m, 0 < m < n,

перемещение 0 диски еще проще и не нарушают никаких законов.

---

На ваш конкретный вопрос,

А потом снова вычитает 1, чтобы сделать еще один ход?

нет, n все так же, так (n-1) одинаково в обоих случаях.

Вы чередуете башни, чтобы приземлиться на правую в конце.