Skip to content

Calculating Fibonacci Sequence in Python: Step-by-Step Guide with Code Examples

Updated: at 04:23 AM

The Fibonacci sequence is a famous mathematical sequence in which each number is the sum of the previous two numbers, starting with 0 and 1. This sequence commonly comes up as an interview question for software engineering positions, as it allows candidates to demonstrate their proficiency with recursion and iteration. In this comprehensive guide, we will examine methods for calculating Fibonacci numbers in Python using both recursive and iterative techniques.

Table of Contents

Open Table of Contents

Overview of the Fibonacci Sequence

The Fibonacci sequence begins with 0 and 1, and each subsequent number is calculated by adding the previous two numbers. For example, the first several numbers of the Fibonacci sequence are:

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

The mathematical formula for generating the Fibonacci sequence is:

F(n) = F(n-1) + F(n-2)

Where F(n) is the nth Fibonacci number.

Some key properties of the Fibonacci sequence include:

The Fibonacci sequence appears frequently in nature, such as the spiral arrangment of leaves, branches, and petals. It also has numerous applications in computer science, statistics, and applied mathematics.

Now let’s examine methods for calculating Fibonacci numbers in Python.

Recursive Approach

A recursive approach follows the mathematical definition of the Fibonacci sequence closely. In recursion, a function calls itself to solve a smaller part of the overall problem.

Here is an example recursive function to calculate the nth Fibonacci number in Python:

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

This function has two base cases:

For any n > 1, it calls itself recursively on the prior two numbers and sums the result.

Let’s step through how this function calculates f(5):

  1. f(5) calls fibonacci_recursive(4)
  2. f(4) calls fibonacci_recursive(3)
  3. f(3) calls fibonacci_recursive(2)
  4. f(2) calls fibonacci_recursive(1)
  5. f(1) returns 1
  6. f(2) calls fibonacci_recursive(0)
  7. f(0) returns 0
  8. f(2) returns 1 + 0 = 1
  9. f(3) returns 1 + 1 = 2
  10. f(4) returns 2 + 1 = 3
  11. f(5) returns 3 + 2 = 5

By recursively calling itself on smaller inputs, it is able to compute the desired nth Fibonacci number.

Let’s test our function:

# 5

# 21

The recursive approach works well and is simple to implement. However, it is inefficient for larger inputs due to repeated recursive calls. Each f(n) results in f(n-1) and f(n-2) being called, leading to an exponential explosion of recursive calls.

For example, calculating f(35) would require over 68 billion recursive calls! This makes our naive recursive implementation impractical for larger n. Let’s examine an iterative approach next.

Iterative Approach

An iterative solution calculates each Fibonacci number sequentially, storing the previous two numbers. This avoids the exponential growth in work of the recursive solution.

Here is an iterative function to calculate the nth Fibonacci number:

def fibonacci_iterative(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

This function initializes two variables a and b representing the first two Fibonacci numbers 0 and 1. It then enters a for loop iterating up to the nth number. On each iteration, it updates a and b to contain the next two numbers in the sequence. After n iterations, a will contain the nth Fibonacci number.

Stepping through the calculation of f(8):

  1. Initialize: a = 0, b = 1
  2. i = 0: a, b = 1, 1
  3. i = 1: a, b = 1, 2
  4. i = 2: a, b = 2, 3
  5. i = 3: a, b = 3, 5
  6. i = 4: a, b = 5, 8
  7. i = 5: a, b = 8, 13
  8. i = 6: a, b = 13, 21
  9. i = 7: a, b = 21, 34
  10. Return a = 21

By iterating up to n and updating a and b, we calculate the nth Fibonacci number in O(n) linear time and constant O(1) space.

Testing the iterative function:

# 21

# 9227465

This iterative approach is much more efficient than the recursive solution and does not run into issues calculating larger n.

Comparing Recursive and Iterative Implementations

Let’s summarize the tradeoffs between the recursive and iterative solutions:

The recursive solution is simpler but inefficient for larger n due to exponential recursive calls. The iterative approach is more complex but significantly more efficient and practical.

Here is a chart showing the number of calls for each function on increasing n:

n	Recursive Calls	Iterative Calls
5	15			5
10	177			10
20	21891		20
35	68,719,476,735	35

The exponential growth of the recursive function quickly makes it impractical, while iterative remains efficient.

Tips for Implementing Fibonacci Solutions

When implementing a Fibonacci function, keep these tips in mind:

Applications of the Fibonacci Sequence

Beyond technical interview questions, the Fibonacci sequence arises in many real-world contexts:

Nature and Biology

Computer Science

Signals and Image Processing

Architecture and Art

Understanding and implementing Fibonacci sequence calculations is a foundational computer science skill with far-reaching utility across many domains.


Calculating the Fibonacci sequence recursively and iteratively is a common technical interview question and programming exercise. In this guide, we examined Python implementations using both techniques and discussed their performance tradeoffs. The recursive approach provides an elegant and simple solution following the mathematical definition, but is inefficient for larger inputs. The iterative technique requires more complex logic but provides linear O(n) performance that scales well.

When implementing Fibonacci solutions, optimize for your expected use case. Use recursion for readability on small n or add memoization. Employ iteration for efficiency on large inputs. Consider advanced algorithms like dynamic programming or Binet’s formula for further optimizations. Mastering Fibonacci sequence coding challenges demonstrates core computer science and algorithms skills that translate into real-world applications across many fields.