## Fibonacci Series Program

The following program can be used to generate the Fibonacci series in Python.

```
N = int(input("Enter the number of terms : "))
# first two terms are f1, f2 equal to 0 and 1 respectively
f1, f2 = 0, 1
count = 0
# checking for invalid inputs
if(N <= 0):
print("Invalid Input, Kindly enter number greater than 0")
# if only one number in the sequence
elif(N == 1):
print("Generating Fibonacci Sequence upto ", N, ": ")
print(f1)
# for all the other cases, i.e. when N > 1
else:
print("Generating Fibonacci sequence upto ", N, ": ")
while count < N:
print(f1)
fth = f1 + f2
# swapping the values for f1 and f2
f1 = f2
f2 = fth
count += 1
```

The above program will generate the Fibonacci Series in Python. The Fibonacci series in Python can also be generated using Recursion as follows:-

```
# Python program to display the Fibonacci sequence using Recursion
def fibonacci_recur(n):
if n <= 1:
return n
else:
# recursive call for (n-1) and (n-2)
return(fibonacci_recur(n-1) + fibonacci_recur(n-2))
count = input("Enter number of terms: ")
# check if the number of terms is valid
if count <= 0:
print("Plese enter a positive numbee")
else:
print("Generating Fibonacci sequence upto :", count, ": ")
for i in range(count):
print(fibonacci_recur(i))
```

The time complexity will be T(n - 1) + T(n - 2) which is exponential. Alternatively, we can also use Dynamic Programming (Memoization) to generate the Fibonacci series as follows:

```
# Function for nth fibonacci number - Dynamic Programming
# Taking 1st two fibonacci nubers as 0 and 1
Fibonacci_Array = [0, 1]
def fibonacci_DP(n):
# Check is n is less than 0
if n <= 0:
print("Incorrect input")
# if the numbers of terms in the sequence are to be 1 or 2
elif n <= len(Fibonacci_Array):
return Fibonacci_Array[n - 1]
else:
temp_fib = fibonacci_DP(n - 1) + fibonacci_DP(n - 2)
# .append() is used for adding elements to the last of
# the array
Fibonacci_Array.append(temp_fib)
return temp_fib
count = int(input("Enter the number of terms"))
for i in range(1, count+1):
print(fibonacci_DP(i))
```

The time complexity will be O(N), where N is the number of terms in the Fibonacci sequence.

Program to check if a given number is a Fibonacci number or not

Also see, __Swapcase in Python__

## Approach 1

To check if a given number is fibonacci number, a simple technique is to generate Fibonacci numbers until the generated numbers are greater than or equal to the given number, ‘N.’ In other words, generate Fibonacci series in python till the generated numbers are greater than or equal to N.

**Sample Input and Output:**

```
Example 1
Input: Enter the number you want to check: 34
Output: Given number is Fibonacci number
Explanation: 34 is a Fibonacci number
Example 2
Input: Enter the number you want to check: 45
Output: No it’s not a Fibonacci number
Explanation: 45 is not a Fibonacci number
```

Program

```
N = int(input("Enter the number you want to check: "))
# variables for generating fibonacci sequence
f3 = 0
f1 = 1
f2 = 1
# 0 and 1 both are fibonacci numbers
if (N == 0 or N == 1):
print("Given number is fibonacci number")
else:
# generating the fibonacci numbers until the generated number is less than N
while f3 < N:
f3 = f1 + f2
f2 = f1
f1 = f3
if f3 == N:
print("Given number is fibonacci number")
else:
print("No it’s not a fibonacci number")
```

You can compile it with __online python compiler__.

## Approach 2

An essential property about Fibonacci numbers is that a number N is Fibonacci if and only if either one of (5N^2 + 4) or (5N^2 - 4) is a perfect square.

Sample Input and Output

```
Example 1:
Input: 6
Output: 6 is not a Fibonacci number
Explanation: 6 do not form a part of the Fibonacci series
Example 2:
Input: 233
Output: Given number is Fibonacci number
Explanation: 233 is a part of the Fibonacci series
```

Program

```
import math
# A utility function that will return true
# if the number is perfect square, else this
# will return false
def isPerfectSquare(num):
# finding the square root of num
s =int(math.sqrt(num))
return s*s == num
def isFibonacciNumber(n):
# return true if the number is fibonacci otherwise
# return false
return isPerfectSquare(5*n*n + 4) or isPerfectSquare(5*n*n - 4)
n = int(input("Enter the number you want to check : "))
if(isFibonacciNumber(n) == True):
print("Given number is fibonacci number")
else:
print(n ," is not a fibonacci number")
```

** Read about - **Strong number in c and Fibonacci Series in JavaScript

## Frequently Asked Questions

**How do you check if a number is Fibonacci or not Python?**

To check if the given number is a Fibonacci number in Python, use the following property, i.e., A number is Fibonacci if and only if 5n^2 + 4 or 5n^2 – 4 is a perfect square.

Functional implementation of the approach:

A utility function that will return true

if the number is perfect square, else this

will return false

def isPerfectSquare(num):

# finding the square root of num

s =int(math.sqrt(num))

return s*s == num

def isFibonacciNumber(n):

# return true if the number is fibonacci otherwise

# return false

return isPerfectSquare(5*n*n + 4) or isPerfectSquare(5*n*n – 4)

**Is four a Fibonacci number?**

No, 4 is not a Fibonacci number.

**Is zero a Fibonacci number?**

Yes, 0 is a Fibonacci number.

**How do you check if a number is Fibonacci or not in C?**

To check if the given number is a Fibonacci number, Use the same approach as discussed above. The code in C Programming languages is.

bool isPerfectSquare(int x)

{

int s = sqrt(x);

// will return true if x is perfect square

return (s*s == x); } int isFibonacci(int n) { return isPerfectSquare(5*n*n + 4) || isPerfectSquare(5*n*n – 4);

}

int main()

{

int num;

printf(“Enter a number”);

scanf(“%d”, &num);

if(isFibonacci(num)){

printf(“%d is a fibonacci number”, num);

}

else{

printf(“%d is not a fibonacci number”, num);

}

return 0;

}

## Conclusion

Fibonacci series is an important topic from an interview perspective in the initial stages. This blog covered an overview of basic concepts regarding the Fibonacci series, owing to which many different sets of problems can be attempted. Feel free to explore more of the Fibonacci series, practice more questions on Code Studio.

Also read: __fibonacci series in c__

*“Curiosity is the spark behind the spark of every great idea. The future belongs to the curious”. #BeCurious*