# Code-A1 (Fibonacci)
# Problem Statement: Write a program non-recursive and recursive program to calculate Fibonacci numbers and analyze their time and space complexity.

# Initalize global variables
iteration_counter = 0
recursion_counter = 0

# Iteration
def fibonacci_iteration(n):
  fib_series = []           # For storing Fibonacci series
  previous = 0              # Previous
  current = 1               # Next
  global iteration_counter  # Global iteration counter
  iteration_counter = 0     # Initialize global iteration counter to 0

  for i in range(n):
    fib_series.append(previous)
    previous, current = current, previous + current
    iteration_counter += 1

  return fib_series

# Recursion
def fibonacci_recursion(n):
  global recursion_counter # Global recursion counter
  recursion_counter += 1   # Increment recursion counter for each call

  if (n <= 0):    # Handle n less than or equal to 0
    return 0
  elif (n <= 1):  # Handle n less than or equal to 1
    return n
  else:           # Recursive call
    return fibonacci_recursion(n - 1) + fibonacci_recursion(n - 2)

n = int(input("Enter total numbers to print in fibonacci series:\t"))

# Fibonacci using iteration
fib_series = fibonacci_iteration(n)
print(f"Fibonacci using iteration:\t{fib_series}")
print(f"Iteration counter:\t{iteration_counter}| Time Complexity: O(n) (linear growth)")

print("="*80)

# Fibonacci using recursion
fib_series = []
for i in range(n):
  fib_series.append(fibonacci_recursion(i))
print(f"Fibonacci using recursion:\t{fib_series}")
print(f"Recursion counter:\t{recursion_counter} | Time Complexity: O(2^n) (exponential growth)")