Examples:

Problem 1: Fibonacci

The Fibonacci sequence is a series where each number is the sum of the two preceding ones, typically starting with 0 and 1.

• Recursive (Simple but Inefficient):

This follows the mathematical definition but is slow for large n due to redundant calculations, running in O(2^n) time.

1
2
3
4
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

• Memoization (Optimized Recursion):

Stores previously computed values to avoid recalculation, drastically improving performance to O(n) time.

1
2
3
4
5
6
7
from functools import lru_cache

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

• Common Implementation Methods

Iterative (Most Efficient for Small to Medium ): This method uses a loop and two variables to track the sequence, running in O(n) time with O(1) space.

1
2
3
4
5
def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        print(a, end=' ')
        a, b = b, a + b

• Generators (Memory Efficient):

Yields numbers one at a time, which is useful for processing infinite sequences without storing them all in memory.

1
2
3
4
5
def fibonacci_generator(n):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b