CODEWITHSUNDEEP
javaperformancerecursion
user19293033
user19293033

Reputation:

how to speed up recursive method to under one second?

I have to solve a task with recursion, and the code has to run in under one second on an average computer. We are not allowed to use for/while loops and streams. We are allowed to use supporting methods and variables.

I already solved the recursion part of the task, my method works for all -111 < n < 131. I am not sure how to speed up the process tho. Ive already tried it with an array and saved the values in it, but I don't think we are allowed to solve the task like that, since everything should be solved recursively..

How do I speed up this recursive method, especially for values n>30?

public static long sequence(int n, int a, int b, int c) {
   if (n > -111 && n < 131) {
      if(n==0) {
         return a;
      }
      if(n==1) {
         return b;
      }
      if(n==2) {
         return c;
      }
      if (n < 0) {
         return 2 * sequence(-n, a, b, c);
      } else {
         return sequence(n - 1, a, b, c) - sequence(n - 2, a, b, c) + 2 * sequence(n - 3, a, b, c);
      }
   }
   return 0L;
}

Upvotes: 0

Views: 91

Answers (1)

Chaosfire
Chaosfire

Reputation: 6985

Look up and try to implement memoization.

It's a technique to cache the result of a computation (especially useful if it's expensive one) and reuse this result when the same input appears again. Currently you recalculate the result for the same input n every time it appears.

Hints: You can use Map<Integer, Long>, where key will be n and value is computed result. Or long[] can work as well, where value at index n will be computed result, you can use second array for negative ns.

Upvotes: 1

Related Questions