Java 8 fast non recursive fibonacci

Problem

Classical recursive Fibonacci is slow and crashes with a stack-overflow exception:

package recursion;

public class Fibon {

    public static void main(String[] args) {
        System.out.println(fib(50));
    }

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

Solution Non recursive Fibonacci

In order to make fast and working Fibonacci you can use an object. This is working for really high numbers extremely fast and do not crash with error:

package recursion;

class Fibon {

    public static void main(String[] args) {
        Fibon fibon = new Fibon();
        while(fibon.current < 100) fibon.next();
        System.out.println(fibon.fib);
    }

    int old=1,fib=1,current=1;

    int next() {
        int newFib=fib+old;
        old=fib;
        fib=newFib;
        current++;
        return  fib;
    }
}

The method next() calculate the next element of the sequence. In the main we instantiate new Fibon object and when call method next() until we reach 100. The result is available in less than a second. Of course the number is negative because you get overflow.

Related Article