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

Question

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

Yes. That's the hard part if I want to use containers to store values. Should I ditch the containers idea then? — Jack L.
– Jack L., Commented Jul 18, 2014 at 3:31

Elliott Frisch · Accepted Answer · 2014-07-18 03:39:14Z

7

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.

answered Jul 18, 2014 at 3:39

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Leonardo Over a year ago

Great answer, and just to point something else out, the choice of HashMap is due to Hashes being (most of the time) O(1), which is pretty quick, it doesn't need to iterate to find a value !

Jack L. Over a year ago

Thanks for the reply. I should have said this earlier, but I'm also not allowed to use class constants or globals.

nukesz · Accepted Answer · 2016-05-12 14:42:22Z

4

You can use Map::computeIfAbsent method (since 1.8) to re-use the already calculated numbers.

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    private final Map<Integer, Integer> cache = new HashMap<>();

    public int fib(int n) {
        if (n <= 2) {
            return n;
        } else {
            return cache.computeIfAbsent(n, (key) -> fib(n - 1) + fib(n - 2));
        }
    }
}

answered May 12, 2016 at 14:42

nukesz

512 bronze badges

1 Comment

supraja Over a year ago

``` if (n == 0) { return 0; } else if (n <= 2) { return 1; }

Tesseract · Accepted Answer · 2014-07-18 03:47:15Z

2

The other way to do this is to use a helper method.

static private int fibonacci(int a, int b, int n) {
  if(n == 0) return a;
  else return fibonacci(b, a+b, n-1);
}

static public int fibonacci(int n) {
  return fibonacci(0, 1, n);
}

answered Jul 18, 2014 at 3:47

Tesseract

8,1392 gold badges23 silver badges37 bronze badges

Comments

Ken Cheung · Accepted Answer · 2014-07-18 03:49:03Z

How about a class and a private static HashMap?

import java.util.HashMap;

public class Fibonacci {
    private static HashMap<Integer,Long> cache = new HashMap<Integer,Long>();

    public Long get(Integer n) {
        if ( n <= 2 ) {
            return 1L;
        } else if (cache.containsKey(n)) {
            return cache.get(n);
        } else {
            Long result = get(n-1) + get(n-2);
            cache.put(n, result);
            System.err.println("Calculate once for " + n);
            return result;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Fibonacci f = new Fibonacci();
        System.out.println(f.get(10));
        System.out.println(f.get(15));
    }

}

宏杰李 · Accepted Answer · 2017-10-21 16:08:03Z

0

public class Fibonacci {

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


    private void addToCache(int index, int value) {

        cache.put(index, value);


    }

    private int getFromCache(int index) {

        return cache.computeIfAbsent(index, this::fibonacci);

    }


    public int fibonacci(int i) {

        if (i == 1)

            addToCache(i, 0);

        else if (i == 2)
            addToCache(i, 1);
        else
            addToCache(i, getFromCache(i - 1) + getFromCache(i - 2));

        return getFromCache(i);

    }
}

answered Oct 21, 2017 at 16:08

宏杰李

12.2k2 gold badges32 silver badges37 bronze badges

Comments

Bram Van Dyck · Accepted Answer · 2017-12-01 18:50:55Z

You can use memoization (store the values you already have in an array, if the value at a given index of this array is not a specific value you have given to ignore --> return that).

Code:

public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int n = Integer.parseInt(s.nextLine());
    int[] memo = new int[n+1];
    for (int i = 0; i < n+1 ; i++) {
        memo[i] = -1;
    }

    System.out.println(fib(n,memo));


}

static int fib(int n, int[] memo){
    if (n<=1){
        return n;
    }
    if(memo[n] != -1){
        return memo[n];
    }
    memo[n] = fib(n-1,memo) + fib(n-2,memo);
    return memo[n];
}

Explaination:

memo :

 -> int array (all values -1)
 -> length (n+1) // easier for working on index

You assign a value to a given index of memo ex: memo[2]
memo will look like [-1,-1, 1, ..... ]
Every time you need to know the fib of 2 it will return memo[2] -> 1

Which saves a lot of computing time on bigger numbers.

Binay Mishra · Accepted Answer · 2019-07-30 11:21:10Z

0

private static Map<Integer, Integer> cache = new HashMap<Integer, Integer(){
    {
      put(0, 1);
      put(1, 1);
    }
  };
  /**
   * Smallest fibonacci sequence program using dynamic programming.
   * @param n
   * @return
   */
  public static int fibonacci(int n){
    return n < 2 ? n : cache.computeIfAbsent(n, (key) -> fibonacci( n - 1) + fibonacci(n - 2));
  }

edited Jul 30, 2019 at 11:21

answered Mar 9, 2018 at 11:24

Binay Mishra

12 bronze badges

Comments

kumar shivam · Accepted Answer · 2021-06-17 05:29:00Z

0

public static long Fib(int n, Dictionary<int, long> dict)
    {
        if (n <= 1)
            return n;
        if (dict.ContainsKey(n))
            return dict[n]; 
       
        var value = Fib(n - 1,dict) + Fib(n - 2,dict);
        dict[n] = value;
        return value;
    }

answered Jun 17, 2021 at 5:29

kumar shivam

791 gold badge3 silver badges9 bronze badges

Collectives™ on Stack Overflow

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

8 Answers 8

2 Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

2 Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related