best way to find Fibonacci number

Question

Fibonacci series is 0 1 1 2 3 5 8... and so on. It can be obtained using swapping elements and displaying them whereas we can obtain it using array. I was asked to find it using recursion in interview and main logic for it,

int fib(int n){
if(n<1)
    return 1;
else
    return fib(n-1)+fib(n-2);}

It generate problem for stack for big number because we are increasing complexity here. So what is optimum way here?

Answer 1

Memoization. Create logic that calculates each fib numb only once.

static BigInteger[] fibNumbs = new BigInteger[10000];


public static void main(String[] args) {
        fibNumbs[1] = BigInteger.ONE;
        fibNumbs[2] = BigInteger.ONE;
        System.out.println(fibOf(10000));
    }

public static BigInteger fibOf(int n) {
        if (n <= 1) {
            return BigInteger.ONE;
        }

        if (fibNumbs[n - 1]==null) {
            fibNumbs[n - 1] = fibOf(n - 1);
        }

        if (fibNumbs[n - 2]==null) {
            fibNumbs[n - 2] = fibOf(n - 2);
        }

        return fibNumbs[n - 1].add(fibNumbs[n - 2]);
    }