Interview questions regarding the Fibonacci series are very popular, so there are very few developers that haven't heard of or computed the sequence in one way or another. They are defined by the following relation:
But why is that? Why does everyone love the Fibonacci Numbers so much? During a series of articles, I am going to present some of the magic behind this sequence and why I think they are so popular, as well as compare some ways of computing them.
Properties
They appear in natural settings
One beautiful example of where exactly numbers from the Fibonacci Series appear in nature is the number of petals some flowers have. Some examples:
- Irises typically have 3 petals
- Buttercups have 5 petals
- Michaelmas Daisies / New York Asters (Purple Daisies) usually have 55 petals
Human bodies exhibit Fibonacci characteristics
The Fibonacci series goes like this: 1, 1, 2, 3, 5, 8 and so on. Well, we have 2 hands. Each with 5 fingers. Each finger has 3 sections, separated by 2 knuckles. All of these fit right in.
They have very interesting mathematical properties
One interesting property of the Fibonacci Sequence is that any integer can be written as a unique sum of one or more non-consecutive Fibonacci numbers (Zeckendorf's theorem). Later during the series, we will see a very simple algorithm that computes this.
Another remarkable property is this:
- where gcd denotes the greatest common divisor.
Computing
Naive recursive approach
The most basic way of computing a specific Fibonacci number is by using the recursive formula directly - more specifically, by writing a recursive function. I'll attach a simple C++ snippet of the function:
int F(int n) {
if(n <= 1) return n;
return F(n-1) + F(n-2);
}
However, when examining the recursive tree of this function, we get something like this:
We can clearly see that the function is called multiple times for some numbers, such as F(2) or F(3) - this is one of the possible drawbacks of recursion and teaches us that we should be careful when writing recursive functions as they can "backfire".
Let's analyze this approach in terms of complexity. The recurrence relation is:
(the time needed for computing F(n) equals the time needed for F(n-1) + F(n-2) and some constant)
Looking at the recurrence relation, we guess that the relation might be exponential. So, let's say that:
That leads us to:
(we won't take the constant into account) When diving by x^(n-2) and move all the terms to the left hand side, we get:
By solving the equation, we get 2 possible solutions: x = 1.62 or x = -0.62. As x is a positive integer, the final solution is x = 1.62.
So, the time complexity of the algorithm above is ~ O((1.62)^n)), which is exponential.
Recursive approach with memoization
This approach can be slightly improved in order to get the time complexity a lower by using an additional array in which we "remember" the numbers we have already computed:
int *fib;
int fRec(int n) {
if(n <= 1) return n;
return (fib[n] != 0) ? fib[n] : (fib[n] = fRec(n-1) + fRec(n-2));
/// if we have already computed the n-th fibonacci number, return it.
/// else, "remember" the result for later use.
}
int F(int n) {
if(fib != nullptr) delete[] fib; /// deleting the whole array
fib = new int[n+1]; /// dynamically allocating memory for a new array
for(int i = 1; i <= n; i++) /// setting all the elements to 0
fib[i] = 0;
return fRec(n-1) + fRec(n-2);
}
The dynamic memory allocation can be skipped if we know approximately how big n is going to be.
This concept of "remembering" results of recursive calls is called memoization and can be used to improve run times of several algorithm types. The time complexity of this algorithm is ~ O(n), which is much better than the non-memoization approach. There is also an O(n) space complexity.
That's it for this article. I will continue presenting other properties and methods of computing the Fibonacci numbers during 1 or 2 more articles, so stay tuned!
But, after all, why are Fibonacci numbers so popular in computer science? Well, as you have seen above, they are a pretty simple concept which we can use in order to understand some programming concepts (not only recursion and memoization, but others that we will see in other articles).
Latest comments (1)
Bagi un ceseu?