The Fibonacci sequence is named after the Italian mathematician Leonardo of Pisa also known as Fibonacci. Although the sequence was described earlier in Indian mathematics, he introduced it to the Western European mathematics. By definition the first two numbers of the infinite sequence is either 0 and 1 or 1 and 1, and every other preceding number is the sum of the two previous numbers.
Fibonacci Sequence: 1,1,2,3,5,8,13,21,….
Modern Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21,…
The Fibonacci Sequence is defined by the following recurrence relation:
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)
Don’t be over whelmed by the recurrence relation above. Fib(n) is just a function similar to f(x), Fib is short for Fibonacci. Fib(0) is a Fibonacci function with input 0, and outputs the value 0, and is considered one of the base cases because it returns a specific constant. Fib(1) is a Fibonacci function with input 1, and it outputs the value 1, it is another base case of the Fibonacci function. Now for the tricky part Fib(n) is the recursive case of the Fibonacci function with some arbitrary input ’n’ it is equal to Fib(n-1) + Fib(n-2). Recursive just means it’s a function that calls itself or is defined by itself. So if for example n = 2, then the function would give us the following:
Fib(2) = Fib(2–1) + Fib(2–2)
= Fib(1) + Fib(0)
= 1 + 0
We see that given n=2, the recursive function gives us the value 1. So the input of ’n’ is the index of the Fibonacci number. Let’s take a look at an example.
Fibonacci Sequence: 0,1,1,2,3,5,8,13
Index of Sequence_: 0,1,2,3,4,5,6
This means if we input the value n=0 we get the Fibonacci number 0, if we input the value n=6 into our algorithm, we get back the Fibonacci number 8. That is how simple the algorithm is, now we can write some code for the Fibonacci sequence. The user will input some index, we are calling the variable ’n’, and loop through all of the numbers from 0 to n, and print the Fibonacci numbers up to index ’n’, for example if the input for n=6, then we want to print out 0,1,1,2,3,5,8. If the input value for n=3, then we want to print out 0,1,1,2. You can get the code on my GitHub or below! You can also see me creating this program on YouTube or in the video below.
/* C Program for a recursive fibonacci function
*/ #include< stdio.h >
int n, i = 0, c;
for ( c = 1 ; c <= n ; c++ )
int Fibonacci(int n)
if ( n == 0 )//Base Case 1
else if ( n == 1 )//Base Case 2
else// Recursive Case
return ( Fibonacci(n-1) + Fibonacci(n-2) );
Fibonacci Running Time
Time Complexity: T(n) = T(n-1) + T(n-2) + C , where C is a constant
T(n) = O(1.6180)^n
1.6180 is also called the golden ratio and it’s appearance can be found through out nature: face, body, flower petals, animals, fibonacci series, shell, galaxies, arts, architecture etc. You can read more about golden ratio here: Golden Ratio in Math and here.
Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )
Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:
Video Tutorials on Recurrence Relation:
Video Tutorial on Algorithm Analysis:
Time complexity of recursive Fibonacci program - GeeksforGeeks
The Fibonacci numbers are the numbers in the following integer sequence 0, 1, 1, 2, 3, 5, 8, 13... Mathematically…
Program for Fibonacci numbers - GeeksforGeeks
The Fibonacci numbers are the numbers in the following integer sequence. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…