#Iterative Method
# Time Complexity: O(n) Space Complexity: O(1)
def fib_iterative(n):
  a = 0
  b = 1
  if n <= 1:
    return n
  for i in range(2, n+1):
    c = a + b
    a = b
    b = c
  return b

# Print series
def fib_series_iter(n):
  a = 0
  b = 1
  print(a, b, end=" ")
  for i in range(2, n):
    c = a + b
    print(c, end=" ")
    a = b
    b = c
fib_series_iter(10)

#Recursive Method
#Time Complexity: O(2ⁿ) Space Complexity: O(n)
def fib_recursive(n):
  if n <= 1:
    return n
  return fib_recursive(n-1) + fib_recursive(n-2)

# Print series
def fib_series_recursive(n):
  for i in range(n):
    print(fib_recursive(i), end=" ")
fib_series_recursive(10)

#Recursion with Memoization
# Time Complexity: O(n) Space Complexity: O(n)
def fib_memo(n, memo={}):
  if n in memo:
    return memo[n]
  if n <= 1:
    memo[n] = n
  else:
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
  return memo[n]

# Print series
def fib_series_memo(n):
  for i in range(n):
    print(fib_memo(i), end=" ")
fib_series_memo(10)