java - How to improve the performance of the recursive method? -

i'm learning data structures , algorithms, , here question i'm stuck with.

i have improve performance of recursive call storing value memory.

but problem non-improved version seems faster this.

can me out?

syracuse numbers sequence of positive integers defined following rules:

syra(1) ≡ 1

syra(n) ≡ n + syra(n/2), if n mod 2 == 0

syra(n) ≡ n + syra((n*3)+1), otherwise

import java.util.hashmap; import java.util.map;  public class syralengthsefficient {      int counter = 0;     public int syralength(long n) {         if (n < 1) {             throw new illegalargumentexception();         }          if (n < 500 && map.containskey(n)) {             counter += map.get(n);             return map.get(n);         } else if (n == 1) {             counter++;             return 1;         } else if (n % 2 == 0) {             counter++;             return syralength(n / 2);         } else {             counter++;             return syralength(n * 3 + 1);         }     }      map<integer, integer> map = new hashmap<integer, integer>();      public int lengths(int n) {         if (n < 1) {             throw new illegalargumentexception();         }             (int = 1; <= n; i++) {             syralength(i);             if (i < 500 && !map.containskey(i)) {                 map.put(i, counter);             }         }             return counter;     }      public static void main(string[] args) {         system.out.println(new syralengthsefficient().lengths(5000000));     } } 

here normal version wrote:

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

edit

it slower non-enhanced version.

import java.util.hashmap; import java.util.map;  public class syralengthsefficient {      private map<long, long> map = new hashmap<long, long>();      public long syralength(long n, long count) {          if (n < 1)             throw new illegalargumentexception();          if (!map.containskey(n)) {             if (n == 1) {                 count++;                 map.put(n, count);             } else if (n % 2 == 0) {                 count++;                 map.put(n, count + syralength(n / 2, 0));             } else {                 count++;                 map.put(n, count + syralength(3 * n + 1, 0));             }         }          return map.get(n);      }      public int lengths(int n) {         if (n < 1) {             throw new illegalargumentexception();         }         int total = 0;         (int = 1; <= n; i++) {             // long temp = syralength(i, 0);             // system.out.println(i + " : " + temp);             total += syralength(i, 0);          }         return total;     }      public static void main(string[] args) {         system.out.println(new syralengthsefficient().lengths(50000000));     } } 

final solution (mark correct school auto mark system)

public class syralengthsefficient {  private int[] values = new int[10 * 1024 * 1024];  public int syralength(long n, int count) {      if (n <= values.length && values[(int) (n - 1)] != 0) {         return count + values[(int) (n - 1)];     } else if (n == 1) {         count++;         values[(int) (n - 1)] = 1;         return count;     } else if (n % 2 == 0) {         count++;         if (n <= values.length) {             values[(int) (n - 1)] = count + syralength(n / 2, 0);             return values[(int) (n - 1)];         } else {             return count + syralength(n / 2, 0);         }     } else {         count++;         if (n <= values.length) {             values[(int) (n - 1)] = count + syralength(n * 3 + 1, 0);             return values[(int) (n - 1)];         } else {             return count + syralength(n * 3 + 1, 0);         }     }  }  public int lengths(int n) {     if (n < 1) {         throw new illegalargumentexception();     }     int total = 0;     (int = 1; <= n; i++) {         total += syralength(i, 0);     }     return total; }  public static void main(string[] args) {     syralengthsefficient s = new syralengthsefficient();     system.out.println(s.lengths(50000000)); } 

}

forget answers code inefficient because of use of map, that's not reason why it's going slow - it's fact you're limiting cache of calculated numbers n < 500. once remove restriction, things start work pretty fast; here's proof of concept fill-in details:

private map<long, long> map = new hashmap<long, long>();  public long syralength(long n) {      if (!map.containskey(n)) {         if (n == 1)             map.put(n, 1l);         else if (n % 2 == 0)             map.put(n, n + syralength(n/2));         else             map.put(n, n + syralength(3*n+1));     }      return map.get(n);  } 

if want read more what's happening in program , why fast, take @ wikipedia article memoization.

also, think you're misusing counter variable, increment (++) when value calculated first time, accumulate on (+=) when value found in map. doesn't seem right me, , doubt gives expected result.