Thread: Recursive Fibonacci sequence optimization

Originally Posted by aesguitar

I've written an algorithm for finding terms in a Fibonacci Sequence using a recursive method.

Here's the thing: Lots of things are "easy" to define and explain, and, maybe even easy to understand as recursive processes.

However...

There is a lot of overhead (time and memory) in deep recursive calls. In the case of the Fibonacci sequence, each term requires two recursive calls.

So...

Implement iteratively instead of recursively. Make a loop, not a recursive call.

    public static BigInteger fibSeq(int x)
    {
        // Declare BigInteger variables for sum, nminus1 and nminus2
        // Initialize sum to zero and the others to 1
 
        if( x <= 2)
        {
            return BigInteger.ONE;
        } // x <= 2
        else
        {
            for (int i = 3; i <= x; i++)
            {
                // Set sum equal to nminus1 + nminus2
                // Set nminus2 equal to nminus1
                // Set nminus1 equal to sum
            } // for
        } // else
        return sum;
    }

Now, this can get an answer much quicker.

But, here's the thing:

Your problem is not to calculate, say the 3000th term of the sequence. It is to keep calculating until there are 1000 digits in the result and then stop. I mean, the whole problem is to determine how many terms it takes to get up to the 1000 digit thing, right?

So...

Here's what I suggest:

Declare a Fibonacci class. It has private BigInteger variables for sum, nminus1 and nminus2. Because of the quirkiness of the startup routine, I might make a variable named "called" that takes care of the first two terms.

Then, instead of trying to tell it how many terms to give just make a "next()" method that gives the next term.

After creating the object, the first call to next() gives F1, the second call gives F2. Just keep calling next() until you get a term with the number of digits you need. (I would probably just keep count of the terms in main(), although you could use the "called" variable in the object if you wanted to create a "getter" method for it.)

class Fibonacci
{
    private int called;
    private BigInteger nm2;
    private BigInteger nm1;
 
    // Constructor
    public Fibonacci()
    {
        nm2 = new BigInteger("1");
        nm1 = new BigInteger("1");
        called = 0;
    }
 
    public BigInteger next()
    {
        // Special condition to get the first two terms
        if (called < 2)
        {
            ++called;
            return BigInteger.ONE;
        } // if (called < 2)
        else
        {// A loop to get higher terms.  Note that nm1 and nm2 have been "primed" with values of 1, so it's ready to go
            // Set sum equal to nmi1+nm2
            // Set nm2 equal to nm1
            // Set nm1 equal to sum
        }//else
        return sum;
    }// next
} // Fibonacci

Now in main(), create a Fibonacci instance and call its next() method in a loop where the loop control function is the length of the string that the BigInteger.toString() function gives you for the terms as they flow out from the object.
Of course, instead of making a separate class, the whole Fibonacci loop could be put into main(), and it would save the time-consuming function calls.

My methodology: Implement first. Optimize later, if appropriate. (It's not a speed contest, right? I mean if a clean, modular object-oriented approach does the deed in a second or so, is there any practical reason to try to get it down to ten milliseconds? maybe so; maybe not.)


Cheers!

Z