Image for post
Image for post

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,…

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
= 1

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.

Code:

/* C Program for a recursive fibonacci function 
by:randerson112358
*/
#include< stdio.h >

int Fibonacci(int);

main()
{
int n, i = 0, c;

scanf("%d",&n);

printf("Fibonacci series\n");

for ( c = 1 ; c <= n ; c++ )
{
printf("%d\n", Fibonacci(i));
i++;
}

return 0;
}

int Fibonacci(int n)
{
if ( n == 0 )//Base Case 1
return 0;
else if ( n == 1 )//Base Case 2
return 1;
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

Fun Fact:
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:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Recurrence Relation:

Image for post
Image for post

RESOURCES:

MIT Paper:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store