Jack L. Jack L. - 6 months ago 30
Java Question

Storing values of a Fibonacci sequence w/ recursion with minimal runtime

I know my code has a lot of issues right now, but I just want to get the ideas correct before trying anything. I need to have a method which accepts an integer n that returns the nth number in the Fibonacci sequence. While solving it normally with recursion, I have to minimize runtime so when it gets something like the 45th integer, it will still run fairly quickly. Also, I can't use class constants and globals.

The normal way w/ recursion.

public static int fibonacci(int n) {
if (n <= 2) { // to indicate the first two elems in the sequence
return 1;
} else { // goes back to very first integer to calculate (n-1) and (n+1) for (n)
return fibonacci(n-1) + fibonacci(n-2);
}
}


I believe the issue is that there is a lot of redundancy in this process. I figure that I can create a List to calculate up to nth elements so it only run through once before i return the nth element. However, I am having trouble seeing how to use recursion in that case though.

If I am understanding it correctly, the standard recursive method is slow because there are a lot of repeats:

fib(6) = fib(5) + fib(4)

fib(5) = fib(4) + fib(3)

fib(4) = fib(3) + 1

fib(3) = 1 + 1

Is this the correct way of approaching this? Is it needed to have some form of container to have a faster output while still being recursive? Should I use a helper method? I just recently got into recursive programming and I am having a hard time wrapping my head around this since I've been so used to iterative approaches. Thanks.

Here's my flawed and unfinished code:

public static int fasterFib(int n) {
ArrayList<Integer> results = new ArrayList<Integer>();
if (n <= 2) { // if
return 1;
} else if (results.size() <= n){ // If the list has fewer elems than
results.add(0, 1);
results.add(0, 1);
results.add(results.get(results.size() - 1 + results.get(results.size() - 2)));
return fasterFib(n); // not sure what to do with this yet
} else if (results.size() == n) { // base case if reached elems
return results.get(n);
}
return 0;
}

Answer

I think you want to use a Map<Integer, Integer> instead of a List. You should probably move that collection outside of your method (so it can cache the results) -

private static Map<Integer, Integer> results = new HashMap<>();

public static int fasterFib(int n) {
  if (n == 0) {
    return 0;
  } else if (n <= 2) { // if
    return 1;
  }
  if (results.get(n) != null) {
    return results.get(n);
  } else {
    int v = fasterFib(n - 1) + fasterFib(n - 2);
    results.put(n, v);
    return v;
  }
}

This optimization is called memoization, from the Wikipedia article -

In computing, memoization is an optimization technique used primarily to speed up computer programs by keeping the results of expensive function calls and returning the cached result when the same inputs occur again.