The Fibonacci series is a very famous series in mathematics. Each number in the sequence is the sum of the two previous numbers. So, the sequence goes as 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The mathematical equation describing it is
An+2= An+1 + An.
We can generate the Fibonacci sequence using many approaches. In this tutorial I will show you how to generate the Fibonacci sequence in Python using a few methods.
Generate Fibonacci sequence (Simple Method)
In the Fibonacci sequence except for the first two terms of the sequence, every other term is the sum of the previous two terms. The first two numbers of the Fibonacci series are 0 and 1. From the 3rd number onwards, the series will be the sum of the previous 2 numbers.
#Program to generate the Fibonacci Sequence till n n=int(input("Enter the value of 'n': ")) #first two terms are first and second first=0 second=1 sum=0 count=1 print("Fibonacci Sequence: ") # Count should not be more then n. while(count<=n): print(sum) count+=1 first=second second=sum sum=first+second
The output of the program:
Enter the value of 'n': 10 Fibonacci Sequence: 0 1 1 2 3 5 8 13 21 34 $
Generate Fibonacci sequence recursively
In this approach, we will recursively call the function and calculate the Fibonacci sequence. We will calculate the recursive sum of the previous two numbers (number-2) and (number-1).
#Program to generate Fibonacci sequence recursively def Fibonacci(Number): if(Number==0): return 0 elif(Number==1): return 1 else: return (Fibonacci(Number-2)+Fibonacci(Number-1)) #return the sum of two prevous terms n=int(input("Enter the value of 'n': ")) print("Fibonacci Sequence:") for n in range(0, n): print(Fibonacci(n))
The output of the above program:
Enter the value of 'n': 10 Fibonacci Sequence: 0 1 1 2 3 5 8 13 21 34
Dynamic Programming Approach
In this approach, we store the previous values and calculate the current value. We are using a list to store the Fibonacci series. Both, the recursive approach and dynamic approach are the same, but the difference is that we are storing the value of
n-2 for each value between
# Program to generate fibonacci sequence using dynamic programming approach def fib_dp(num): arr=[0,1] print("Fibonacci Sequence: ") if num==1: print('0') elif num==2: print('[0,','1]') else: while(len(arr)<num): #length of list should be less then 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] #New term is equal to sum of two previous terms. print(arr) return arr[num-2] n=int(input("Enter the value of 'n': ")) fib_dp(n)
Enter the value of 'n': 13 Fibonacci Sequence: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
In this tutorial, we learned 3 approaches to create Fibonacci sequence. In terms of space complexity, the first approach is the best as we don’t require any extra space related to the data structure.
The other two approaches will require using data structures, in the third approach we are using the list to store all the Fibonacci sequence.
In the second method, recursion uses a stack data structure for the function calls. The first and third approaches will require equal time to execute the program.