 # Fibonacci Sequence In Python

In this article, we are going to write program for the Fibonacci sequence in python. Additionally, we will also create a program that tells whether a number is a Fibonacci number or not. ## Introduction To Fibonacci Sequence

A Fibonacci sequence is a series of numbers in which each number is the sum of the last two numbers in the sequence. The first two numbers in the sequence are 0 and 1.

The sequence was named after the Italian mathematician Leonardo Pisano Fibonacci, who introduced it in 1202 in his book.

The sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …

Starting from 0 and 1, the next number is (0 + 1) = 1, and the next number is (1 + 1) = 2, and so on. ## Fibonacci sequence using for loop

Let's see how we can generate the Fibonacci sequence using for loop.

Algorithm

1. Initialize prev and curr to 0 and 1 respectively. These are the first two numbers in the sequence.
2. Create a for loop to iterate through the range of 0 to n.
3. For each number in the sequence, calculate the next number by adding the previous two numbers in the sequence.
4. Swap the number. Make the current number the previous number and the newly generated number the current number.
5. Return the previous number.
6. Later you can print the sequence.
``````# Fibonacci series using for loop
def fibonacci(n):
prev, curr = 0, 1

# calculate nth Fibonacci number
for i in range(n):
num = curr
curr = prev + curr
prev = num
return prev

# print the Fibonacci series
for i in range(10):
print(f"{i}th Fibonacci number is {fibonacci(i)}")``````

Output:

```0th Fibonacci number is 0
1th Fibonacci number is 1
2th Fibonacci number is 1
3th Fibonacci number is 2
4th Fibonacci number is 3
5th Fibonacci number is 5
6th Fibonacci number is 8
7th Fibonacci number is 13
8th Fibonacci number is 21
9th Fibonacci number is 34```

## Fibonacci sequence using recursion

The recursion is a technique to solve a problem by calling a function within itself. The function calls itself until the base case is reached.

Here the base case is when the number is 0 or 1.

Let's first see the Python program to generate the Fibonacci series using recursion then we will look at its working.

``````# fibonacci series using recursion
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)

# call function
for i in range(5, 13):
print(f"{i}th Fibonacci number is {fibonacci(i)}")``````

Output:

```5th Fibonacci number is 5
6th Fibonacci number is 8
7th Fibonacci number is 13
8th Fibonacci number is 21
9th Fibonacci number is 34
10th Fibonacci number is 55
11th Fibonacci number is 89
12th Fibonacci number is 144```

Here is how the function works:

If the number is 0 or 1, then the number is returned (which is the base case). When the number is greater than 1, the function calls itself again. For example, if number is 2 then else part of the function is executed and return fibonacci(2 - 1) + fibonacci(2 - 2), which is 1 + 0 = 1.

Similarly, if number is 3 then else part of the function is executed and return fibonacci(3 - 1) + fibonacci(3 - 2), which is fibonacci(2) + fibonacci(1), which is 1 + 1 = 2, and so on. ## Fibonacci sequence using memoization

The recursive function discussed above is terribly slow for large numbers. The reason is that because of recursion the function has to calculate the Fibonacci value of the same number multiple times at the different stages of the function execution. Which is a very expensive operation.

You can see in the above figure, that to calculate the 5th Fibonacci number f(5), the execution calculates f(2) 3 times, f(3) 2 times, and f(4) for 1 time. You can imagine how complex the calculation gets as soon as the number gets bigger.

We can solve this problem if we store the calculated value of f(n). So that we don't have to calculate the same value again.

Here comes the memoization. It is a technique to store the result of a function call and use it later.

The value store is in a dictionary. The key is the number and the value is the Fibonacci value.

``````# fibonacci series using memoization
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
else:
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]

# call function
for i in range(50, 55):
print(f"{i}th Fibonacci number is {fibonacci(i)}")``````

Output:

```50th Fibonacci number is 12586269025
51th Fibonacci number is 20365011074
52th Fibonacci number is 32951280099
53th Fibonacci number is 53316291173
54th Fibonacci number is 86267571272```

You can also calculate the Fibonacci number using this for larger values. For example, the 100th Fibonacci number is 354224848179261915075.

## Identify the Fibonacci number

According to Binet's formula, a number N is a Fibonacci number if and only if one or both of 5 × N × N + 4 or 5 × N × N + 4 is a perfect square. (source: Wikipedia)

We can use the above formula to identify the Fibonacci number.

``````# identify the Fibonacci number
from math import sqrt

def is_fibonacci(n):
return sqrt(5 * n * n + 4) % 1 == 0 or sqrt(5 * n * n - 4) % 1 == 0

# check if the number is Fibonacci
for i in range(1, 100):
if is_fibonacci(i):
print(f"{i} is a Fibonacci number")``````

Output:

```1 is a Fibonacci number
2 is a Fibonacci number
3 is a Fibonacci number
5 is a Fibonacci number
8 is a Fibonacci number
13 is a Fibonacci number
21 is a Fibonacci number
34 is a Fibonacci number
55 is a Fibonacci number
89 is a Fibonacci number```

## Conclusion

We have created 3 different python programs to calculate the Nth factorial number. The first program is using for loop, the second program is using recursion and the third program is using memoization.

We have also created a program to identify the Fibonacci number.

• 100th Fibonacci number is 354224848179261915075
• 200th Fibonacci number is 573147844013817084101
• Binet formula is used to identify whether a number is a Fibonacci number or not.