Shahrouz Nikseresht

Posted on Dec 6

Day 56: Python Fibonacci nth Term – Blazing Fast O(n) Iterative Solution with O(1) Space (No Recursion!)

#challenge #python #intermediate #programming

Welcome to Day 56 of the #80DaysOfChallenges journey! This intermediate challenge delivers the absolute best way to compute the nth Fibonacci number in Python: a linear-time iterative loop with constant space, beating the pants off naive recursion that explodes for n > 35. It uses just two variables to track the sequence, making it lightning-fast and memory-efficient even for huge n (like n=10,000).

This is the exact method used in real-world applications, competitive programming, and interviews when they ask "but can you do it without recursion or memoization?"

Example: F₀ = 0, F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, ...

If you're tired of recursion timeouts or bloated memoization tables, this "Python fast Fibonacci" solution is clean, optimal, and ready for production.

💡 Key Takeaways from Day 56: Iterative Fibonacci Function

This challenge shows the gold-standard iterative approach that runs in O(n) time and O(1) space. We'll break it down: early base cases, two-variable state tracking, and simple loop with updates.

1. Function Design: Handle Base Cases Immediately

def fibonacci(n: int) -> int:
    if n < 0:
        raise ValueError("n must be a non-negative integer")

    if n == 0:
        return 0
    if n == 1:
        return 1

Instant checks for n=0 and n=1, plus error for negative (Fibonacci not defined for negatives in this context). This makes the function bulletproof.

2. The Core Magic: Two Variables, No List Needed

    prev = 0       # F(n-2)
    curr = 1       # F(n-1)

    for _ in range(2, n + 1):
        next_value = prev + curr
        prev = curr
        curr = next_value

    return curr

This is pure genius:

Only track the last two numbers
Each iteration computes the next one
O(n) time, O(1) space
No recursion stack, no memoization overhead

For n=10: starts with prev=0, curr=1 → 1,1 → 1,2 → 2,3 → 3,5 → 5,8 → 8,13 → 13,21 → 21,34 → 34,55 → returns 55 ✓

3. Main Interactive: Easy Testing

raw = input("Enter n (non-negative integer): ").strip()

if raw == "":
    print("No input provided. Exiting.")
else:
    n = int(raw)
    result = fibonacci(n)
    print(f"Fibonacci number F{n} =", result)

Clean input, error-free, ready to test huge numbers.

🎯 Summary and Reflections

This Fibonacci implementation is perfect: fast, memory-efficient, readable, and handles huge n without crashing. It reinforced:

Space matters: O(1) beats O(n) memoization for large n
Iteration > Recursion: No stack overflow, ever
State tracking pattern: Two variables for sequences is a superpower

This is the version I use in every real project. Recursion is cute for teaching, but this is production.

Advanced Alternatives:

Matrix exponentiation for O(log n) time
Closed-form Binet's formula (with rounding)
Generator for infinite sequence

But for 99.9% of cases, this iterative version is king.

🚀 Next Steps and Resources

Day 56 gave you the fastest practical Fibonacci in Python. Try n=1000, it’s instant!

Source Code for Challenge #56: scripts/fibonacci.py
Main Repository: 80-days-of-challenges
Daily Updates: Twitter/X (@Shahrouzlogs)

What's the largest n you computed? Drop it below, I dare you! 🔥

DEV Community