Fibonacci Revisited

Good day! Hope your day is winding down nicely. We were expecting thunderstorms today in the Twin Cities of Minneapolis and St. Paul, but we just got some rain in an almost sunny and warm day. It seems that this summer is going to be warmer than usual.

I decided to watch Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges which is slightly over 5 hours long. The idea is to watch and experiment as you go. The code on the video is implemented in JavaScript. I decided to use Java.

It is going to take me a few days to watch the entire video and experiment with the code.

On a separate note I am in the process of setting up .NET on a different machine. I want to do so experimentation using the VSCode IDE. I have the same setup on a different machine but I am using Visual Studio Enterprise Edition. More on this as soon as I complete and verify the installation.

The problem at hand is to develop a method / function to compute the n Fibonacci number.

We will have to write a simple test scaffold to collect the input number, call the method in questions and display the results.

So what is a Fibonacci sequence? Is a sequence that start with two 1 numbers and the following number is the sum of the previous two.

Fib: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
  n: 1  2  3  4  5  6  7   8   9   10 ...

The first line shows the first few Fibonacci numbers. The second line the associated number. The idea for our method / function of interest is to present ‘n’ and in return get the associated Fibonacci number.

45
main <<< n: 45
main <<< i: 1 fib0: 1
main <<< i: 2 fib0: 1
main <<< i: 3 fib0: 2
main <<< i: 4 fib0: 3
main <<< i: 5 fib0: 5
main <<< i: 6 fib0: 8
main <<< i: 7 fib0: 13
main <<< i: 8 fib0: 21
main <<< i: 9 fib0: 34
main <<< i: 10 fib0: 55
main <<< i: 11 fib0: 89
main <<< i: 12 fib0: 144
main <<< i: 13 fib0: 233
main <<< i: 14 fib0: 377
main <<< i: 15 fib0: 610
main <<< i: 16 fib0: 987
main <<< i: 17 fib0: 1597
main <<< i: 18 fib0: 2584
main <<< i: 19 fib0: 4181
main <<< i: 20 fib0: 6765
main <<< i: 21 fib0: 10946
main <<< i: 22 fib0: 17711
main <<< i: 23 fib0: 28657
main <<< i: 24 fib0: 46368
main <<< i: 25 fib0: 75025
main <<< i: 26 fib0: 121393
main <<< i: 27 fib0: 196418
main <<< i: 28 fib0: 317811
main <<< i: 29 fib0: 514229
main <<< i: 30 fib0: 832040
main <<< i: 31 fib0: 1346269
main <<< i: 32 fib0: 2178309
main <<< i: 33 fib0: 3524578
main <<< i: 34 fib0: 5702887
main <<< i: 35 fib0: 9227465
main <<< i: 36 fib0: 14930352
main <<< i: 37 fib0: 24157817
main <<< i: 38 fib0: 39088169
main <<< i: 39 fib0: 63245986
main <<< i: 40 fib0: 102334155
main <<< i: 41 fib0: 165580141
main <<< i: 42 fib0: 267914296
main <<< i: 43 fib0: 433494437
main <<< i: 44 fib0: 701408733
main <<< i: 45 fib0: 1134903170

main <<< i: 1 fib: 1
main <<< i: 2 fib: 1
main <<< i: 3 fib: 2
main <<< i: 4 fib: 3
main <<< i: 5 fib: 5
main <<< i: 6 fib: 8
main <<< i: 7 fib: 13
main <<< i: 8 fib: 21
main <<< i: 9 fib: 34
main <<< i: 10 fib: 55
main <<< i: 11 fib: 89
main <<< i: 12 fib: 144
main <<< i: 13 fib: 233
main <<< i: 14 fib: 377
main <<< i: 15 fib: 610
main <<< i: 16 fib: 987
main <<< i: 17 fib: 1597
main <<< i: 18 fib: 2584
main <<< i: 19 fib: 4181
main <<< i: 20 fib: 6765
main <<< i: 21 fib: 10946
main <<< i: 22 fib: 17711
main <<< i: 23 fib: 28657
main <<< i: 24 fib: 46368
main <<< i: 25 fib: 75025
main <<< i: 26 fib: 121393
main <<< i: 27 fib: 196418
main <<< i: 28 fib: 317811
main <<< i: 29 fib: 514229
main <<< i: 30 fib: 832040
main <<< i: 31 fib: 1346269
main <<< i: 32 fib: 2178309
main <<< i: 33 fib: 3524578
main <<< i: 34 fib: 5702887
main <<< i: 35 fib: 9227465
main <<< i: 36 fib: 14930352
main <<< i: 37 fib: 24157817
main <<< i: 38 fib: 39088169
main <<< i: 39 fib: 63245986
main <<< i: 40 fib: 102334155
main <<< i: 41 fib: 165580141
main <<< i: 42 fib: 267914296
main <<< i: 43 fib: 433494437
main <<< i: 44 fib: 701408733
main <<< i: 45 fib: 1134903170

In this example we have specified 45 for ‘n’. Our test program reads the input value and assigns it to the variable.

It seems that our program returns the first n Fibonacci numbers. You can compare the first few results with the list we just saw in this post.

At some point it seems we repeat the process but with a second implementation. The values seem to match.

    /**
     * Test scaffold
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read n ****
        int n = Integer.parseInt(br.readLine().trim());

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< n: " + n);

        // **** generate and display Fibonacci number(s) ****
        for (int i = 1; i <= n; i++)
            System.out.println("main <<< i: " + i + " fib0: " + fib0(i));

        // ???? ????
        System.out.println();

        // **** generate and display Fibonacci number(s) ****
        for (int i = 1; i <= n; i++)
            System.out.println("main <<< i: " + i + " fib: " + fib(i));
    }

The test code appears to match closely the description for the run of the program.

We read the input value and assign it to variable ‘n’.

We then call a loop from 1 to n inclusive and return the associated Fibonacci number. The first implementation of the method / function of interest is fib0().

We then repeat the process this time calling function / method fib().

    /**
     * Generate fibonacci number.
     * Recursive call.
     * Simple code but very ineficient.
     * Try it with n = 50
     * 
     * Time: O(2^n) Space: O(n)
     */
    static int fib0(int n) {

        // **** base case ****
        if (n <= 2)
            return 1;

        // **** recursion ****
        return fib0(n - 2) + fib0(n - 1);
    }

This function is quite simple and follows a perfect recursive approach. We determine a base case and then a recursive call is made. Since a Fibonacci number is obtained by adding the two previous Fibonacci numbers, this approach seems to be exactly what the doctor ordered.

If you copy the code to your favorite IDE and execute the first method, you should notice something. If you enter 10 as input the results appear almost instantly. But as you start increasing ‘n’, say 45 as we saw in the previous screen capture, the last few values take longer and longer to print.

The problem is with the call stack. The video I am watching provides a nice explanation of why the code might be elegant but is quite inefficient. Take a look at the time complexity which is shown in the comments section.

    /**
     * Generate fibonacci number.
     * Entry call.
     */
    static int fib(int n) {

        // **** sanity checks ****
        if (n <= 2)
            return 1;

        // **** initialization ****
        int[] callCounter   = new int[] {0};
        int[] memo          = new int[n];
        memo[0] = memo[1]   = 1;

        // **** start recursion ****
        fib(n, memo, callCounter);

        // ???? ????
        //System.out.println("fib <<< callCounter: " + callCounter[0]);
        //System.out.println("fib <<< memo: " + Arrays.toString(memo));

        // **** return answer ****
        return memo[n - 1];
    }

This is the entry point for our second implementation.

We start by performing a sanity check. It makes sense because the first two Fibonacci numbers are 1.

We then declare a call counter which is used to count the number of times we make a recursive call. Note that I removed the same argument to the implementation of fib0(). You might want to experiment with the call stack using a diagram and fully understand why something needs to be done in order to speed up the fib0() recursive call.

In the fib() function we use the common dynamic programming technique of memoization. The technique is to store the results of computation that have already been performed in order to reduce the call stack and run time.

After the declaration of the memo array we initialize the first two entries.

We then call a recursive method with three arguments. Note that the call has a third argument that is used to keep track of the number of times the recursive call is invoked.

After recursion, we find our result in the last entry of the memo array.

    /**
     * Generate fibonacci number.
     * Recursive call with memoization.
     */
    static int fib(int n, int[] memo, int[] callCounter) {

        // ???? ????
        callCounter[0] += 1;

        // **** base case ****
        if (n <= 1)
            return 1;

        // **** generate this value (if needed) ****
        if (memo[n - 1] == 0)
            memo[n - 1] = fib(n - 1, memo, callCounter);

        // **** generate this value (if needed) ****
        if (memo[n - 2] == 0)
            memo[n - 2] = fib(n - 2, memo, callCounter);

        // **** return result  ****
        return memo[n - 1] + memo[n - 2];
    }}

This is the recursive call that makes use of memoization.

We first have a base case.

Next we check if the value in n – 1 of the memo array has been set. If not, we compute it recursively.

The same holds true for the value in n – 2of the memo array has been set. If so we use it without having to incur is a long call stack associate with additional execution time.

We then just return the result.

Make sure you run the code showing the callCounter in both functions. It is amazing how much space and execution time can be saved using memoization.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.