# Fibonacci Series in Python | Algorithm, Codes, and more

In Mathematics, the Fibonacci Series is a sequence of numbers such that each number in the series is a sum of the preceding numbers. The series starts with 0 and 1. This blog will teach us how to create the Fibonacci Series in Python using a loop, recursion, and dynamic programming. Check out this Python for beginners course we have prepared for you to brush up your skils.

Leonardo Pisano Bogollo was an Italian mathematician from the Republic of Pisa and was considered the most talented Western mathematician of the Middle Ages. He lived between 1170 and 1250 in Italy. “Fibonacci” was his nickname, meaning “Son of Bonacci.” Fibonacci was not the first to know about the sequence, and it was known in India hundreds of years before!

## What is Fibonacci Series?

Fibonacci Series is a pattern of numbers where each number results from adding the last two consecutive numbers. The first 2 numbers start with 0 and 1, and the third number in the sequence is 0+1=1. The 4th number is the addition of the 2nd and 3rd number, i.e., 1+1=2, and so on.
The Fibonacci Sequence is the series of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

## The logic of the Fibonacci Series

The following number is a sum of the two numbers before it.
The 3rd element is (1+0) = 1
The 4th element is (1+1) = 2
The 5th element is (2+1) = 3

## Fibonacci Series Formula

Hence, the formula for calculating the series is as follows:
xn = xn-1 + xn-2 ; where
xn is the term number “n”
xn-1 is the previous term (n-1)
xn-2 is the term before that

## Fibonacci Spiral

An exciting property about these numbers is that we get a spiral when we make squares with these widths. A Fibonacci spiral is a pattern of quarter-circles connected inside a block of squares with Fibonacci numbers written in each of the blocks. The number in the giant square is a sum of the following 2 smaller squares. This is a perfect arrangement where each block is denoted a higher number than the previous two blocks. The main idea has been derived from the Logarithmic pattern, which also looks similar. These numbers are also related to the golden ratio.

Learn how to find if a String is a Palindrome in Python

## Fibonacci Series Algorithm

### Iterative Approach

• Initialize variables a,b to 1
• Initialize for loop in range[1,n) # n exclusive
• Compute next number in series; total = a+b
• Store previous value in b
• Store total in a

### Recursive Approach

• If n equals 1 or 0; return 1
• Else return fib(n-1) + fib(n-2)

### Dynamic Programming Approach

• Initialize an array arr of size n to zeros
• If n equals 0 or 1; return 1 Else
• Initialize arr[0] and arr[1] to 1
• Run for loop in range[2,num]
• Compute the value arr[I]=arr[I-1] +arr[I-2]
• The array has the sequence computed till n

Hence, the solution would be to compute the value once and store it in an array from where it can be accessed the next time it is required. Therefore, we use dynamic programming in such cases. The conditions for implementing dynamic programming are
1. overlapping sub-problems
2. optimal substructure

### Iterative Approach

```def fib_iter(n):
a=1
b=1
if n==1:
print('0')
elif n==2:
print('0','1')
else:
print("Iterative Approach: ", end=' ')
print('0',a,b,end=' ')
for i in range(n-3):
total = a + b
b=a
a= total
print(total,end=' ')
print()
return b

fib_iter(5)

```

TEST THE CODE

Output : Iterative Approach : 0 1 1 2 3

### Recursive Approach

```def fib_rec(n):
if n == 1:
return [0]
elif n == 2:
return [0,1]
else:
x = fib_rec(n-1)
# the new element the sum of the last two elements
x.append(sum(x[:-3:-1]))
return x
x=fib_rec(5)
print(x)

```

TEST THE CODE

Output – 0, 1, 1, 2, 3

### Dynamic Programming Approach

```There is a slight modification to the iterative approach. We use an additional array.

def fib_dp(num):
arr = [0,1]
print("Dynamic Programming Approach: ",end= ' ')
if num==1:
print('0')
elif num==2:
print('[0,','1]')
else:
while(len(arr)```

TEST THE CODE

Output – 0, 1, 1, 2, 3

## FAQs

What are the properties of the Fibonacci series?

The Fibonacci series has several properties, including:
-Each number in the series is the sum of the two preceding numbers.
-The first two numbers in the series are 0 and 1.

What are some applications of the Fibonacci series?

The Fibonacci series has several applications, including:
-It can be used to model the growth of populations of animals.
-It can be used to calculate the Golden Ratio, which is used in architecture and art.
-It can be used in computer programming to generate efficient algorithms.

What is the time complexity of generating the Fibonacci series?

The time complexity of generating the Fibonacci series is O(n).

What is the space complexity of storing the Fibonacci series?

The Fibonacci series is an infinite sequence, so the space complexity is infinite.