fibonacci_with_and_without_memoization.md

Let's compare the fibonacci function with and without memoization to understand the performance difference.

Fibonacci without Memoization

Here's the fibonacci function without memoization:

def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(30))  # Calculates without memoization

Fibonacci with Memoization

And here's the fibonacci function with memoization using the memoize decorator:

import functools

def memoize(func):
    cache = {}
    @functools.wraps(func)
    def wrapper(*args):
        if args in cache:
            return cache[args]
        result = func(*args)
        cache[args] = result
        return result
    return wrapper

@memoize
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(30))  # Calculates with memoization

Performance Comparison

Let's see the difference in execution time for both versions. Run this program in your code editor to see the difference:

import time

# Without memoization
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

start_time = time.time()
print(fibonacci(30))  # Calculates without memoization
end_time = time.time()
print(f"Time without memoization: {end_time - start_time:.4f} seconds")

# With memoization
import functools

def memoize(func):
    cache = {}
    @functools.wraps(func)
    def wrapper(*args):
        if args in cache:
            return cache[args]
        result = func(*args)
        cache[args] = result
        return result
    return wrapper

@memoize
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

start_time = time.time()
print(fibonacci(30))  # Calculates with memoization
end_time = time.time()
print(f"Time with memoization: {end_time - start_time:.4f} seconds")

Expected Output and Explanation

Without Memoization

The calculation of fibonacci(30) involves a large number of recursive calls (approximately 2^30), which results in a significant amount of redundant computation. Execution time is much longer.

Explaination:

• Every call to fibonacci(n) recursively calls fibonacci(n-1) and fibonacci(n-2).
• This leads to a large number of repeated calculations. For example, fibonacci(28) is calculated twice, fibonacci(27) four times, and so on.
• The time complexity is exponential (O(2^n)), which makes it impractical for larger values of n.

With Memoization

The calculation of fibonacci(30) stores intermediate results in a cache, avoiding redundant computations. Execution time is significantly reduced because each Fibonacci number is computed only once.

Explaination:

• The memoize decorator caches results of function calls.
• When fibonacci(n) is called, it first checks if the result is in the cache. If it is, it returns the cached result.
• This avoids redundant calculations, reducing the time complexity to linear (O(n)).

By comparing both versions, it's clear that memoization drastically improves performance, especially for recursive functions like calculating Fibonacci numbers.