1 
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

3如果重新启动该功能，它怎么能达到2？河内塔片段也是如此：它是如何到达第二个注释代码的？

4

2 回答 2

3

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

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

if (n==0){
    return;
}

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

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

我认为河内塔虽然是经典但很难理解你应该从一个更简单的问题开始，比如计算斐波那契数列的元素或实用算法：深度优先搜索

如果您在理解递归方面有困难，我可以推荐The Little Schemer，这是一本关于这个主题的优秀书籍。我几乎无法想象比这更好、更彻底的解释了。

于 2013-11-12T00:50:35.960 回答
2

当递归函数完成时，它会在此处调用的相同位置恢复，这是一个小插图，仅打印 3-1 中的数字

递归方法

public static void printRecursive(int n)
{
    if(n ==0)
        return;
    system.out.println(n);
    print(n-1);
    //continue execution here
}

迭代法

public static void printIterative()
{
    if(n == 0)
    {
        return;
    }
    else
    {
        system.out.println(n);
        int n2 = n-1;
        if(n2 == 0)
        {
            return
        }
        else
        {
            system.out.println(n2);
            int n3 = n2-1;
            if(n3 ==0)
            {
                return;
            }
            else
            {
                system.out.println(n3);
                int n....
                ...
                ...
            }
            //continue....
        }
        //continue exectuion from second call
    }
    //continue exection from first call
}

基本上我在第二种方法中所做的是复制并通过连续调用直接内联打印而不是调用自身。

递归调用将从进行递归调用的位置继续运行。这可能很难理解，但值得努力理解

于 2013-11-12T00:59:45.440 回答