Calculating a Fibonacci number with array

Question

// I am learning about recursion in Java. /** I am trying to calculate the 45th Fibonacci number by using an array to shorten the time used, which does not work out well... error message: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 45 at Auf1.fib2(Auf1.java:25) at Auf1.main(Auf1.java:49) **/

public class Auf1 {

    public static long[] feld;

        public static long fib2(long n) { 
            if ((n == 1) || (n == 2)) {
                return 1;
            } else {
                if (feld[(int) n] != -1) {
                    return feld[(int) n];
                } else {
                    long result = fibo(n - 1) + fibo(n - 2);
                    feld[(int) n] = result;
                    return result;
                }
            }
        }

public static void main(String[] args) {
     long n = 45;
     feld = new long[(int) n];
        for (int i = 0; i < n; i++) {
            feld[i] = -1;
        }
        long result = fib2(n);
        System.out.println("Result: " + result);
    }
}

Make the array one element larger: `feld = new long[(int) n + 1];` (valid indices are from 0 to length-1) — Henry, Oct 19 '14 at 20:32
Do you have to use an array? Do you have to store the prior computations of the fibonacci sequence? — Richard Kenneth Niescior, Oct 19 '14 at 20:36
Of course the iterative way is much faster but its a nice practice to get in touch with dynamic programming — user, Oct 19 '14 at 20:41

user · Accepted Answer · 2014-10-19T20:38:53.970

The Array indices starts with 0. You create a array of size 45. Valid array indices are 0,1...44. In your first call of fib2 your check if array[45] equals -1. array[45] is not a valid index and will result in an IndexOutOfBoundException.

change the following lines:

(feld[(int) n] != -1)

to

(feld[(int) n - 1] != -1)

and the line

feld[(int) n] = result

to

feld[(int) n - 1] = result;

BTW There is a syntax error. The recursive call should be fib2(n-1) + fib2(n-2) and not fibo(n-1) + fibo(n-2)

Calculating a Fibonacci number with array

1 Answers1

Linked