Skip to main content

Fibonacci Sequence in Python: Learn and Explore Coding Techniques

Discover how the Fibonacci sequence works. Explore its mathematical properties and real-world applications.
Jan 17, 2025  · 6 min read

The Fibonacci sequence is a fun way to keep practicing Python. In this article, you'll learn how to implement the Fibonacci sequence in Python using different Python techniques, from writing efficient functions and handling recursion to using object-oriented principles for more optimized solutions. 

When you’re all the way through, take our Writing Functions in Python course to reinforce concepts like scoping and error handling, or try our Intermediate Object-Oriented Programming in Python course to learn about inheritance and base classes. Now, let's try out the Fibonacci sequence.

What is the Fibonacci Sequence?

The Fibonacci sequence is a mathematical concept that appears in many areas of science and nature. It is a series of numbers where each number is the sum of the two preceding ones, starting with 0 and 1. This pattern forms the basis for applications in fields like computer science and finance. 

Two main aspects define the Fibonacci sequence: the recursive structure of the sequence and its relationship with the golden ratio.

Recursive nature of the Fibonacci sequence

The Fibonacci sequence starts with 0 and 1. Each new number is the sum of the two numbers before it. For example:

0 + 1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

And so on. 

Mathematically, we write it as F(n) = F(n-1) + F(n-2). The sequence builds itself by repeatedly adding the last two numbers. The first two numbers, 0 and 1, are the starting point or base cases. Without these, the sequence wouldn’t work.

This recursive pattern serves as the basis for some algorithms in computer science. For example, recursion in programming works on this sequence when solving problems like generating Fibonacci numbers or dividing tasks into smaller, manageable pieces.

Golden ratio connection 

The Fibonacci sequence is closely tied to the golden ratio which is an irrational number represented by φ (its value is about 1.618). If you divide a Fibonacci number by the one before it, the ratio gets closer and closer to φ. For example:

5 ÷ 3 ≈ 1.666

8 ÷ 5 ≈ 1.6

13 ÷ 8 ≈ 1.625

The further along you go, the closer it gets to 1.618. This isn’t a coincidence — the ratio shows up naturally in the Fibonacci sequence because of how the numbers grow.

Euclid first described it in ancient Greece as the extreme and mean ratio. Since then, it’s been linked to patterns in nature, like the spirals in shells and flowers, as well as in art and architecture.

golden ratio in art

Golden ratio in art. Source

Practical Applications of the Fibonacci Sequence

The Fibonacci sequence shows up in surprising ways across many fields. Let’s focus on two of its most notable applications: its patterns in nature and its use in computer science.

Fibonacci in nature

You can see the Fibonacci sequence all over nature. Look at flowers — the number of petals often matches Fibonacci numbers. For example, daisies may have 34, 55, or 89 petals, and lilies often have 3, 5, or 8. These patterns help plants grow in ways that maximize sunlight and rainfall.

Spirals in pinecones and sunflowers also follow Fibonacci numbers. The arrangement of seeds in a sunflower, for example, matches the sequence. It’s fascinating how something as simple as adding two numbers can describe so much of the natural world.

Fibonacci in computer science

The Fibonacci sequence also plays a key role in algorithms and data structures. For example, Fibonacci numbers are used in search algorithms to break down problems into smaller parts efficiently. The sequence is even behind Fibonacci heaps, a type of data structure used to speed up certain operations like finding the shortest path in a network.

Here’s a simple example of how you can generate a Fibonacci sequence in Python:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
for i in range(10):
    print(fibonacci(i), end=" ")
0 1 1 2 3 5 8 13 21 34

This recursive function shows how the Fibonacci sequence is built. While recursion is easy to understand, there are also optimized versions, like dynamic programming, to calculate Fibonacci numbers much faster.

In cryptography, Fibonacci numbers can help generate secure keys. And in artificial intelligence, they optimize neural networks to improve how algorithms learn and adapt. 

Other common examples

Here are a few more examples of how this sequence appears in everyday life and specialized fields:

  • In Art: The Fibonacci sequence has been used by artists and architects for centuries. Famous structures like the Parthenon feature these proportions because they are naturally pleasing to the eye.
  • In Music: Composers use Fibonacci numbers to create rhythms and melodies. For example, they assign whole notes to 1, half notes to 2, and quarter notes to 3 to create harmonious patterns.
  • In Trading: Stock traders apply Fibonacci numbers to analyze market trends. They use them to predict potential price levels where stocks might reverse, helping them decide when to buy or sell.
  • In Physics: In quantum physics, Fibonacci patterns have been observed in the interactions and behavior of particles, revealing how these sequences appear even at the smallest scales of nature.

Implementing the Fibonacci Sequence in Python

Since Python provides several ways to generate the Fibonacci sequence, I’ve discussed the most commonly used ones step-by-step with examples.

Using an iterative method

The iterative method is one of the simplest ways to generate the Fibonacci sequence. It uses a loop to calculate each term in the sequence, which makes it more memory-efficient than recursive methods. Here’s how it works:

I set two variables, a and b, to 0 and 1. These represent the first two numbers in the sequence. Then, I use a for loop to calculate the next numbers. I update a to hold the value of b, and b becomes the sum of the previous a and b.

Here's a Python code for this:

n = 10
a, b = 0, 1

for i in range(n):
    print(a)
    a, b = b, a + b
0
1
1
2
3
5
8
13
21
34

If you want to use a while loop instead of a for loop, here’s how you can write the code:

# Number of terms to print in the Fibonacci series
n = 10

# Initialize the first two terms
a, b = 0, 1
i = 0

while i < n:
    print(a, end=' ')
    # Update the terms
    a, b = b, a + b
    i += 1
0 1 1 2 3 5 8 13 21 34

Both methods are super easy to understand, which makes them perfect for beginners. 

Using a recursive method

The recursive method is another way to generate Fibonacci numbers. It’s not as fast as the iterative method for larger sequences, but it’s a great way to understand the logic behind how the sequence builds.

For example, I create a function called fibonacci_recursive. This function takes a number n as input. If n is 0 or 1, the function returns n. These are the base cases that tell the recursion when to stop. For any other number, the function calls itself to calculate the previous two numbers and adds them together.

Here’s the code for this:

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

num_terms = 10
for i in range(num_terms):
    print(fibonacci_recursive(i), end=" ")
0 1 1 2 3 5 8 13 21 34

This method works well for small sequences but can get slow as the sequence grows because it recalculates the same values multiple times.

Using an optimized recursive method with caching

To fix the inefficiency of plain recursion, I often use caching. Python’s lru_cache stores previously calculated values so the function doesn’t have to redo the work.

Here’s how I do it:

from functools import lru_cache

@lru_cache(maxsize = None)
def fib_cache(n):
    if n == 0:
        return 0  
    elif n == 1:
        return 1
    else:
        return fib_cache(n-1) + fib_cache(n-2)

print(f"The Fibonacci Number is {fib_cache(10)}")
The Fibonacci Number is 55.

This approach combines the clarity of recursion with the efficiency of caching.

More Advanced Ways to Do the Fibonacci Sequence in Python

If you’re looking for other ways to calculate Fibonacci numbers, here are a few more advanced techniques:

Matrix exponentiation

Matrix exponentiation is one of the most efficient ways to compute Fibonacci numbers for large values of n. Instead of recalculating terms repeatedly, this method uses matrix multiplication to get results in logarithmic time.

Here’s how I implemented this in Python:

import numpy as np

def fibonacci_matrix(n):
    def matrix_power(matrix, power):
        return np.linalg.matrix_power(matrix, power)
    
if n == 0:
        return 0
    matrix = np.array([[1, 1], [1, 0]])
    result = matrix_power(matrix, n-1)
    return result[0][0]
for i in range(10):
    print(fibonacci_matrix(i)  , end=" ")
0 1 1 2 3 5 8 13 21 34

In this code, if n is 0, it returns 0 as the base case. For other values, the matrix is raised to the power (n-1) using numpy’s matrix_power function. The Fibonacci number at position n is found in the top-left element of the resulting matrix.

Binet's formula

Binet’s formula directly calculates the nth Fibonacci number without iteration or recursion. It’s based on the golden ratio, φ, and uses a mathematical expression to calculate the result instantly.

The formula is:

Binet's formula in fibonacci sequence in python.

Where:

  • φ = (1 + 5) / 2​​, the golden ratio.
  • 1 - φ is the conjugate of φ.

Here’s the Python code for Binet’s formula:

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))

# Find the 10th Fibonacci number
n = 10
result = fibonacci_binet(n)
print(f" The Fibonacci Number of {n}th term is {result}" ) 
The Fibonacci number of 10th term is 55

In this code, the function fibonacci_binet(n) calculates the nth Fibonacci number using Binet's formula. Inside the function, I calculate phi (the golden ratio) as (1 + math.sqrt(5)) / 2, using math.sqrt() for the square root of 5. The formula (phi ** n - (1 - phi) ** n) / math.sqrt(5) is then applied to find the nth Fibonacci number directly. Then, I use the round() function to handle any small floating-point inaccuracies.

Arrays

You can even use arrays to generate and store the entire Fibonacci sequence. This is helpful when you need multiple terms simultaneously.

Here’s the code for this:

def fibonacci(n):
    if n <= 0:
        return "Incorrect Output"
    data = [0, 1]  # Initialize list with first two Fibonacci terms: 0 and 1
    if n > 2:
        for i in range(2, n):  # Start loop from the third term
            data.append(data[i-1] + data[i-2])  # Calculate next term as sum of previous two
    return data[n-1]  # Return the nth term

print(f"Fibonacci Number: {fibonacci(10)}")
Fibonacci number: 34

Backtracking

Backtracking is another option I could use, especially when I want to combine recursion with memoization for better performance.

Here’s the code for this:

def fibonacci_backtracking(n, computed ={0: 0, 1: 1}):
    if n in computed:
        return computed[n]
    computed[n] = fibonacci_backtracking(n - 1) + fibonacci_backtracking(n - 2)
    return computed[n]

n = 10
result = fibonacci_backtracking(n)
print(f"The {n}th Fibonacci term is {result}")
The 10th Fibonacci term is 55

Complexity of Fibonacci Algorithms in Python

We have gone through quite a few examples! Let's now look at their differences in terms of time and space complexity. As we have mentioned, some methods are fast but use more memory, while others are slower but need less space. I prepared this table to compare each approach's efficiency.

Method Time Complexity Space Complexity
Iterative (For Loop) O(n) O(1)
Iterative (While Loop) O(n) O(1)
Simple Recursion O(2ⁿ) O(n)
Memoization/Caching O(n) O(n)
Array-based O(n) O(n)
Backtracking Method O(2ⁿ) O(2ⁿ)
Matrix Exponentiation O(log n) O(log n)

In the above table, here’s what each time and space complexity means:

Time complexity

  • O(n): The algorithm iterates through the sequence once by performing a fixed number of operations for each element. The time it takes grows linearly with the input size n.

  • O(1): The Fibonacci number is calculated using a fixed number of operations without iteration or recursion.

  • O(2n): The algorithm makes two recursive calls for each input which leads to exponential growth in the number of function calls as n increases.

  • O(log n): Runtime grows in proportion to the logarithm of the input size n.

Space complexity

  • O(n): The algorithm uses memory that grows directly with the number of inputs n. Here, each element requires a fixed amount of space.

  • O(1): Memory usage remains constant regardless of input size.

  • O(2n): It uses exponential space due to the creation of new states for each branch.

  • O(log n): Intermediate matrix multiplications use logarithmic memory.

Final Thoughts

As you have seen, in Python, you can calculate Fibonacci numbers using many different methods, from simple loops to advanced techniques like matrix exponentiation and Binet’s formula. Each method has its strengths and trade-offs.

I hope you learned something both about the Fibonacci sequence but also about Python programming. If you want to explore more about Python and related topics, check out our Introduction to Python course. You can also try our full Python Developer career track and learn programming techniques and even start developing your own packages!


Laiba Siddiqui's photo
Author
Laiba Siddiqui
LinkedIn
Twitter

I'm a content strategist who loves simplifying complex topics. I’ve helped companies like Splunk, Hackernoon, and Tiiny Host create engaging and informative content for their audiences.

Fibonacci Sequence in Python FAQs

What is the Fibonacci sequence used for?

The Fibonacci sequence is used in various fields, such as mathematics, computer science, and nature studies, to model growth patterns and optimize algorithms.

How is the Fibonacci sequence calculated?

The Fibonacci sequence is calculated by adding the two preceding numbers to get the next number, starting with 0 and 1.

What are examples of the Fibonacci sequence in nature?

Examples include the arrangement of leaves on a stem, the branching of trees, and the pattern of various fruits and flowers.

How do you implement the Fibonacci sequence in Python?

You can implement it using either an iterative or recursive approach, with Python code examples available in many programming tutorials.

What is the formula for the nth term of the Fibonacci sequence?

The nth term can be calculated using Binet's formula, which involves the golden ratio and provides a direct computation method.

Topics

Learn Python with DataCamp

course

Introduction to Python

4 hr
6M
Master the basics of data analysis with Python in just four hours. This online course will introduce the Python interface and explore popular packages.
See DetailsRight Arrow
Start Course
See MoreRight Arrow
Related

tutorial

Understanding Recursive Functions in Python

In this tutorial, learn about the different aspects of recursive functions and implement a recursive function in Python from scratch.
Sayak Paul's photo

Sayak Paul

12 min

tutorial

Python Slice: Useful Methods for Everyday Coding

Discover how slicing can effortlessly extract, rearrange, and analyze your data. Harness negative indices, multi-dimensional slices, and advanced step values for full precision.
Oluseye Jeremiah's photo

Oluseye Jeremiah

8 min

tutorial

Python Arrays

Python arrays with code examples. Learn how to create and print arrays using Python NumPy today!
DataCamp Team's photo

DataCamp Team

3 min

tutorial

Markov Chains in Python: Beginner Tutorial

Learn about Markov Chains, their properties, transition matrices, and implement one yourself in Python!
Sejal Jaiswal's photo

Sejal Jaiswal

15 min

tutorial

Python Tutorial for Beginners

Get a step-by-step guide on how to install Python and use it for basic data science functions.
Matthew Przybyla's photo

Matthew Przybyla

12 min

code-along

Time Series Analysis in Python

Dig into financial time series in Python.
Justin Saddlemyer's photo

Justin Saddlemyer

See MoreSee More