Fibonacci Series in Python: Loop, Recursion, Memoization

Three Python programs cover the Fibonacci series question at every level: iterative, recursive, and memoized. The difference between them matters directly in placement coding rounds, where the follow-up question is almost always “now make it faster.”

What Is the Fibonacci Series?

The Fibonacci series is a sequence of numbers where each term equals the sum of the two terms before it. It starts at 0 and 1:

• Term 0: 0
• Term 1: 1
• Term 2: 0 + 1 = 1
• Term 3: 1 + 1 = 2
• Term 4: 1 + 2 = 3
• Term 5: 2 + 3 = 5
• Term 6: 3 + 5 = 8
• Term 7: 5 + 8 = 13

The full sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

This sequence appears in placement coding rounds because it tests three skills at once: loop control, recursion, and optimisation awareness. Knowing one version isn’t enough. Placement screeners at IT companies routinely ask for the recursive version and then ask you to explain why it’s slow for large inputs.

The sequence also comes up in discussions about algorithm design patterns. In CS interviews, Fibonacci numbers are a standard benchmark for demonstrating why memoization and dynamic programming reduce exponential problems to linear ones.

Before writing any Fibonacci code, confirm two things: you understand how to update two variables in a loop, and you know what a recursive base case is. If either of those is shaky, work through the Python basic programs collection first and return here.

Method 1: Fibonacci Using a While Loop

The iterative approach uses two variables, a and b, that always hold the last two Fibonacci numbers. In each step, the loop prints a, then shifts both variables one position forward.

The algorithm:

• Set a = 0, b = 1, count = 0
• While count < n, print a, then update: a, b = b, a + b
• Increment count by 1 each iteration

# Fibonacci series using a while loop
n = int(input("Enter number of terms: "))
a, b = 0, 1
count = 0
print("Fibonacci series:", end=" ")
while count < n:
    print(a, end=" ")
    a, b = b, a + b
    count += 1

Sample run for n = 5:

• Input: 5
• Output: Fibonacci series: 0 1 1 2 3

The simultaneous assignment a, b = b, a + b is the cleanest Python idiom here. Python evaluates the right side completely before assigning, so no temporary variable is needed. The same variable-swap pattern appears in sum of array elements and other accumulation problems, making it worth internalising early.

For placement rounds, this iterative version is the expected implementation when the question is “print the first n Fibonacci numbers.” It runs in O(n) time and uses O(1) space, handling any value of n without hitting stack limits.

Method 2: Fibonacci Using Recursion

The recursive version translates the mathematical definition directly into code: fib(n) = fib(n-1) + fib(n-2), with base cases at 0 and 1.

The algorithm:

• Base case: if n == 0, return 0
• Base case: if n == 1, return 1
• Recursive case: return fibonacci(n - 1) + fibonacci(n - 2)

# Fibonacci series using recursion
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

terms = int(input("Enter number of terms: "))
print("Fibonacci series:", end=" ")
for i in range(terms):
    print(fibonacci(i), end=" ")

Sample run for n = 5:

• Input: 5
• Output: Fibonacci series: 0 1 1 2 3

The recursive version is short and mirrors the mathematical definition. That’s why placement screeners like it as the opening question. The follow-up is where most students lose marks.

To compute fibonacci(5), Python calls fibonacci(4) and fibonacci(3). Computing fibonacci(4) requires fibonacci(3) and fibonacci(2). fibonacci(3) runs twice, fibonacci(2) three times, and the redundancy compounds with every level. Time complexity is O(2^n), making the naive version unusable for n much above 35 on a standard machine.

The space complexity is O(n), because the call stack grows to depth n before any call returns. For a Tier-2 or Tier-3 college placement round, being able to state both complexities and explain the overlapping-subproblem issue is the complete answer screeners look for.

The Armstrong number check uses a similar loop-and-condition structure but stays iterative throughout, making it a useful contrast for understanding when recursion adds clarity versus when it adds cost.

Method 3: Memoized Fibonacci with lru_cache

Memoization solves the redundancy by caching the result of each fibonacci(n) call the first time it runs. Every subsequent call with the same argument returns the cached result immediately. Time complexity drops from O(2^n) to O(n).

Python’s standard library provides functools.lru_cache, which attaches memoization to any function with a single decorator line. No manual dictionary management required.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

terms = int(input("Enter number of terms: "))
print("Fibonacci series:", end=" ")
for i in range(terms):
    print(fibonacci(i), end=" ")

Sample run for n = 5:

• Input: 5
• Output: Fibonacci series: 0 1 1 2 3

One practical note: Python’s default recursion depth limit is 1000 calls. For large n, the memoized recursive version still hits this ceiling. Python’s sys.setrecursionlimit can raise the limit, but for very large sequences the iterative version is the better choice: O(n) time with O(1) space, and no risk of stack overflow.

The maxsize=None setting in @lru_cache(maxsize=None) tells Python to cache every unique argument without any eviction limit. For Fibonacci this is safe because n only grows upward during a single print loop. In production code with unbounded inputs, you would set a finite maxsize.

Which Approach to Use in Placement Coding Rounds?

Approach	Time	Space	Use when
While loop (iterative)	O(n)	O(1)	Default choice for large n
Recursive (naive)	O(2^n)	O(n)	Small n or explaining the concept
Memoized recursive	O(n)	O(n)	Recursion required, correctness at scale

The expected answer sequence in a Tier-2/Tier-3 college placement round:

• Write the recursive solution first — it’s readable and shows you know recursion
• State the O(2^n) time complexity and explain why: overlapping subproblems, exponential call tree
• Offer the iterative or memoized version as the optimisation
• Note that Python integers handle arbitrarily large Fibonacci numbers without overflow

That four-step answer demonstrates code fluency, complexity analysis, knowledge of a standard optimisation technique, and Python internals awareness. Screeners at IT companies hiring freshers rank exactly these four skills when evaluating placement coding submissions.

The jump from O(2^n) to O(n) via @lru_cache is the same caching pattern that production engineers apply when storing AI model responses and embedding lookups. TinkerLLM is where you test that reasoning on real data. At ₹299 entry, it costs less than most placement-prep books.