Abstract

The Fibonacci sequence — 0, 1, 1, 2, 3, 5, 8, 13, 21, …0, 1, 1, 2, 3, 5, 8, 13, 21, … — is the most famous integer sequence in mathematics. Each number is the sum of the previous two. It is a perfect teaching tool: trivial to define, deeply connected to the golden ratio, and a textbook example for comparing algorithm strategies. In this project you will implement six different ways to generate it — iterative, recursive, memoized recursive, generator-based, closed-form using the golden ratio, and matrix exponentiation — and learn when each one is appropriate.

You will leave understanding:

• The definition: F(0) = 0F(0) = 0, F(1) = 1F(1) = 1, F(n) = F(n-1) + F(n-2)F(n) = F(n-1) + F(n-2).
• Why naïve recursion is exponentially slow.
• How memoization turns it into linear time.
• The golden-ratio closed form (and its precision limits).
• Matrix exponentiation in O(log n)O(log n) for huge nn.
• Why iterative is almost always the right answer in practice.

Prerequisites

• Python 3.6 or above.
• A text editor or IDE.
• Comfort with loops, recursion (helpful), and functions.

Getting Started

Create the project

1. Create folder fibonacci-generatorfibonacci-generator.
2. Inside, create fibonacci_sequence_generator.pyfibonacci_sequence_generator.py.

Write the code

# Fibonacci Sequence Generator
 
# The Fibonacci sequence is a series of numbers where a number is the addition of the last two numbers, starting with 0, and 1. The Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
 
n = int(input("How many numbers that generates?: "))
n1 = 0
n2 = 1
count = 0
 
if n <= 0:
    print("Please enter a positive integer")
elif n == 1:
    print("Fibonacci sequence upto", n, ":")
    print(n1)
else:
    print("Fibonacci sequence:")
    while count < n:
        print(n1)
        nth = n1 + n2
        # update values
        n1 = n2
        n2 = nth
        count += 1

# Fibonacci Sequence Generator
 
# The Fibonacci sequence is a series of numbers where a number is the addition of the last two numbers, starting with 0, and 1. The Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
 
n = int(input("How many numbers that generates?: "))
n1 = 0
n2 = 1
count = 0
 
if n <= 0:
    print("Please enter a positive integer")
elif n == 1:
    print("Fibonacci sequence upto", n, ":")
    print(n1)
else:
    print("Fibonacci sequence:")
    while count < n:
        print(n1)
        nth = n1 + n2
        # update values
        n1 = n2
        n2 = nth
        count += 1

Run it

C:\Users\Your Name\fibonacci-generator> python fibonacci_sequence_generator.py
How many numbers? 10
Fibonacci sequence:
0
1
1
2
3
5
8
13
21
34

C:\Users\Your Name\fibonacci-generator> python fibonacci_sequence_generator.py
How many numbers? 10
Fibonacci sequence:
0
1
1
2
3
5
8
13
21
34

Step-by-Step Explanation

1. Iterative version (the default)

def fib_iter(n: int) -> list[int]:
    if n <= 0: return []
    if n == 1: return [0]
    out = [0, 1]
    while len(out) < n:
        out.append(out[-1] + out[-2])
    return out

def fib_iter(n: int) -> list[int]:
    if n <= 0: return []
    if n == 1: return [0]
    out = [0, 1]
    while len(out) < n:
        out.append(out[-1] + out[-2])
    return out

• O(n) time, O(n) space (storing the list).
• Single allocation, no recursion overhead.
• This is what 95 % of real-world Fibonacci code looks like.

2. Bare minimum — just compute F(n)

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

• O(n) time, O(1) space.
• The tuple assignment a, b = b, a + ba, b = b, a + b is the Pythonic way to swap-and-update.

Other Implementations

3. Naïve recursive (DO NOT use for large n)

def fib_rec(n: int) -> int:
    if n < 2: return n
    return fib_rec(n - 1) + fib_rec(n - 2)

def fib_rec(n: int) -> int:
    if n < 2: return n
    return fib_rec(n - 1) + fib_rec(n - 2)

• O(2^n) time. fib_rec(35)fib_rec(35) takes seconds; fib_rec(50)fib_rec(50) takes minutes.
• The same subproblems are recomputed billions of times.
• Educational only — never ship this.

4. Memoized recursive

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n < 2: return n
    return fib_memo(n - 1) + fib_memo(n - 2)

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n < 2: return n
    return fib_memo(n - 1) + fib_memo(n - 2)

• O(n) time, O(n) space.
• One decorator turns exponential into linear.
• Best example you will ever see of @lru_cache@lru_cache’s value.

5. Generator-based (memory-efficient)

def fib_gen():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b
 
# usage
import itertools
print(list(itertools.islice(fib_gen(), 10)))

def fib_gen():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b
 
# usage
import itertools
print(list(itertools.islice(fib_gen(), 10)))

• O(1) extra memory regardless of how far you go.
• Lazy — computes only as many as you ask for.
• Great when you want “the first N matching some condition” without precomputing.

6. Closed form (Binet’s formula)

import math
PHI = (1 + math.sqrt(5)) / 2
PSI = (1 - math.sqrt(5)) / 2
 
def fib_binet(n: int) -> int:
    return round((PHI**n - PSI**n) / math.sqrt(5))

import math
PHI = (1 + math.sqrt(5)) / 2
PSI = (1 - math.sqrt(5)) / 2
 
def fib_binet(n: int) -> int:
    return round((PHI**n - PSI**n) / math.sqrt(5))

• O(1) time (constant-time arithmetic).
• Loses precision past n ≈ 70n ≈ 70 because of floating-point rounding.
• Beautiful mathematically; not what you ship.

7. Matrix exponentiation (O(log n)O(log n))

def fib_matrix(n: int) -> int:
    def mat_mul(A, B):
        return [
            [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
            [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]],
        ]
    def mat_pow(M, p):
        result = [[1, 0], [0, 1]]            # identity
        while p:
            if p & 1: result = mat_mul(result, M)
            M = mat_mul(M, M)
            p >>= 1
        return result
    if n == 0: return 0
    return mat_pow([[1, 1], [1, 0]], n)[0][1]

def fib_matrix(n: int) -> int:
    def mat_mul(A, B):
        return [
            [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
            [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]],
        ]
    def mat_pow(M, p):
        result = [[1, 0], [0, 1]]            # identity
        while p:
            if p & 1: result = mat_mul(result, M)
            M = mat_mul(M, M)
            p >>= 1
        return result
    if n == 0: return 0
    return mat_pow([[1, 1], [1, 0]], n)[0][1]

• O(log n) time using fast exponentiation.
• Uses arbitrary-precision Python ints — no precision loss for huge n.
• fib_matrix(1_000_000)fib_matrix(1_000_000) computes in milliseconds.

Comparing the Approaches

*Constant-time only if you treat float ops as O(1). Above n ≈ 70 it returns wrong values.

Algorithm Walkthrough — Iterative for n = 5

init      a=0  b=1
step 1    yield 0;  a=1, b=1
step 2    yield 1;  a=1, b=2
step 3    yield 1;  a=2, b=3
step 4    yield 2;  a=3, b=5
step 5    yield 3;  a=5, b=8
result:   0, 1, 1, 2, 3

init      a=0  b=1
step 1    yield 0;  a=1, b=1
step 2    yield 1;  a=1, b=2
step 3    yield 1;  a=2, b=3
step 4    yield 2;  a=3, b=5
step 5    yield 3;  a=5, b=8
result:   0, 1, 1, 2, 3

Input Validation

def get_n():
    while True:
        raw = input("How many? ")
        try:
            n = int(raw)
            if n < 0:
                raise ValueError
            return n
        except ValueError:
            print("Enter a non-negative integer.")

def get_n():
    while True:
        raw = input("How many? ")
        try:
            n = int(raw)
            if n < 0:
                raise ValueError
            return n
        except ValueError:
            print("Enter a non-negative integer.")

Reject negative numbers and non-integers up front.

Common Mistakes

The Golden Ratio Connection

The ratio of consecutive Fibonacci numbers approaches φ ≈ 1.61803398875…, the golden ratio:

for n in [5, 10, 20, 40, 80]:
    print(n, fib(n+1) / fib(n))
# 1.6, 1.617..., 1.6180..., 1.61803..., 1.61803398875...

for n in [5, 10, 20, 40, 80]:
    print(n, fib(n+1) / fib(n))
# 1.6, 1.617..., 1.6180..., 1.61803..., 1.61803398875...

This is why Binet’s formula works — φφ is a root of x² = x + 1x² = x + 1, the characteristic equation of the Fibonacci recurrence.

Variations to Try

1. Sum of Fibonacci numbers

def fib_sum(n): return sum(fib_iter(n))

def fib_sum(n): return sum(fib_iter(n))

Surprising identity: F(0) + F(1) + … + F(n) = F(n+2) - 1F(0) + F(1) + … + F(n) = F(n+2) - 1.

2. Even-only Fibonacci (Project Euler #2)

total = 0
a, b = 0, 1
while a < 4_000_000:
    if a % 2 == 0: total += a
    a, b = b, a + b

total = 0
a, b = 0, 1
while a < 4_000_000:
    if a % 2 == 0: total += a
    a, b = b, a + b

3. Plot the sequence

import matplotlib.pyplot as plt
plt.plot(fib_iter(30), "o-"); plt.yscale("log"); plt.show()

import matplotlib.pyplot as plt
plt.plot(fib_iter(30), "o-"); plt.yscale("log"); plt.show()

On a log scale, Fibonacci grows almost linearly — exponential growth made visual.

4. Spiral drawing

Use turtleturtle to draw the famous Fibonacci spiral by chaining quarter-circles whose radii follow the sequence.

5. nth Fibonacci modulo m (Pisano period)

For very large n with a modulus, the sequence is periodic — useful in cryptography and contest programming.

6. Tribonacci, Lucas, Pell sequences

Same recurrence pattern, different starting values. Easy variations to implement once you have Fibonacci.

7. Find n such that F(n) > 10^k

Useful interview question — combine with a generator and a counter.

8. Performance benchmark

Time each method for n in [10, 30, 100, 1000, 100_000][10, 30, 100, 1000, 100_000]. Plot results with matplotlib.

9. Decimal version

For really, really huge n, Python’s int already supports arbitrary precision. Try len(str(fib(10_000_000)))len(str(fib(10_000_000))) — you will get over 2 million digits.

10. Web API

Wrap with Flask: GET /fib/<n>GET /fib/<n> returns JSON {"n": n, "value": fib(n)}{"n": n, "value": fib(n)}. See Basic Web Server.

Real-World Connections

The sequence appears in:

• Nature — sunflower seed spirals, pinecone scales, nautilus shells, flower petals.
• Markets — Elliott Wave theory and Fibonacci retracement levels (anecdotal at best).
• Algorithms — Fibonacci heaps (used in Dijkstra/Prim shortest-path).
• Number theory — Zeckendorf’s theorem: every positive integer is a unique sum of non-adjacent Fibonacci numbers.
• Computer science — F-heaps, Fibonacci search, golden-ratio-based hashing.

Educational Value

• Algorithmic thinking — six different solutions, six different trade-offs.
• Recursion vs. iteration — both kinds of repetition compared head to head.
• Memoization (@lru_cache@lru_cache) — one decorator, exponential speed-up.
• Generators — laziness as a tool.
• Closed forms and their limits — math vs. machine.
• Fast exponentiation — divide-and-conquer over a sequence.

Next Steps

• Run a benchmark harness comparing iterative, memoized, and matrix versions.
• Implement Tribonacci and Lucas sequences using the same patterns.
• Combine with Reverse a String to see another “many ways to solve” project.
• Read about Pisano periods for modular Fibonacci.
• Try Project Euler problem #2 using your generator.

Conclusion

Fibonacci is a one-line problem that pays off in spades the deeper you look. You implemented six solutions, learned why exponential recursion is a punishment, and saw how a single @lru_cache@lru_cache line rewrites the algorithm class. The same trade-offs recur in real systems — choosing iterative vs. recursive, caching vs. recomputing, fast paths vs. fallbacks. Full source on GitHub. Find more algorithm projects on Python Central Hub.