In Mathematics, Fibonacci Series in 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. Through the course of this blog, we will learn how to create the Fibonacci Series in Python using a loop, using recursion, and using dynamic programming.
While there are ample resources available online to help you understand the subject, there’s nothing quite like a certificate. Check out Great Learning’s PG program in Data Science and Business Analytics to upskill in the domain. This course will help you learn from a top-ranking global school to build job-ready Data Science skills. This 6-month program offers a hands-on learning experience with top faculty and mentors. On completion, you will receive a Certificate from The University of Texas at Austin.
- What is Fibonacci Series
- Fibonacci Series Logic
- Fibonacci Series Formula
- Fibonacci Spiral
- Fibonacci series algorithm
- Fibonacci Series in Python
a. Fibonacci Series Using loop
b. Fibonacci Series using Recursion
c. Fibonacci Series using Dynamic Programming
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, which roughly means “Son of Bonacci”. Fibonacci was not the first to know about the sequence, it was known in India hundreds of years before!
Fibonacci Series is a pattern of numbers where each number is the result of addition of the previous two consecutive numbers. First 2 numbers start with 0 and 1. The third numbers in the sequence is 0+1=1. The 4th number is the addition of 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, …
Logic of Fibonacci Series
The next 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 term number “n”
xn-1 is the previous term (n-1)
xn-2 is the term before that
An interesting property about these numbers is that when we make squares with these widths, we get a spiral. 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 written in the bigger square is a sum of the next 2 smaller squares. This is a perfect arrangement where each block 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 Palindrome in Python
Fibonacci Series Algorithm
- 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
- 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
- Initalize arr and arr 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 the value is required. Therefore, we use dynamic programming in such cases. The conditions for implementing dynamic programming are
1. overlapping sub-problems
2. optimal substructure
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)
def fib_rec(n): if n == 1: return  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)
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)<num): arr.append(0) if(num==0 or num==1): return 1 else: arr=0 arr=1 for i in range(2,num): arr[i]=arr[i-1]+arr[i-2] print(arr) return arr[num-2] fib_dp(5)
If you found this blog helpful, learn artificial intelligence and power ahead in your career. Learn from the best in the industry and also gain access to mentorship sessions and career assistance.
- Factorial of a number in Python
- Palindrome in Python
- Convert List to String in Python
- Eval Function in Python