course
Fibonacci Sequence in Python: Learn and Explore Coding Techniques
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. 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:
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:
-
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
.
-
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!
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.
Learn Python with DataCamp
course
Intermediate Object-Oriented Programming in Python
course
Python Toolbox
tutorial
Understanding Recursive Functions in Python
tutorial
Python Slice: Useful Methods for Everyday Coding

Oluseye Jeremiah
8 min
tutorial
Python Arrays

DataCamp Team
3 min
tutorial
Markov Chains in Python: Beginner Tutorial
tutorial