Lately I have not had the time to write in this blog. For the past several months I have been getting up seven days a week, no later than 04:30 AM. I am taking a specialization on Big Data and machine learning. Loving every minute but it does not leave time at the end of the day to sit down and do something in order to be able to write a post.
A few days ago I ran into a video on YouTube regarding Fibonacci sequences. I am not interested in the actual code presented. I just went ahead and wrote the code that I thought was needed. While watching the video, the presenter briefly explained how numbers are produced in a Fibonacci sequence. The idea is quite simple. Starting with a zero and followed by a one, the next number is computed by summing the two previous numbers. Following is a list of the first few numbers in the sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... <=== Fibonacci sequence 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... <=== sequence number
I am starting the sequence number with zero (0). The first two numbers in the Fibonacci sequence are 0 and 1. The third one, 
indexed 1 is 1 due to the fact that 0 + 1 = 1. The fourth number labeled 3 is 2 due to the fact that 1 + 1 = 2. I am sure you get the drift.
If you are a software developer / computer scientist you are familiar with the concept or recursion. Using recursion is somewhat viewed as being elegant and having a good handle of algorithms. After reading the rest of the post I will ask your opinion regarding the blind use of recursion or any other algorithm for that matter.
In general, any code written as a recursion can be written as a set of one or more loops.
The presenter decided to use recursion to generate the specified position in a Fibonacci sequence using recursion. In order to avoid repeating some operations, the use of an array holding previously computed numbers was suggested. The idea being that when the position of the number was specified, the function would look if the value was in the array. If not, it would look backwards for the last used position. If the two consecutive values were available, the algorithm would start there and proceed until the specified position was generated. To clarify, assume the position specified by the user was 50. The algorithm would look back until a set of two consecutive numbers were located e.g., 233 and 377 at locations 13 and 14 respectively. At that time the algorithm would proceed to compute the required Fibonacci number for the specified position e.g., 50.
Allow me to present set of three screen captures from the Eclipse IDE:
pos: 48
FibNonRec: 4807526976
time: 0 ms
FibRec: 4807526976
time: 25070 ms
pos: 50
FibNonRec: 12586269025
time: 1 ms
FibRec: 12586269025
time: 65502 ms
pos: 52
FibNonRec: 32951280099
time: 0 ms
FibRec: 32951280099
time: 172753 ms
The first set shows the times taken by two algorithms to generate entry 48 in the series. Take a look at the second time of 25,070 ms which is roughly 27 seconds. The next set represents the time it takes to generate the number is position 50. This one took 65,502 ms which is about 66 seconds. The pass to generate the number at position 52 took 172,753 ms which represents about 2.89 minutes (not seconds). That is a long time and we just generated a single number from scratch. Imagine position 60 or 100. Besides the time it would take (in the hour range), most programming languages would not be able to deal with the size of the number being generated. In this case I used Java 8. If I needed to compute such large numbers I would have to use a special library that could handle such large numbers.
Did you pay attention to the first time in each set? The times are no more than a millisecond to produce the same result as the second operation in each set. My question, if you are able to use the first algorithm, would you consider optimizing the second one? Seems like the author of the YouTube video would. This behavior is not isolated to the video. In practice I seem several times a week approaches and implementations that do not fall within what I would call acceptable. To dismiss it simply one could say that senior developers are able to come up with simple and elegant solutions to problems, while junior developers tend to produce complex solutions to simple problems.
Allow me to show you the code behind what generated the output we just discussed:
package canessa.finonacci;
public class Solution {
/*
*
*/
static void DumpArray(int[] arr) {
System.out.print("[ ");
for (int val : arr) {
System.out.print(String.format("%03d ", val));
}
System.out.println("]");
}
/*
* Compute a Fibonacci number in a recursive fashion.
*/
static long FibRec(int pos) {
// **** end recursion ****
if (pos <= 0) {
return 0;
}
if (pos <= 2) {
return 1;
}
// **** recursion ****
return FibRec(pos - 1) + FibRec(pos - 2);
}
/*
* Compute a Fibonacci number in a non-recursive fashion.
*/
static long FibNonRec(int pos) {
if (pos <= 0) {
return 0;
} else if (pos <= 2) {
return 1;
}
long[] arr = new long[pos + 1];
arr[0] = 0;
arr[1] = 1;
arr[2] = 1;
for (int i = 2; i <= pos; i++) {
arr[i] = arr[i - 2] + arr[i - 1];
}
return arr[pos];
}
/*
* The Fibonacci numbers are the numbers in the following integer sequence,
* called the Fibonacci sequence, and characterized by the fact that every
* number after the first two is the sum of the two preceding ones:
*
* 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...
*
* Often, especially in modern usage, the sequence is extended by one more
* initial term:
*
* 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...
* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
*/
public static void main(String[] args) {
final int pos = 48;
System.out.println(" pos: " + pos);
// **** non-recursive approach ****
long startTime = System.currentTimeMillis();
System.out.println("FibNonRec: " + FibNonRec(pos));
long endTime = System.currentTimeMillis();
System.out.println(" time: " + (endTime - startTime) + " ms");
// **** recursive approach ****
startTime = System.currentTimeMillis();
System.out.println(" FibRec: " + FibRec(pos));
endTime = System.currentTimeMillis();
System.out.println(" time: " + (endTime - startTime) + " ms");
}
}
The main() function shows that the FibNonRec() function will be called to generate the Fibonacci number for position 48. The second function FibRec() should generate the same result as we verified in the output screen. As you might have figured out, the first function generates the Fibonacci number using a loop. The second one uses the more elegant and slower as molasses dripping in February approach.
Please note that with some additional effort we could have used a global or a parameter with an array to generate and store the Fibonacci numbers. The FibNonRec() function might not look as elegant and fancy as the recursive approach, but there is no need to optimize it when compared with the other one.
When starting a software development task, take the necessary time to understand what the requirements are. If in doubt, ask for clarification(s). Then write some tests to verify the operation of the software to be written. It is then that you should try, time permitting, several approaches in order to select the best for your product.
If you have comments or questions on this or any other post in this blog, please leave me a message.
Enjoy learning;
John
Follow me on Twitter: @john_canessa