Complete Guide to Fibonacci in Python

The Fibonacci sequence appears in interviews to evaluate your coding skills, problem-solving skills, and knowledge of performance optimization. It is used by Google, Microsoft, and other companies to determine the efficiency with which you code.

Outside of interviews, Fibonacci appears in nature, for example, in flower petals and pinecone spirals. It is also used in analyzing the stock market.

Don’t worry if you don’t get the difficult mathematics. This tutorial will stick to useful Python coding methods that you can implement immediately.

What is the Fibonacci Sequence?

The Fibonacci sequence is a series where each number equals the sum of the two numbers before it:

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

Here’s how it works:

• Start with 0 and 1
• Add them: 0 + 1 = 1
• Add the last two: 1 + 1 = 2
• Keep going: 1 + 2 = 3, then 2 + 3 = 5, and so on

The math formula is: F(n) = F(n-1) + F(n-2)

Method 1: Simple Loop (Best Choice)

This is usually what you want to use:

python
def fibonacci(n):
    if n <= 1:
        return n
    
    # Start with first two numbers
    prev, curr = 0, 1
    
    # Calculate each number once
    for i in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

# Test it
print(fibonacci(10))  # Output: 55
print(fibonacci(0))   # Output: 0
print(fibonacci(1))   # Output: 1

Why this is good:

• Fast: calculates each number only once
• Uses very little memory
• Easy to understand once you trace through it
• Works for large numbers

Method 2: Recursion (Looks Nice, But Slow)

Recursion is when a function calls itself. The recursive solution matches the Fibonacci mathematical formula.

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

print(fibonacci_recursive(10))  # Output: 55

The problem: This is extremely slow for big numbers because it recalculates the same values over and over. Try fibonacci_recursive(40) and watch it take forever.

Method 3: Smart Recursion with Memory

If you want recursion that’s actually fast, use memoization:

python
def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    result = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    memo[n] = result
    return result

print(fibonacci_memo(50))  # Fast now!

Or use Python’s built-in cache:

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(100))  # Very fast

Getting Multiple Fibonacci Numbers

Want the first N Fibonacci numbers as a list?

python
def fibonacci_sequence(n):
    if n <= 0:
        return []
    if n == 1:
        return [0]
    
    sequence = [0, 1]
    for i in range(2, n):
        next_num = sequence[i-1] + sequence[i-2]
        sequence.append(next_num)
    
    return sequence

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

Performance Comparison

Common Mistakes

Mistake 1: Using basic recursion for anything bigger than fibonacci(30)

python
# DON'T do this for large n
fibonacci_recursive(40)  # Will take minutes

Mistake 2: Forgetting the base cases

python
# This will crash
def bad_fibonacci(n):
    return bad_fibonacci(n-1) + bad_fibonacci(n-2)  # No stopping condition

Mistake 3: Off-by-one errors

python
# Make sure you know if you want the nth number or first n numbers
fibonacci(5)        # Returns the 5th Fibonacci number (5)
fibonacci_sequence(5) # Returns first 5 Fibonacci numbers [0,1,1,2,3]

Interview Tips

When asked about Fibonacci in an interview:

• Start with the simple loop solution – shows you care about performance
• Explain why basic recursion is bad – demonstrates you understand efficiency
• Mention memoization – shows advanced knowledge
• Ask clarifying questions: Do they want the nth number or first n numbers? Should you handle negative inputs?

Read:

• Python Interview Questions and Answers
• Python MCQs Test
• Online Python Compiler

Quick Reference

python
# Most common: get the nth Fibonacci number
def fibonacci(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for i in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# Get first n Fibonacci numbers
def fibonacci_sequence(n):
    if n <= 0: return []
    if n == 1: return [0]
    sequence = [0, 1]
    for i in range(2, n):
        sequence.append(sequence[i-1] + sequence[i-2])
    return sequence

# Fast recursive version
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_recursive_fast(n):
    if n <= 1: return n
    return fibonacci_recursive_fast(n-1) + fibonacci_recursive_fast(n-2)

Use the simple loop version unless you have a specific reason not to. It’s fast, uses little memory, and easy to debug.

Common Questions

Why do interviewers love this problem?
They want to see your coding style, test if you understand recursion, and how you handle performance issues. Most people know about Fibonacci, so it’s fair game.

What’s the biggest Fibonacci number I can calculate?
Python doesn’t have integer limits like other languages. Some people have calculated Fibonacci (10000) on a laptop – it runs fast. The real limit is how long you want to wait and how much memory you have.

Any tricks for interviews?
Start with the loop version. It shows you care about speed. Then mention why recursion is slow (it recalculates everything). Finally, explain memoization if they ask about fixing recursion. This covers all the bases.

What about negative numbers?
There’s actually a pattern: F(-n) = (-1)^(n+1) * F(n). But most interview questions stick to positive numbers. Just ask what they want you to do with edge cases.

Should I memorize all these approaches?
No. Understand the loop version really well. Know why basic recursion is slow. Remember that caching fixes it. That’s 90% of what you need for interviews.

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