java - 理解这种递归方法

Question

我们在我的 Java 类介绍中学习递归，我很难理解给出的示例中的方法是如何工作的。调用该方法时会发生什么？

这是代码：

public class Hanoi

    private int n;
    private int pegA;
    private int pegB;

    public Hanoi(int in_n, int in_pegA, int in_pegB)
    {
        n = in_n;
        pegA = in_pegA;
        pegB = in_pegB;
    }

    public void makemoves()
    {
        if (n==1)
            System.out.format("%d ==> %d%n", pegA, pegB)
        else
        { 
             int otherPeg = 6 - pegA - pegB; // 1 + 2 + 3 =6
             Hanoi firstmove = new Hanoi (n-1, pegA, otherPeg);
             firstmove.makemoves();
             System.out.format("%d ==> %d%n", pegA, pegB);
             Hanoi secondmove = new Hanoi (n-1, otherPeg, pegB);
             secondmove.makemoves();
        }
    }
}

Answer 1

递归只是一种调用自身并测试中断条件的方法。这是一个非常简单的例子来说明基本概念：

static void recurse( int val ) {
    if ( val == 0 ) {
        return; // returns from last invocation
    }
    System.out.println("val=" + val );
    recurse( val - 1 );
    return; // here the method returns to previous invocation (or initial call from main)
}


public static void main( String[] args) {
    recurse( 3 );
}

第一次调用 recurse(3) 调用该方法，在测试 3 != 0 之后，该方法使用 val - 1 调用自身，直到值变为 0。

调用层次结构如下：

recurse( 3 )
  recurse( 2 )
    recurse( 1 )
      recurse( 0 ) // break condition
      return        // val == 0
    return          // val == 1
  return            // val == 2
return              // val == 3

Answer 2

这项工作的原理很简单，就是按顺序遍历二叉树。检查维基。