comportement étrange lors de l'exécution de la tour de Hanoi

Question

Je cours un programme très simple qui simule tour de Hanoi. J'imprime le temps nécessaire pour déplacer les disques n (20 à 30). Je vois un motif étrange. Il faut environ le même laps de temps pour déplacer n (nombre pair) et n + 1 disques. Et pour déplacer n + 2 disque il faut 4 fois de n disques. J'ai mis le programme ci-dessous. Je suppose qu'il y a une certaine optimisation en vm lorsque nous avons plusieurs appels de récursivité. Quelqu'un peut-il donner plus de lumière à ce sujet?

public class Hanoi { 
    public static void move(int n) { 
     if(n > 0) {   
      move(n-1); 
      move(n-1);    
     } 
    } 

    public static void main(String[] args) { 
     int N = 28; 
     move(12); 
     for(int n=18; n <= N; n++) { 
      long start = System.currentTimeMillis(); 
      move(n); 
      long end = System.currentTimeMillis(); 
      System.out.printf("n=%d t=%d i=%d\n",n, (end-start) , 10); 
     } 
    } 
} 

Answer 1

"Problème"? :-)

Si vous ajoutez des E/S ou des calculs décents à la méthode move, vous verrez que ce comportement disparaît. En outre, si vous effectuez simplement un appel récursif move, le programme se termine immédiatement. Ces deux anomalies de synchronisation sont dues à l'optimisation du compilateur et du JIT, comme l'a mentionné Gunner. Cette version de votre méthode move par exemple, a beaucoup plus attendu calendrier:

static int[] pieces = new int[100]; 
public static void move(int n) { 
    if (n > 0) { 
     // random memory operations 
     pieces[n - 1] = pieces[n]; 
     pieces[n] = pieces[n + 1]; 
     pieces[n + 1] = pieces[n + 2]; 
     move(n - 1); 
     move(n - 1); 
    } 
} 

Voici un article intéressant par IBM à propos tail recursion. Voici un autre blog posting sur le sujet.