# fibsLib.py
# info: https://en.wikipedia.org/wiki/Fibonacci_sequence
# input: 22 or 23 or 26
'''
  functions for calculating the Fibonacci numbers.
  Start the sequence with 0, 1, for fib(0), fib(1)
'''

import math
# import decimal
from decTrig import *


PHI_F = (1 + math.sqrt(5)) / 2


def fibRec(n):
  if n <= 0:  # base cases
    return 0
  elif n == 1:  
    return 1
  else:
    return fibRec(n-1) + fibRec(n-2)
  

def fibIter(n):
  a = 0   # first fibonacci numbers: F0, F1
  b = 1
  if n <= 0:
    return a
  elif n == 1:
    return b
  else:
    for i in range(2, n+1):
      a, b = b, a + b
    return b


# ------------ other integer approaches -------------


fibsStore = [0, 1]
numCalls = 0

def fibMemo(n):
  global numCalls
  numCalls += 1

  if n < len(fibsStore):
    return fibsStore[n]
  else:
    res = fibMemo(n-1) + fibMemo(n-2)
    fibsStore.append(res)
    return res


def fibGen():
  # generator that never stops
  current = 0 # first fibonacci numbers
  b = 1
  while True:
    yield current
    current, b = b, current+b


def fibs(n):
  # return the first n fibs
  gen = fibGen()
  return [ next(gen) for _ in range(n+1) ]


# ---------- approximation ---------

def fibPhi(n): # Binet's formula
  return (PHI_F**n - (1-PHI_F)**n)/ math.sqrt(5)

def fibPhiD(n):
  return (PHI**D(n) - (D(1)-PHI)**D(n))/ D(5).sqrt()


# ------------------------------------

if __name__ == "__main__":
  # print("Recursion limit:", sys.getrecursionlimit())
  # sys.setrecursionlimit(10**6)
  # sys.set_int_max_str_digits(0)  
      # for printing the result; new in v 3.11

  n = int(input("n=? "))
  print("Recursive:", fibRec(n))
  print("Iterative:", fibIter(n))

'''
  print()
  fn = input("fn? ")
  print( eval(fn)(n))
'''