How to Write the Fibonacci Sequence in Python

In mathematics, the Fibonacci sequence is a sequence of numbers where each number is the sum of the two preceding numbers. For example:

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

The sequence starts with 0 and 1, and we find the following number by summing the two numbers that occur before it.

In the case of the third number in the sequence, the two preceding numbers are 0 and 1, so the third number is (0 + 1) = 1.

In the case of the fourth number in the sequence, the two preceding numbers are 1 and 1, so the fourth number is (1 + 1) = 2.

Each number in the Fibonacci sequence is a Fibonacci number, F(N).

This tutorial will go through how to write the Fibonacci sequence in Python using both an iterative and recursive method.

---

Implementing the Fibonacci Sequence in Python

We can implement the Fibonacci sequence both iteratively and recursively in Python. Let’s go through how to do each with the help of some code snippets.

Iterative Implementation of the Fibonacci Sequence in Python

def fib(n):

    # first two terms
    
    n1 = 0
    
    n2 = 1
    
    counter = 0
    
    if n ≺= 0:
    
        print("Incorrect input, number cannot be negative")
    
    elif n == 1:
    
        print(f'Fibonacci sequence up to {n} is : {n1}')
    
    else:
    
        print(f'Fibonacci sequence up to n={n}: ')
    
        while counter ≺ n:
    
             print(n1)
    
             temp = n1 + n2
    
             # update values
    
             n1 = n2
    
             n2 = temp
    
             counter +=1

In the above implementation, the function uses a while loop to iteratively print each Fibonacci number up to the specified number of terms. The function prints the n1 value on each iteration of the loop. Each iteration determines the next value in the sequence by summing the two previous values then updating the values of n1 and n2.

Let’s test the function and write the Fibonacci sequence up to seven terms:

fib(7)

Fibonacci sequence up to n=7: 
0
1
1
2
3
5
8

Recursive Implementation of the Fibonacci Sequence in Python

Recursion is when a function refers to itself to solve a problem. In every function call, the problem becomes smaller until the call reaches a base case, after which it will return the result to each intermediate call until it returns the final result to the first call.

Let’s look at the example of calculating the fifth Fibonacci number, F(5). First, we will need to calculate its preceding numbers to do this calculation. F(4) and F(3). Then to calculate F(4) and F(3), you would need to calculate their preceding numbers and so on. The complete recursive solution for F(5) would look as follows:

Each time we call the Fibonacci function, the problem breaks up into smaller component problems. When the function eventually reaches the base case of either F(0) or F(1), it will return the result to the caller. Let’s look at how to implement the recursive solution in Python:

def fib_recursive(n):

    if n ≺= 1:

        return n

    else:

        return(fib_recursive(n-1) + fib_recursive(n-2))

In the above function, we use recursion to generate the Fibonacci sequence. The function takes the parameter n. If the number is 0 or 1, the function will return the value of n. Otherwise, it will recursively call the fib_recursive function with the values n-1 and n-2.

Next, we will use the input function to get a number from the user. We will use this number in the range() function within a for loop to iteratively print the Fibonacci sequence for the specified number of terms to the console.

nterms = int(input("Enter number of terms to return: "))

    if nterms ≺= 0:

        print("Please enter a positive integer")

    else:

        print(f'Fibonacci sequence for n={nterms}:')

        for i in range(nterms):

            print(fib_recursive(i))

Let’s run the code to get the result.

Enter number of terms to return: 10
Fibonacci sequence for n=10:
0
1
1
2
3
5
8
13
21
34

Summary

Congratulations on reading to the end of this tutorial! You have gone through implementing the Fibonacci sequence in Python both iteratively and recursively. The Fibonacci Sequence and Fibonacci numbers are ubiquitous in nature and underpin fascinating mathematical expressions. Learning how to implement the Fibonacci sequence is particularly helpful for understanding how recursion works in Python.

For further reading on recursive functions, go to the article: How to Find the Factorial of a Number in Python.

To learn how to implement the Fibonacci sequence in C++, go to the article: How to Write the Fibonacci Sequence in C++.

Go to the online courses page on Python to learn more about coding in Python for data science and machine learning.

Have fun and happy researching!