java计算递归步数

Question

我想计算递归步骤的数量，并在达到一定限制时停止递归。

实际上，我正在处理河内塔问题，我想限制为解决该问题而执行的幻灯片数量。这是我的解决方案：

class HanoiNK{

    public static void main(String args[]){

            int n = 4;
            int k = 5;

            try{
                slide(k, n, 'A', 'B', 'C');
            }catch(Exception e){
                System.out.println(e);
            }
    }

    public static void slide(int counter, int height, char source,
                              char buffer, char destination) throws Exception{      
        if(counter > 0){
            if(height == 1){                                
                System.out.println("move "+ height +" from " +
                                                source + " to " + destination);
            }else{  
                counter--;
                slide(counter, height - 1, source, destination, buffer);    
                System.out.println("move "+ hoehe +" from " +
                                                source + " to " + destination);
                counter--;
                slide(counter, height - 1, buffer, source, destination);    
            }
        }else{
            throw new Exception("stop here");
        }
    }
}

这是实例： http://ideone.com/xeN4x

我的问题是我得到

move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to A
move 2 from C to B
java.lang.Exception: stop

了输出。但应该进行 5 张而不是 6 张幻灯片。有什么想法吗？

Answer 1

问题是您正在测试 counter 是否大于或等于 一，然后将其递减 二。

counter--;
// ...
counter--;

这里计数器可能会变为负数。你需要检查一下。

Answer 2

由于您想要计算移动次数而不是递归深度，因此您需要存储每个步骤中进行的移动次数。像这样：

    public static int slide(int counter, int hoehe, char quelle,                           char ablage, char ziel)
throws Exception{         
    if (hoehe == 1) {          
        System.out.println("move "+ hoehe +" from " +                                             
                quelle + " to " + ziel);   
        if (--counter == 0) throw new Exception("hier stoppen"); 
    } else {     
        counter = slide(counter, hoehe - 1, quelle, ziel, ablage);     
        System.out.println("move "+ hoehe +" from " +          
                quelle + " to " + ziel);             
        if (--counter == 0) throw new Exception("hier stoppen"); 
        counter = slide(counter, hoehe - 1, ablage, quelle, ziel);       
    }     
    return counter;
}

然后，您将获得预期的结果：

move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to A
java.lang.Exception: hier stoppen

Answer 3

递归调用 counter 次，其中有 counter---; 两次，因此在许多情况下它不会满足条件

public void callMe(int counter){
      if(counter == 1 ){
             return;
      }else{
             callMe(--counter);
      }

}

这是一个示例方法，将在代码中

Answer 4

您必须在每次减量时测试您的计数器，如下所示：

public static void slide(int counter, int hoehe, char quelle,
                      char ablage, char ziel) throws Exception{
    if(hoehe == 1){
        System.out.println("move "+ hoehe +" from " +
                                        quelle + " to " + ziel);
    }else{
        if (--counter == 0) throw new Exception("hier stoppen");
        slide(counter, hoehe - 1, quelle, ziel, ablage);
        System.out.println("move "+ hoehe +" from " +
                                        quelle + " to " + ziel);
        if (--counter == 0) throw new Exception("hier stoppen");
        slide(counter, hoehe - 1, ablage, quelle, ziel);
    }
}