Fibonacci Sequence Generator

Abstract

The Fibonacci sequence — 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) = 0, F(1) = 1, 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) for huge n.
• 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-generator.
2. Inside, create fibonacci_sequence_generator.py.

Write the code

Fibonacci Generator

pch.viewSource

Fibonacci Generator

"""Fibonacci sequence — seven implementations, timed against each other.

The sequence itself is a one-liner. What makes it worth a project is that it
has a genuinely wide range of correct implementations, from O(2^n) to O(log n),
and running them side by side turns "recursion is slow" into a number.

Run it with no arguments for the demo, or `python fibonacci_sequence_generator.py 20`.
"""

import itertools
import math
import sys
import time
from functools import lru_cache

PHI = (1 + math.sqrt(5)) / 2
PSI = (1 - math.sqrt(5)) / 2


def fib_iter(n: int) -> list[int]:
    """The first n terms as a list. O(n) time, O(n) space.

    This is what most real Fibonacci code looks like: one allocation, no
    recursion, and the whole sequence available afterwards.
    """
    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(n: int) -> int:
    """Just F(n). O(n) time, O(1) space — nothing is stored along the way."""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


def fib_rec(n: int) -> int:
    """Naive recursion. O(2^n) — correct, and unusable past about n=35."""
    if n < 2:
        return n
    return fib_rec(n - 1) + fib_rec(n - 2)


@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    """The same recursion with a cache. One decorator turns 2^n into n."""
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)


def fib_gen():
    """An endless generator. O(1) extra memory however far you go."""
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b


def fib_binet(n: int) -> int:
    """Closed form. Constant time, and wrong past n ~ 70 in float64."""
    return round((PHI ** n - PSI ** n) / math.sqrt(5))


def mat_mul(a, b):
    """Multiply two 2x2 matrices, written out rather than looped.

    Four multiplications and two additions. A general matmul would loop, but
    at this size the loop overhead is larger than the arithmetic it saves.
    """
    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(matrix, power):
    """Exponentiation by squaring: O(log n) multiplications, not O(n).

    Reading `power` in binary, each 1 bit contributes the current square. So
    the 1,000,000th power costs 20 multiplications rather than a million.
    """
    result = [[1, 0], [0, 1]]                   # identity
    while power:
        if power & 1:
            result = mat_mul(result, matrix)
        matrix = mat_mul(matrix, matrix)
        power >>= 1
    return result


def fib_matrix(n: int) -> int:
    """Matrix exponentiation. O(log n) multiplications by squaring."""
    return mat_pow([[1, 1], [1, 0]], n)[0][1]


def fib_sum(n: int) -> int:
    """Sum of the first n Fibonacci numbers -- without adding them up.

    The identity is F(0)+...+F(n-1) = F(n+1) - 1, so the whole sum costs one
    more Fibonacci call. Worth knowing because it turns an O(n) loop into
    whatever the underlying F() costs.
    """
    return fib(n + 1) - 1


def get_n(prompt: str = "How many numbers? ", default: int = 12) -> int:
    """Ask until the answer is a positive integer.

    `int(input())` raises on "twelve" and accepts "-5", and neither is a
    count. Validation is the difference between a script that scolds the user
    and one that crashes at them.
    """
    while True:
        raw = ask_line(prompt, str(default))
        try:
            value = int(raw)
        except ValueError:
            print(f"'{raw}' is not a whole number.")
            continue
        if value < 0:
            print("A count cannot be negative.")
            continue
        if value > 100_000:
            print("That will take a while -- pick something under 100,000.")
            continue
        return value


def ask_line(prompt: str, default: str) -> str:
    """One line of input, or `default` when nobody is there to type."""
    try:
        return input(prompt).strip() or default
    except EOFError:
        print(f"{default}   (no input available, using the default)")
        return default


def ask(prompt: str, default: int) -> int:
    """Read a count, falling back to `default` when nobody is there to type.

    A script that dies with EOFError the moment it is run without a terminal
    cannot be tested, scheduled or demonstrated. Handling that is three lines.
    """
    if len(sys.argv) > 1 and sys.argv[1].isdigit():
        return int(sys.argv[1])
    try:
        answer = input(prompt).strip()
    except EOFError:
        return default
    return int(answer) if answer.isdigit() else default


def check(count: int = 25) -> bool:
    """Every implementation must agree before any timing means anything."""
    expected = fib_iter(count)
    generated = list(itertools.islice(fib_gen(), count))
    checks = {
        "fib(n)": [fib(i) for i in range(count)],
        "fib_rec": [fib_rec(i) for i in range(count)],
        "fib_memo": [fib_memo(i) for i in range(count)],
        "fib_gen": generated,
        "fib_binet": [fib_binet(i) for i in range(count)],
        "fib_matrix": [fib_matrix(i) for i in range(count)],
    }
    print(f"agreement over the first {count} terms:")
    everything_matches = True
    for name, values in checks.items():
        matches = values == expected
        everything_matches &= matches
        print(f"  {name:11} {'matches' if matches else 'DIFFERS'}")
    return everything_matches


def timings(n: int = 28) -> None:
    print(f"\ntime to compute F({n}), lower is better:")
    fib_memo.cache_clear()
    methods = (("fib_rec (naive)", fib_rec), ("fib_memo", fib_memo),
               ("fib (loop)", fib), ("fib_binet", fib_binet),
               ("fib_matrix", fib_matrix))
    baseline = None
    for name, function in methods:
        started = time.perf_counter()
        function(n)
        elapsed = time.perf_counter() - started
        baseline = elapsed if baseline is None else baseline
        print(f"  {name:16} {elapsed * 1000:9.3f} ms   "
              f"{baseline / elapsed:>8,.0f}x faster than naive"
              if elapsed else f"  {name:16} {elapsed * 1000:9.3f} ms")


def precision_limit() -> None:
    print("\nwhere the closed form stops being exact:")
    for n in (10, 40, 70, 71, 75, 90):
        exact = fib(n)
        approximate = fib_binet(n)
        mark = "exact" if exact == approximate else f"off by {approximate - exact}"
        print(f"  F({n:2}) = {exact:<20} binet {mark}")


def digit_count(n: int) -> int:
    """How many decimal digits `n` has, without building the string.

    `len(str(n))` is the obvious version and it raises on anything past 4,300
    digits: CPython 3.11 capped int-to-str conversion, because the algorithm
    is quadratic and a single `str(huge)` was a denial-of-service vector. The
    bit length times log10(2) sidesteps the whole conversion.
    """
    if n == 0:
        return 1
    return int(n.bit_length() * math.log10(2)) + 1


def big_n(n: int = 100_000) -> None:
    """The O(log n) method against the O(n) one, where the gap shows."""
    print(f"\ncomputing F({n:,}) two ways:")
    started = time.perf_counter()
    by_matrix = fib_matrix(n)
    matrix_time = time.perf_counter() - started

    started = time.perf_counter()
    by_loop = fib(n)
    loop_time = time.perf_counter() - started

    print(f"  fib_matrix  {matrix_time * 1000:8.1f} ms")
    print(f"  fib (loop)  {loop_time * 1000:8.1f} ms   "
          f"{loop_time / matrix_time:.1f}x slower")
    print(f"  same answer: {by_matrix == by_loop}, "
          f"{digit_count(by_matrix):,} digits long")


def main() -> None:
    count = ask("How many numbers to generate?: ", 12)
    print(f"Fibonacci sequence, first {count} terms:")
    print("  " + ", ".join(str(value) for value in fib_iter(count)))
    print()
    if not check():
        raise SystemExit("implementations disagree")
    timings()
    precision_limit()
    print(f"\nsum of the first {count} terms: {fib_sum(count)} "
          f"(checked against adding them up: {sum(fib_iter(count))})")
    big_n()
    print("\nseven ways to compute the same numbers. The loop is what you")
    print("ship; the rest are here because the gaps between them are the")
    print("whole lesson.")


if __name__ == "__main__":
    main()

Run it

command

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

What it produces

Running the file exactly as it ships takes 0.3 s and prints:

python fibonacci_sequence_generator.py

How many numbers to generate?: Fibonacci sequence, first 12 terms:
  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
 
agreement over the first 25 terms:
  fib(n)      matches
  fib_rec     matches
  fib_memo    matches
  fib_gen     matches
  fib_binet   matches
  fib_matrix  matches
 
time to compute F(28), lower is better:
  fib_rec (naive)     60.863 ms          1x faster than naive
  fib_memo             0.042 ms      1,463x faster than naive
  fib (loop)           0.005 ms     12,950x faster than naive
  fib_binet            0.007 ms      9,364x faster than naive
  fib_matrix           0.009 ms      6,763x faster than naive
 
where the closed form stops being exact:
  F(10) = 55                   binet exact
...

The first 20 of 36 lines are shown; the run continues past this point.

How it fits together

Read from the top: this is what runs when you execute the file, and which function calls which. It is generated from the code, so it cannot drift from it.

diagram Diagram mermaid

  flowchart TD
  RUN(["python fibonacci_sequence_generator.py"])
  fib_iter("fib_iter")
  fib("fib")
  fib_rec("fib_rec")
  fib_memo("fib_memo")
  fib_gen("fib_gen")
  fib_binet("fib_binet")
  fib_matrix("fib_matrix")
  ask("ask")
  check("check")
  timings("timings")
  precision_limit("precision_limit")
  main("main")
  RUN --> main
  check --> fib
  check --> fib_binet
  check --> fib_gen
  check --> fib_iter
  check --> fib_matrix
  check --> fib_memo
  check --> fib_rec
  main --> ask
  main --> check
  main --> fib_iter
  main --> precision_limit
  main --> timings
  precision_limit --> fib
  precision_limit --> fib_binet

Step-by-Step Explanation

1. Iterative version (the default)

iterative.py

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)

fib_n.py

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 + b is the Pythonic way to swap-and-update.

Other Implementations

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

naive_rec.py

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) takes seconds; fib_rec(50) takes minutes.
• The same subproblems are recomputed billions of times.
• Educational only — never ship this.

4. Memoized recursive

memo_rec.py

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’s value.

5. Generator-based (memory-efficient)

gen.py

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)

binet.py

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 ≈ 70 because of floating-point rounding.
• Beautiful mathematically; not what you ship.

7. Matrix exponentiation (O(log n))

matrix.py

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) computes in milliseconds.

Comparing the Approaches

Method	Time	Space	When to use
Iterative	O(n)	O(1)	Default choice
Naïve recursion	O(2^n)	O(n)	Never (teaching only)
Memoized recursion	O(n)	O(n)	Demonstrating DP / cache
Generator	O(n) total	O(1)	Streaming or unknown count
Binet’s formula	O(1)*	O(1)	Tiny n, accept FP error
Matrix exponentiation	O(log n)	O(1)	Massive n

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

Algorithm Walkthrough — Iterative for n = 5

text

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

validate.py

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

Problem	Cause	Fix
RecursionError	Naïve recursion past ~1000	Use the iterative version
Hang on n=40	Naïve recursion’s exponential blow-up	Switch to memoized or iterative
Wrong result for n>70	Floating-point precision in Binet	Use integer-based methods
IndexError for n=0 or n=1	Hard-coded out[-2]	Special-case small n
Memory ballooning for huge n	Storing the full list	Use the generator if you only need streaming

The Golden Ratio Connection

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

phi.py

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 + 1, the characteristic equation of the Fibonacci recurrence.

Variations to Try

1. Sum of Fibonacci numbers

sum.py

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

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

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

even.py

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

plot.py

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 turtle 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]. 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))) — you will get over 2 million digits.

10. Web API

Wrap with Flask: GET /fib/<n> returns JSON {"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) — 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 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.

Pitfalls

• The naive recursion’s cost is the answer. Computing F(30) takes 2,692,537 calls — exactly 2*F(31)-1, checked in the exercise below at five values of n. The work grows as fast as the sequence does, which is why n=50 is not slow but hopeless.
• @lru_cache turns that into n+1 calls. Measured: 31 calls for n=30, an 86,856x reduction from one decorator. It also means the cache persists between calls, so any timing loop must call cache_clear() first or it measures a dictionary lookup.
• Binet’s formula stops being exact at n=71. F(70) is right; F(71) is off by 1, F(75) by 5, F(90) by 8,584. A closed form in float64 has 53 bits of mantissa, and Fibonacci numbers outgrow it.
• len(str(n)) raises on very large integers. CPython 3.11 capped int-to-str conversion at 4,300 digits, so asking a 20,899-digit Fibonacci number for its length crashes. n.bit_length() * log10(2) sidesteps it.
• Recursion has a hard ceiling. Python’s default limit is 1,000 frames, so fib_rec(2000) raises RecursionError regardless of how long you wait.

Recap

• Seven implementations, all checked to agree over the first 25 terms before any of them is timed.
• F(28) on this machine: naive recursion 268.8 ms, memoised 0.149 ms, the plain loop 0.010 ms.
• F(100,000): matrix exponentiation 43.8 ms, the O(n) loop 337.3 ms — 7.7x slower, same 20,899-digit answer.
• mat_pow does 17 squarings for n=100,000 instead of 100,000 additions; exponentiation by squaring is the whole trick.
• The sum identity F(0)+...+F(n-1) = F(n+1)-1 turns an O(n) sum into one extra Fibonacci call — verified in the program’s own output.

pch.quizTag pch.quizDefaultTitle

1. Naive recursion needs 2,692,537 calls to compute F(30), which is 832,040. What is the relationship?

   A Coincidence B The call count is exactly 2*F(n+1)-1 — the recursion recomputes subtrees, so its cost grows at the same rate as the sequence itself C The calls are proportional to n squared D The count depends on the machine
   pch.quizShowAnswer

   B — The call count is exactly 2*F(n+1)-1 — the recursion recomputes subtrees, so its cost grows at the same rate as the sequence itself

2. Binet's closed form gives F(70) correctly but F(71) off by one. Why?

   A The formula is wrong B float64 carries 53 bits of mantissa, and F(71) needs more precision than that — the formula is exact in real arithmetic and approximate in floating point C Python rounds incorrectly D The golden ratio constant is mistyped
   pch.quizShowAnswer

   B — float64 carries 53 bits of mantissa, and F(71) needs more precision than that — the formula is exact in real arithmetic and approximate in floating point

3. Why does matrix exponentiation beat the loop for F(100,000) but not for F(28)?

   A It is always faster and the small case is measurement noise B It does O(log n) multiplications instead of O(n) additions, so it only pays off once n is large — at n=28 the loop's 28 additions beat the setup cost C The loop uses more memory D Matrices are faster only for even n
   pch.quizShowAnswer

   B — It does O(log n) multiplications instead of O(n) additions, so it only pays off once n is large — at n=28 the loop's 28 additions beat the setup cost

Try it yourself

pch.exerciseTag pch.exerciseTitle