Fibonacci Sequence in Python

In today’s post, we’ll look at two ways to calculate the n^th term of a Fibonacci sequence in Python.

We’ll also work on a practice question that requires us to write a function to display the first n terms of the sequence.

Here are some topics we’ll be covering in today’s post:

• What is the Fibonacci sequence
• What is recursion
• 2 ways to calculate the n^th term of a Fibonacci sequence in Python

Key Concepts

Let’s first discuss some key concepts needed for today’s practice question.

What is the Fibonacci sequence?

The Fibonacci sequence is a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1.

The first 10 terms of the Fibonacci sequence are shown below:

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

By definition, the first two numbers of a Fibonacci sequence are 0 and 1. To get the third number, we add the first two numbers. Hence, we get 0 + 1 = 1 as the third number.

To get the fourth number, we add the second and third numbers. Hence, we get 1 + 1 = 2 as the fourth number.

We keep repeating this process until we get all 10 terms of the sequence.

How to use Python to get the nth term of a Fibonacci sequence?

There are two ways to get the n^th term of a Fibonacci sequence using Python.

• The first way is to use a loop
• The second way is to use recursion

Let’s look at each of them.

Using a loop

Suppose we want to get the 10^th term of a Fibonacci sequence. From the previous section, we know that the 10^th term is 34. To calculate it using Python, we can use the code below:

def fibLoop(n):
    if n <= 0:
        return -1
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        a = 0
        b = 1
        result = 0
        for i in range(3, n+1):
            result = a + b
            a = b
            b = result
        return result

print(fibLoop(10))

Here, we first define a function called fibLoop() that has one parameter n.

n represents the term number. For instance, if we want to find the 10^th term, n equals 10.

Inside the function, we return -1 if n is invalid (i.e. if n <= 0).

Next, we check if n is 1 (the first term) or 2 (the second term). If it is, we return the values 0 and 1 respectively.

If n is not negative, 0, 1 or 2, we move on to the else case (lines 8 to 16).

Inside the else case, we first assign 0 and 1 to the variables a and b respectively.

a and b are used to store the preceding two numbers of any number in the sequence. At present, a and b store the first and second terms in the sequence respectively.

As we iterate through the for loop later, a and b will be updated to store the preceding two numbers of subsequent numbers in the sequence. For instance, when i equals 6, a and b will be updated to store the 5^th and 6^th terms in the sequence.

When the loop runs again the next time, i becomes 7. Adding a and b then gives us the 7^th term in the sequence.

Besides a and b, we also declare a variable called result and initialize it to 0 (line 11).

Next, we have a for loop that loops from i = 3 to i = n. (Recall that range(x, y) gives us the numbers from x to y-1, not x to y)

Inside the for loop, we calculate the Fibonacci value for the i^th term by adding a with b. Next, we update the values of a and b so that they store the values of the most recent two numbers.

After we finish iterating through the for loop, result stores the n^th term of the sequence. We then return this value using a return statement on line 16.

With that, the function is complete.

We call the function on line 18 (passing 10 as the argument) and use the print() function to print the result.

If you run the code above, you’ll get 34 as the output.

Using recursion

Besides using a for loop to calculate the n^th term of a Fibonacci sequence, we can use recursion.

As mentioned in a previous post, recursion is very useful when a problem can be solved by solving smaller instances of the same problem.

In the case of a Fibonacci sequence, we can find the n^th term of the sequence by finding the (n-1)^th and (n-2)^th terms. For instance, we can find the 6^th term by finding the 5^th and 4^th terms.

In turn, we can find the 5^th term by finding the 4^th and 3^rd terms and so on. This makes it a perfect case for using recursion.

Similar to all other recursion problems, we need to have a base case that returns the result and stops the recursion. In the case of a Fibonacci sequence, we have multiple base cases. The base cases include the cases where n is negative (return -1), n is 1 (return 0) and n is 2 (return 1).

To use recursion to find the n^th term of a Fibonacci sequence, we can use the function below:

def fibRec(n):
    if n <= 0:
        return -1
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibRec(n-1) + fibRec(n-2)

print(fibRec(4))

Notice how much more elegant this function is?

On line 1, we define a function called fibRec() that has one parameter n. Inside the function, we have three base cases from lines 2 to 7.

On lines 8 and 9, we have the recursive case where we call fibRec(n-1) and fibRec(n-2) and return the result of their sum.

On line 11, we call fibRec(4) and use the print() function to print its result.

The diagram below shows what happens when we run line 11:

Line 11 calls fibRec(4), which in turn calls fibRec(3) and fibRec(2).

When fibRec(4) calls fibRec(3), fibRec(3) in turn calls fibRec(2) and fibRec(1) (highlighted in orange above). Since fibRec(2) and fibRec(1) are both base cases, they return the value 1 and 0 to the caller respectively.

fibRec(3) then adds these two values (0 + 1 = 1) and returns the answer to its caller.

fibRec(4) adds this value together with the value returned by fibRec(2) below and returns the result to the caller (line 11). 

If you run the code above, you’ll get

2

as the output. Got it?

Practice Question

Good!

Now that we know how to get the n^th term of a Fibonacci sequence, let’s work on today’s practice question.

The practice question for today requires us to write a function called fibSequence() that has one parameter n.

This function returns an empty list if n is smaller than 1. Else, it returns a list containing the terms of a Fibonacci sequence up to the n^th term. You can assume that n is an integer.

Expected Results

To test your function, you can use the statements below:

print(fibSequence(-1))
print(fibSequence(2))
print(fibSequence(6))
print(fibSequence(10))

You should get the following output:

[]
[0, 1]
[0, 1, 1, 2, 3, 5]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Suggested Solutions

def fibSequence(n):
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    else:
        fib = [0, 1]
        for i in range(2, n):
            fib.append(fib[i-2] + fib[i-1])
        return fib

def fibRec(n):
    if n <= 0:
        return -1
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibRec(n-1) + fibRec(n-2)
    
def fibSequence(n):
    result = []
    for i in range(1, n+1):
        result.append(fibRec(i))
    return result