Fibonacci Series in Python

You need to understand the Fibonacci sequence in Python. It’s a classic programming problem and a common interview question for a reason. It separates people who can just write code from people who can think about efficiency.

What Exactly Is The Fibonacci Sequence?

It’s a simple series of numbers. You start with 0 and 1. The next number is the sum of the two before it.

So it goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

The mathematical formula looks like this: F(n) = F(n-1) + F(n-2). This is the key.

How to Code Fibonacci in Python: Two Main Ways

There are two common paths to take. One looks elegant but is deeply flawed. The other is less pretty but is the correct way for most situations.

Method 1: The Recursive Approach (The “Elegant” but Slow Way)

Recursion is when a function calls itself. The recursive solution looks a lot like the mathematical formula, which makes it seem clean.

The Code:

Python
def fibonacci_recursive(n):
    # Base cases: the first two numbers
    if n <= 1:
        return n
    # Recursive step
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# Example: Get the 10th Fibonacci number
print(fibonacci_recursive(10))
# Output: 55

The Explanation:

Base Cases: The if n <= 1: part is critical. It tells the function when to stop recursing. Without it, you have an infinite loop. fib(0) is 0 and fib(1) is 1.

Recursive Step: The else block is the direct translation of the formula F(n-1) + F(n-2). To get fib(5), it calls fib(4) and fib(3). To get fib(4), it calls fib(3) and fib(2), and so on.

The Huge Problem: This is extremely inefficient. To calculate fib(5), it calculates fib(3) twice, fib(2) three times, etc. It re-computes the same values over and over. The time complexity is exponential, around O(2^n), which means it gets impossibly slow for even moderately large numbers. Try running fibonacci_recursive(40). Go ahead, I’ll wait.

Method 2: The Iterative Approach (The Smart and Fast Way)

Iteration means using a loop. You build the sequence from the bottom up, calculating each number just once.

The Code:

Python
def fibonacci_iterative(n):
    # The first two numbers
    a, b = 0, 1
    
    # Loop n-1 times to get to the nth number
    for _ in range(n-1):
        a, b = b, a + b # The core logic
        
    return b

# Example: Get the 10th Fibonacci number
print(fibonacci_iterative(10)) 
# Output: 55

The Explanation:

Initialization: a, b = 0, 1 sets up the start of the sequence.

The Loop: The for loop runs n times.

The Swap: a, b = b, a + b is the clever part. In each step, a takes the value of b, and b becomes the sum of the old a and b. It’s a clean way to move one step forward in the sequence.

Why It’s Better: This approach is fast. It calculates each Fibonacci number only once. The time complexity is linear, O(n). You can calculate fibonacci_iterative(1000) instantly. The memory usage is also constant, O(1), because you’re only ever storing a couple of variables.

Recursion vs. Iteration

Conclusion

For the Fibonacci problem in an interview or any practical application, use the iterative approach. The naive recursive solution is a classic example of an elegant-looking but terrible algorithm.

Read:

• Python Interview Questions and Answers
• Python MCQs Test

Fibonacci Code Q&A: Common Problems and Answers

Q: How do I generate a list of the first N Fibonacci numbers?

A: Modify the iterative function to store results in a list.

Python
def fibonacci_list(n):
    result = []
    a, b = 0, 1
    for _ in range(n):
        result.append(a)
        a, b = b, a + b
    return result

print(fibonacci_list(10))
# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Q: Can the recursive solution be fixed to not be slow?

A: Yes. This is a common follow-up question. You fix it with memoization (a form of caching). You store the results of function calls so you don’t have to compute them again.

Python
# A cache to store computed Fibonacci numbers
memo = {}

def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    
    # Compute, store, and then return
    result = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    memo[n] = result
    return result

print(fibonacci_memo(50)) 
# Output: 12586269025
# This is fast now.

This optimized version is O(n), just like the iterative one, but it uses more memory for the cache and the recursion stack.

In Python, the easiest way to do this is with a built-in decorator:

Python
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_cached(n):
    if n <= 1:
        return n
    return fibonacci_cached(n-1) + fibonacci_cached(n-2)

print(fibonacci_cached(50))
# Output: 12586269025

This is the “pro” way to write a fast recursive solution.

Q: What if I’m asked to do this in an interview?

A: Start with the iterative solution. It shows you value performance. Then, mention the naive recursive solution and explain why it’s bad (re-computation, exponential complexity). Finally, explain how to optimize the recursive version with memoization. This covers all your bases and shows a deep understanding of the trade-offs.

Further Reading

1. Factorial of a number in Python
2. Palindrome in Python
3. Convert List to String in Python
4. Eval Function in Python
5. Fibonacci Series in Java
6. Fibonacci Series in C