Strange recursion optimization by java -

i came across weird results when trying answer question: how improve performance of recursive method?

but don't need read post. i'll give relevant context here. might seem lengthy isn't complicated if read through once. hope interesting all. context,

syra(n) = { 1 if n=1;              n + syra(n/2) if n even; ,              n + syra(3n+1) if n odd           } 

and

syralen(n) = no. of steps calculate syra (n) 

e.g, syralen(1)=1, syralen(2)=2 since need go 2 steps. syra(10) = 10 + syra(5) = 15 + syra(16) = 31 + syra(8) = 39 + syra(4) = 43 + syra(2) = 45 + syra(1) = 46. syra(10) needed 7 steps. therefore syralen(10)=7

and finally,

lengths(n) = syralen(1)+syralen(2)+...+syralen(n) 

the question poster there trying calculate lengths(n)

my question recursive solution op has posted (which second snippet in question). i'll repost here:

public class syralengths{          int total=1;         public int syralength(long n) {             if (n < 1)                 throw new illegalargumentexception();             if (n == 1) {                 int temp=total;                 total=1;                 return temp;             }             else if (n % 2 == 0) {                 total++;                 return syralength(n / 2);             }             else {                 total++;                 return syralength(n * 3 + 1);             }         }          public int lengths(int n){             if(n<1){                 throw new illegalargumentexception();             }             int total=0;             for(int i=1;i<=n;i++){                 total+=syralength(i);             }              return total;         }          public static void main(string[] args){             system.out.println(new syralengths().lengths(5000000));         }        } 

surely unusual (and not recommended) way of doing recursively, calculate right thing, have verified that. tried write more usual recursive version of same:

public class syraslow {      public long lengths(int n) {         long total = 0;         (int = 1; <= n; ++i) {             total += syralen(i);         }         return total;     }      private long syralen(int i) {         if (i == 1)             return 1;         return 1 + ((i % 2 == 0) ? syralen(i / 2) : syralen(i * 3 + 1));     } 

now here's weird part - tried test performance of both above versions like:

public static void main(string[] args){             long t1=0,t2=0;             int test_val=50000;              t1 = system.currenttimemillis();             system.out.println(new syralengths().lengths(test_val));             t2 = system.currenttimemillis();             system.out.println("syralengths time taken: " + (t2-t1));              t1 = system.currenttimemillis();             system.out.println(new syraslow().lengths(test_val));             t2 = system.currenttimemillis();             system.out.println("syraslow time taken: " + (t2-t1));         } 

for test_val=50000, output is:

5075114 syralengths time taken: 44 5075114 syraslow time taken: 31 

as expected (i guess) plain recursion better. when go 1 step further , use test_val=500000, output is:

62634795 syralengths time taken: 378 exception in thread "main" java.lang.stackoverflowerror     @ syraslow.syralen(syraslow.java:15)     @ syraslow.syralen(syraslow.java:15)     @ syraslow.syralen(syraslow.java:15) 

why it? kind of optimization being done java here syralengths version doesn't hit stackoverflow (it works @ test_val=5000000)? i tried using accumulator-based recursive version in case jvm doing tail-call optimization:

private long syralenacc(int i, long acc) {         if (i == 1) return acc;     if(i%2==0) {         return syralenacc(i/2,acc+1);     }     return syralenacc(i * 3 + 1, acc+1);     } 

but still got same result (thus there no tail-call optimization here). then, what's happening here?

p.s: please edit better title if can think of any.

with original version, tail recursion optimization possible (within jit). dunno whether occurred or not, though. it's possible original more efficient heap [er, mean stack] use. (or there may functional difference not obvious on cursory examination.)