nth_fibonacci.py

def nth_fib_basic(n: int) -> int:
  """use iteration to find the nth fibonacci number
  
  :param n: the index of the desired fibonacci number
  :return: the nth fibonacci number
  """
  if n <= 1:
    return n
  if n == 2:
    return 1
  
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a + b

  return a


def nth_fib_recursive(n: int) -> int:
  """use recursion to find the nth fibonacci number
  
  :param n: the index of the desired fibonacci number
  :return: the nth fibonacci number
  """
  if n <= 1:
    return n
  if n == 2:
    return 1
  else:
    return nth_fib_recursive(n - 1) + nth_fib_recursive(n - 2)

  
def nth_fib_dynamic(n: int, fib_series: list) -> int:
  """use dynamic programming to optimize finding the nth fibonacci number
  by removing duplicate calculations
  
  :param n: the index of the desired fibonacci number
  :param fib_series: a list of previously calculated fibonacci numbers
  :return: the nth fibonacci number
  """
  if len(fib_series) < n + 1:
    for _ in range((n + 1) - len(fib_series)):
      fib_series.append(0)
  if n <= 1:
    return n
  if n == 2:
    return 1
  else:
    if fib_series[n - 1] == 0:
      fib_series[n - 1] = nth_fib_dynamic(n - 1, fib_series)
    if fib_series[n - 2] == 0:
      fib_series[n - 2] = nth_fib_dynamic(n - 2, fib_series)
    
    fib_series[n] = fib_series[n - 1] + fib_series[n - 2]
  
  return fib_series[n]