Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags


How to implement the Fibonacci sequence in Python

Educative Answers Team

The Fibonacci Sequence is the series of numbers:

0,1,1,2,3,5,8,13,21,34,...0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The series starts with 00 and 11 as the first two numbers in the series. The next number in the series is found by summing the two numbers before it.

For example:

  • The third number in the sequence, 11, is found by adding the two numbers before it (0+1)(0+1).
  • The fourth number in the sequence, 22, is found by adding the two numbers before it (1+1)(1+1).

Implementing the Fibonacci Sequence

Fibonacci Sequence can be implemented both iteratively and recursively in Python.

For both examples, try changing the value of the argument passed to the function to print out more numbers in the sequence.

Iterative implementation

def fib(number_of_terms):
   counter = 0

   first = 0
   second = 1
   temp = 0
   while counter <= number_of_terms:
      temp = first + second
      first = second
      second = temp
      counter = counter + 1

# Driver Code

In the above implementation, The code prints the first value on each iteration of the loop. Each iteration calculates the next value by summing the previous two values and then updates the values of first and second. The time complexity of the above iterative implementation is O(n)O(n).

Recursive Implementation

%0 node_1 fib(6) node_2 fib(5) node_1->node_2 node_3 fib(4) node_1->node_3 node_1560342921469 fib(4) node_2->node_1560342921469 node_1560342953228 fib(3) node_2->node_1560342953228 node_1560342996739 fib(3) node_1560342921469->node_1560342996739 node_1560342958693 fib(2) node_1560342921469->node_1560342958693 node_1560342990245 fib(2) node_1560342996739->node_1560342990245 node_1560343031028 fib(1) node_1560342996739->node_1560343031028 node_1560343051673 fib(1) node_1560342990245->node_1560343051673 node_1560343038312 fib(0) node_1560342990245->node_1560343038312
Calculating the 6th Fibonacci number.
def fib(term):
   if term <= 1:
       return (term)
       return (fib(term-1) + fib(term-2))

# Change this value to adjust the number of terms in the sequence.
number_of_terms = 10
for i in range(number_of_terms):

The above program computes the Fibonacci value by calling itself with a lesser value several times. The termination condition for this is reached when term == 0 and term == 1. The time complexity for this solution is O(2n)O(2^n).


Copyright ©2022 Educative, Inc. All rights reserved

View all Courses

Keep Exploring