An Interest In:
Web News this Week
- March 21, 2024
- March 20, 2024
- March 19, 2024
- March 18, 2024
- March 17, 2024
- March 16, 2024
- March 15, 2024
Program for Fibonacci Numbers
What is the Fibonacci series?
The Fibonacci sequence is a sequence where the next term is the sum of the previous two terms. The first two terms of the Fibonacci sequence are 0 followed by 1.
The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21 ....
In mathematical terms,the sequence Fn of Fibonacci numbers is defined by recursion relation
Fn = Fn-1 + Fn-2
where
F0 = 0 , F1 = 1
We will discuss three ways to write the Fibonacci series program:
- Fibonacci series using recursion
- Fibonacci series using Iterative method
- Fibonacci series using Matrix Exponentiation
(1) Recursive Method:
A simple method that is a direct recursive implementation mathematical recurrence relation is given above.
//pseudo code RFib(n){ if n=0 return 0; else if n=1 return 1; else return (RFib(n-1)+RFib(n-2));}
Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.
Extra Space: O(n) if we consider the function call stack size, otherwise O(1).
(2) Iterative Method:
We can optimize the space used in Recursive Method by storing the previous two numbers only because that is all we need to get the next Fibonacci number in series.
//pseudo code IFib(n)if n=0 return 0; else if n=1 return 1; else { a <= 0; b<=1; for(i=2 to n) do { temp <= b; b<= a+b; a <= temp; }return b;
Time complexity: O(n)
Extra space: O(1)
(3) Matrix Exponentiation:
Let n > 1
Time complexity : O(log(n))
Extra space : O(log(n)) if we consider the function call stack size, otherwise O(1).
Thanks for reading
Original Link: https://dev.to/kkumargcc/program-for-fibonacci-numbers-1ce2
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To