

"""simple docstring"""




def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
					"""simple docstring"""
					if not isinstance(lowercase__    ,							lowercase__   ):
										raise TypeError("recursive_lucas_number accepts only integer arguments."   )
					if n_th_number == 0:
										return 2
					if n_th_number == 1:
										return 1

					return recursive_lucas_number(n_th_number - 1   ) + recursive_lucas_number(
					    n_th_number - 2   )
def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
					"""simple docstring"""
					if not isinstance(lowercase__    ,							lowercase__   ):
										raise TypeError("dynamic_lucas_number accepts only integer arguments."   )
					A    ,					A    =      2, 1
					for _ in range(lowercase__   ):
										A    ,					A    =      b, a + b
					return a


if __name__ == "__main__":
	from doctest import testmod

	testmod()
	__A  :					Optional[int]												=	int(input('Enter the number of terms in lucas series:\n').strip())
	print('Using recursive function to calculate lucas series:')
	print(' '.join(str(recursive_lucas_number(i)) for i in range(n)))
	print('\nUsing dynamic function to calculate lucas series:')
	print(' '.join(str(dynamic_lucas_number(i)) for i in range(n)))








"""simple docstring"""




import functools
from math import sqrt
from time import time
def      __SCREAMING_SNAKE_CASE		(		lowercase__    ,							*lowercase__    ,							**lowercase__   ):
					"""simple docstring"""
					A    =      time()
					A    =      func(*lowercase__    ,							**lowercase__   )
					A    =      time()
					if int(end - start   ) > 0:
										print(F"""{func.__name__} runtime: {(end - start):0.4f} s"""   )
					else:
										print(F"""{func.__name__} runtime: {(end - start) * 1_000:0.4f} ms"""   )
					return output
def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
					"""simple docstring"""
					if n < 0:
										raise Exception("n is negative"   )
					if n == 0:
										return [0]
					A    =      [0, 1]
					for _ in range(n - 1   ):
										fib.append(fib[-1] + fib[-2]   )
					return fib
def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
					"""simple docstring"""

					def fib_recursive_term(lowercase__   ) -> int:
										if i < 0:
															raise Exception("n is negative"   )
										if i < 2:
															return i
										return fib_recursive_term(i - 1   ) + fib_recursive_term(i - 2   )

					if n < 0:
										raise Exception("n is negative"   )
					return [fib_recursive_term(lowercase__   ) for i in range(n + 1   )]
def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
					"""simple docstring"""

					@functools.cache
					def fib_recursive_term(lowercase__   ) -> int:
										if i < 0:
															raise Exception("n is negative"   )
										if i < 2:
															return i
										return fib_recursive_term(i - 1   ) + fib_recursive_term(i - 2   )

					if n < 0:
										raise Exception("n is negative"   )
					return [fib_recursive_term(lowercase__   ) for i in range(n + 1   )]
def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
					"""simple docstring"""
					if n < 0:
										raise Exception("n is negative"   )
					# Cache must be outside recursuive function
					# other it will reset every time it calls itself.
					A    =      {0: 0, 1: 1, 2: 1}  # Prefilled cache

					def rec_fn_memoized(lowercase__   ) -> int:
										if num in cache:
															return cache[num]

										A    =      rec_fn_memoized(num - 1   ) + rec_fn_memoized(num - 2   )
										A    =      value
										return value

					return [rec_fn_memoized(lowercase__   ) for i in range(n + 1   )]
def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
					"""simple docstring"""
					if n < 0:
										raise Exception("n is negative"   )
					if n >= 1_475:
										raise Exception("n is too large"   )
					A    =      sqrt(5   )
					A    =      (1 + sqrt_a) / 2
					return [round(phi**i / sqrt_a   ) for i in range(n + 1   )]


if __name__ == "__main__":
	__A  :					Optional[Any]												=	30
	time_func(fib_iterative, num)
	time_func(fib_recursive, num)  # Around 3s runtime
	time_func(fib_recursive_cached, num)  # Around 0ms runtime
	time_func(fib_memoization, num)
	time_func(fib_binet, num)





