java - 汉诺塔；递归方法意味着方法永远不会完成？

Question

public class han {

    public static void main(String[] args) {
        hanoi(5, "A", "B", "C");   
    }

    private static void hanoi (int n, String from, String other, String to) {
        if (n==0){
            return;
        }
        if (n>0){
            hanoi(n-1, from, to, other); //comment
            System.out.printf("Move one disk from %s to %s \n ", from, to);
            hanoi(n-1, other, from, to); //comment
        }
    }

}

我正在学习递归，经典示例是汉诺塔。然而，上面代码片段中的注释行让我有点难过。

如果方法在第一个注释代码处重新启动，该程序如何到达第二个注释代码？像下面这样的东西来说明:

1: some junk
2: goto 1
3: more junk

如果 2 重新启动函数，它怎么会达到 3？汉诺塔片段也是如此:它是如何到达第二个注释代码的？

Answer 1

它不会重新启动。你可以把它想象成一棵树，正在长出新的枝叶。

在您第一次调用 hanoi() 之后，它会一次又一次地调用自己，直到达到基本情况:

if (n==0){
    return;
}

这意味着当第一个注释行的调用到达其所有分支中的基本情况时，它会返回到该点并继续执行。

如果没有基本情况(某些使您的函数最终返回的条件语句)，您的函数将陷入无限循环。

我认为汉诺塔虽然是经典，但很难理解，你应该从一个更简单的问题开始，比如计算 fibonacci sequence 的元素。或实用算法:depth first search

如果您在理解递归方面有困难，我可以建议 The Little Schemer这是一本关于这个主题的好书。我几乎想不出比这更好、更彻底的解释了。