需要解释我的汉诺塔递归代码是如何工作的

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 个圆盘从 A 移动到 B，您需要将 (n-1) 个圆盘从 A 移动到 C。现在最大的圆盘仍在 A，并在 C 处整齐排列 (n-1) 个圆盘。 B 是空的。只需将最后一个磁盘从 A 移动到 B，然后将 (n-1) 个磁盘从 C 移动到 B。您就完成了。

即使 n 圆盘在附近也可以移动 n-1 个圆盘，因为所有 n-1 个圆盘都小于 n，所以圆盘n 可以安全地忽略。同样适用于任何 m、0 < m < n.

移动 0 个磁盘更容易，而且也不违反任何法律。

针对您的具体问题，

And then it subtracts 1 again to do another move?

不，n 仍然是相同的，所以 (n-1) 在两种情况下都是相同的。

您交替使用塔楼，最终落在正确的塔楼上。

需要解释我的汉诺塔递归代码是如何工作的

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

java

recursion

towers-of-hanoi