Count recursion steps in java

Question

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

I am actually 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");
        }
    }
}

Here is a live example: http://ideone.com/xeN4x

My problem is what I get

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

as a conclusion. But 5, not 6 slides should be performed. Any ideas?

Answer 1

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

    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 will get 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

Answer 2

, , , .

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

. .

Answer 3

Here is an example method that will be called recursively countertimes

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

}

there is counter--;twice in your code , so in many cases it will not satisfy the condition

Answer 4

You must test your counter with each such decrease:

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