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