In the Fibonacci series, each number is the sum of the two previous numbers. The first two numbers in the Fibonacci series are 0 and 1.
The sequence Fn of Fibonacci numbers is defined by the recurrence relation:
Fn = Fn-1 + Fn-2
with seed values
F0 = 0 and F1 = 1.
So if n =7, the Fibonacci series can look like this:
F7 = 0 1 1 2 3 5 8
Methods to get the nth Fibonacci number:
Recursive way to find an nth Fibonacci number.
#include<stdio.h> int Fibonacci( int n) { if(n < 0) //check positive number return -1; else if ( n == 0 ) return 0; else if ( n == 1 ) return 1; else return ( Fibonacci(n - 1) + Fibonacci(n - 2) ); } int main() { int n = 0, fibnumber = 0; printf("\n Enter Number to find nth Fibonacci Number = "); scanf("%d", &n); fibnumber = Fibonacci(n); if(fibnumber < 0) { printf("Please Enter Positive number\n\n"); } else { printf("\n %d Fibonacci Number = %d\n\n", n, fibnumber); } return 0; }
Output:
Code Analysis
- If (n < 0) – check whether the given number is +ve or not. If it is TRUE, the function will return an error message.
- If (n== 0) – check whether the given number is 0 or not. If it is TRUE, the function will return Zero.
- If (Number == 1) – check the specified number is equal to 1 or not. If it is TRUE, the function will return One.
- If the number is greater than 1, then the recursive operation is performed.
Time Complexity: T(n) = T(n-1) + T(n-2) .
You can observe the recursion tree that this implementation does a lot of repeated work. So it is not a good way to find the nth Fibonacci number.
fib(5) / fib(4) fib(3) / / fib(3) fib(2) fib(2) fib(1) / / / fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / fib(1) fib(0)
Optimize way to find an nth Fibonacci number
#include<stdio.h> int Fibonacci(int n) { int f0 = 0, f1 = 1, f =0, i=0; if( n == 0) return f0; for (i = 2; i <= n; i++) { f = f0 + f1; f0 = f1; f1 = f; } return f1; } int main () { int n = 0; int fn = 0; printf("\n Enter Number to find nth Fibonacci Number = "); scanf("%d", &n); if(n < 0) { printf("Please Enter Positive number\n\n"); return -1; } fn = Fibonacci(n); printf("\n %d Fibonacci Number = %d\n\n", n, fn); return 0; }
In the above code, simply we are using the concept Fn = Fn-1 + Fn-2 .
Recommended Posts for you:
- How to use if condition.
- C language character set.
- Elements of C Language.
- Data type in C language.
- Operators with Precedence and Associativity.
- How to pass an array as a parameter?
- Memory Layout in C.
- File handling in C, In a few hours.
- Replacing nested switches with the multi-dimensional array
- How to access a two-dimensional array using pointers?
- Brief Introduction of switch case in C.
- 100 C interview Questions.
- Function pointer in c, a detailed guide.
- How to use the structure of function pointer in c language?
- Function pointer in structure.
- Pointer Arithmetic in C.
- Brief Introduction of void pointer in C.