计算java中的递归步骤 [英] Count recursion steps in java

问题描述

我想计算递归步数，并在达到某个限制时停止递归。

I want to count the number of recursion steps and stop the recursion when a certain limit is reached.

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

Actually I am dealing with the Tower of Hanoi problem and I want to limit the number of slides that are performed to solve the problem. Here is my solution:

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张幻灯片。有什么想法？

as output. But 5 and not 6 slides should be performed. Any ideas?

推荐答案

因为你想计算移动次数而不递归深度，您需要存储每个步骤中所做的移动次数。这样的事情：

Since you want to count the number of moves and not the recursion depth, you need to store the number of moves that were made in each step. Something like this:

    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;
}

然后，您获得预期结果：

Then, you obtain the expected result:

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

这篇关于计算java中的递归步骤的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！