Fun with recursion in Java

Hanoi.java contains a routine textbook solution to the familiar Towers of Hanoi problem. Upon compiling it and running it ( java Hanoi > out.txt), the execution times for the various numbers of discs are printed out as follows



…
n=10 t=64
n=11 t=127
n=12 t=259
n=13 t=509
n=14 t=996
n=15 t=2000
n=16 t=4089
n=17 t=8302
n=18 t=16316
n=19 t=33204
…

As expected, every time the the number of discs increases by 1, the execution time is doubled.

Now run it again after commenting out the System.out.printf in the move method, and you will see something like

…
n=20 t=10
n=21 t=10
n=22 t=42
n=23 t=44
n=24 t=170
n=25 t=164
n=26 t=678
n=27 t=648
n=28 t=2745
n=29 t=2632
n=30 t=10945

This is strange because the execution time is seen to remain roughly the same for adjacent values of n (e.g. 22,23) and then quadruples in one shot for the next two values (e.g. 24,25).

When I tried the same stuff in C (hanoi.c) with gcc on Linux , things ran as expected in both situations and the strange behavior was not seen.

Looks like some JVM optimization is at work since this behavior is not undesirable as less time than expected is being taken for odd values of n.

I used JDK 1.6 Java HotSpot VM on Windows. My friends experimented with other 1.6 VMs and were able to see similar behavior.

Can anyone explain this ?