"""
Fibonacci Numbers — MAT5EJ302(1) Module I
Three algorithms: exponential recursive, memoised, and iterative.
"""

import time


def fib_recursive(n):
    """Direct recursion. Time: O(phi^n) — exponential."""
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib_recursive(n - 1) + fib_recursive(n - 2)


def fib_memo(n, memo=None):
    """Memoised top-down DP. Time: O(n), Space: O(n)."""
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


def fib_iterative(n):
    """Iterative bottom-up. Time: O(n), Space: O(1)."""
    if n == 0:
        return 0
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b


def count_calls_recursive(n, counter=None):
    """Counts how many function calls fib_recursive makes."""
    if counter is None:
        counter = [0]
    counter[0] += 1
    if n <= 1:
        return n, counter
    fib_val, _ = count_calls_recursive(n - 1, counter)
    fib_val2, _ = count_calls_recursive(n - 2, counter)
    return fib_val + fib_val2, counter


if __name__ == "__main__":
    print("=== First 15 Fibonacci numbers ===")
    print([fib_iterative(i) for i in range(15)])
    print()

    print("=== Call count comparison ===")
    for n in [5, 10, 15, 20]:
        _, counter = count_calls_recursive(n, [0])
        print(f"  fib_recursive({n:>2}) makes {counter[0]:>6} calls")
    print()

    print("=== Timing comparison at n=35 ===")
    n = 35

    t0 = time.time()
    result = fib_iterative(n)
    t1 = time.time()
    print(f"  Iterative: F({n}) = {result:<10}  time = {(t1 - t0) * 1e6:.1f} microseconds")

    t0 = time.time()
    result = fib_memo(n)
    t1 = time.time()
    print(f"  Memoised:  F({n}) = {result:<10}  time = {(t1 - t0) * 1e6:.1f} microseconds")

    t0 = time.time()
    result = fib_recursive(n)
    t1 = time.time()
    print(f"  Recursive: F({n}) = {result:<10}  time = {(t1 - t0) * 1000:.1f} milliseconds")

    print()
    print("Warning: Do not run fib_recursive(n) for n > 40 — it will take too long.")