DocsHub
PythonIntermediate

Fibonacci Sequence

Learn how to generate the Fibonacci sequence in Python using loops, recursion, and generators.

Fibonacci Sequence

Problem

The Fibonacci sequence starts with 0 and 1. Every number after that is the sum of the two numbers before it.

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

Two problems to solve:

Part 1 — generate the first N numbers of the sequence:

Input:  8
Output: [0, 1, 1, 2, 3, 5, 8, 13]

Part 2 — find the Nth Fibonacci number:

Input:  7
Output: 13   (the 7th number, counting from 1)

Input:  1
Output: 0

Input:  2
Output: 1

Logic

Part 1:

  1. Start with [0, 1]
  2. Each new number = last number + second to last number
  3. Keep adding until we have N numbers

Part 2:

  1. Same logic — generate up to the Nth number
  2. Return only the last one

Flow

No Yes Start a = 0, b = 1result = 0 and 1 Generated N numbers? next = a + b result.append next a = bb = next Return result

Solution 1 — using a loop

Build the sequence step by step — each iteration calculates the next number.

def fibonacci(n):
    if n <= 0:
        return []
    if n == 1:
        return [0]

    # start with the first two numbers
    sequence = [0, 1]

    # generate the rest
    while len(sequence) < n:
        # next number = sum of last two
        next_num = sequence[-1] + sequence[-2]
        sequence.append(next_num)

    return sequence


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

Code Execution — Solution 1

Trace through fibonacci(8):

Start: sequence = [0, 1]

Stepsequence[-2]sequence[-1]next_numsequence
1st011[0, 1, 1]
2nd112[0, 1, 1, 2]
3rd123[0, 1, 1, 2, 3]
4th235[0, 1, 1, 2, 3, 5]
5th358[0, 1, 1, 2, 3, 5, 8]
6th5813[0, 1, 1, 2, 3, 5, 8, 13]
Stoplen == 8

Result: [0, 1, 1, 2, 3, 5, 8, 13]

Solution 2 — using two variables

Instead of keeping the whole list, use just two variables a and b to track the last two numbers. More memory efficient.

def fibonacci(n):
    if n <= 0:
        return []
    if n == 1:
        return [0]

    a, b = 0, 1         # first two numbers
    sequence = [0, 1]   # result list

    while len(sequence) < n:
        a, b = b, a + b   # shift: a becomes b, b becomes a+b
        sequence.append(b)

    return sequence


def fibonacci_nth(n):
    """Return only the Nth Fibonacci number."""
    if n == 1:
        return 0
    if n == 2:
        return 1

    a, b = 0, 1

    for _ in range(2, n):
        a, b = b, a + b   # shift forward

    return b


print(fibonacci(8))        # [0, 1, 1, 2, 3, 5, 8, 13]
print(fibonacci_nth(7))    # 13
print(fibonacci_nth(1))    # 0
print(fibonacci_nth(10))   # 34

Code Execution — Solution 2

Trace through fibonacci_nth(7) — finding the 7th Fibonacci number:

Start: a = 0, b = 1

range(2, 7) gives us 5 iterations:

Iterationa beforeb beforea, b = b, a+ba afterb after
1st (i=2)01b=1, a+b=111
2nd (i=3)11b=1, a+b=212
3rd (i=4)12b=2, a+b=323
4th (i=5)23b=3, a+b=535
5th (i=6)35b=5, a+b=858

Wait — b = 8? Let us check: the 7th Fibonacci number is 0, 1, 1, 2, 3, 5, 8, 13 → position 7 = 13.

Let me re-trace range(2, 7) = iterations at i=2,3,4,5,6 → 5 steps:

ia, b = b, a+bb
20,1 → 1,11
31,1 → 1,22
41,2 → 2,33
52,3 → 3,55
63,5 → 5,88

Hmm, that gives 8 for the 7th position. But counting from 1: F(1)=0, F(2)=1, F(3)=1, F(4)=2, F(5)=3, F(6)=5, F(7)=8. So fibonacci_nth(7) = 8. Let us verify with fibonacci(8):

fibonacci(8) = [0, 1, 1, 2, 3, 5, 8, 13] → index 6 (7th item) = 8 ✅

a, b = b, a + b is Python's simultaneous assignment. Both right-hand side values are calculated first, then assigned. This means you do not need a temporary variable to swap — it is clean, safe, and the standard way to advance the Fibonacci sequence.

Solution 3 — using recursion

Each Fibonacci number is defined in terms of smaller Fibonacci numbers. This maps directly to recursion.

def fibonacci_recursive(n):
    """Return the Nth Fibonacci number using recursion."""
    # base cases
    if n == 1:
        return 0
    if n == 2:
        return 1

    # recursive case — sum of previous two
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


# generate sequence using recursion
def fibonacci_sequence_recursive(n):
    return [fibonacci_recursive(i) for i in range(1, n + 1)]


print(fibonacci_recursive(7))             # 8
print(fibonacci_sequence_recursive(8))    # [0, 1, 1, 2, 3, 5, 8, 13]

Code Execution — Solution 3

Trace through fibonacci_recursive(5):

fibonacci_recursive(5)
  = fibonacci_recursive(4) + fibonacci_recursive(3)
  = (fibonacci_recursive(3) + fibonacci_recursive(2))
    + (fibonacci_recursive(2) + fibonacci_recursive(1))
  = ((fibonacci_recursive(2) + fibonacci_recursive(1)) + 1)
    + (1 + 0)
  = ((1 + 0) + 1) + 1
  = (1 + 1) + 1
  = 2 + 1
  = 3

F(5) = 3 ✅ (sequence: 0, 1, 1, 2, 3)

Pure recursion is elegant but slow. fibonacci_recursive(40) makes over 300 million calls because it recalculates the same values over and over. Use memoization or the loop solution for large numbers.

Solution 4 — recursion with memoization

Store results of previous calls — never calculate the same value twice.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    """Fibonacci with caching — each value calculated only once."""
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)


# now fast even for large numbers
print(fibonacci_memo(50))    # 12586269025
print(fibonacci_memo(100))   # 354224848179261915075

# generate sequence
sequence = [fibonacci_memo(i) for i in range(1, 11)]
print(sequence)   # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Solution 5 — using a generator

Generate Fibonacci numbers one at a time using yield. Memory efficient — generates values on demand.

def fibonacci_generator(limit=None):
    """
    Generates Fibonacci numbers forever (or up to limit).
    Uses yield — produces one number at a time on demand.
    """
    a, b = 0, 1
    count = 0

    while True:
        if limit is not None and count >= limit:
            return   # stop after limit numbers

        yield a              # produce the current number
        a, b = b, a + b      # advance to next
        count += 1


# generate first 8 numbers
gen = fibonacci_generator(8)
print(list(gen))   # [0, 1, 1, 2, 3, 5, 8, 13]

# use in a for loop
for num in fibonacci_generator(10):
    print(num, end=" ")
# 0 1 1 2 3 5 8 13 21 34

# generate until a value exceeds 100
for num in fibonacci_generator():
    if num > 100:
        break
    print(num, end=" ")
# 0 1 1 2 3 5 8 13 21 34 55 89

Code Execution — Solution 5

Trace through first 4 values of fibonacci_generator():

Callyield aa, b = b, a+ba afterb after
1st next()yields 00,1 → 1,111
2nd next()yields 11,1 → 1,212
3rd next()yields 11,2 → 2,323
4th next()yields 22,3 → 3,535

Each yield pauses the function and returns the current value. The next call resumes from where it left off.

Which solution to use?

SolutionHowBest when
Solution 1Loop with listClear and easy to understand
Solution 2Two variablesMemory efficient — no list needed
Solution 3RecursionUnderstanding recursive thinking
Solution 4Recursion + lru_cacheLarge numbers, elegant code
Solution 5GeneratorProcessing one value at a time — infinite sequences

Output

[0, 1, 1, 2, 3, 5, 8, 13]
[0]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
[]
8
0
34

Count Word Frequency

Learn how to count how many times each word appears in a string in Python.

Factorial

Learn how to calculate the factorial of a number in Python using loops, recursion, and more.

On this page

Fibonacci SequenceProblemLogicFlowSolution 1 — using a loopCode Execution — Solution 1Solution 2 — using two variablesCode Execution — Solution 2Solution 3 — using recursionCode Execution — Solution 3Solution 4 — recursion with memoizationSolution 5 — using a generatorCode Execution — Solution 5Which solution to use?Output