
"""simple docstring"""

def 		UpperCAmelCase (		a_      ):





		'''simple docstring'''


		if upper_limit < 0:
				raise ValueError('Limit for the Catalan sequence must be ≥ 0'      )

		lowerCamelCase					:      Tuple          =   [0] * (upper_limit + 1)

		# Base case: C(0) = C(1) = 1
		lowerCamelCase					:      str          =   1
		if upper_limit > 0:
				lowerCamelCase					:      Optional[int]          =   1

		# Recurrence relation: C(i) = sum(C(j).C(i-j-1)), from j = 0 to i
		for i in range(2,						upper_limit + 1      ):
				for j in range(a_      ):
						catalan_list[i] += catalan_list[j] * catalan_list[i - j - 1]

		return catalan_list


if __name__ == "__main__":
					print('\n********* Catalan Numbers Using Dynamic Programming ************\n')
					print('\n*** Enter -1 at any time to quit ***')
					print('\nEnter the upper limit (≥ 0) for the Catalan number sequence: ', end='')
					try:
										while True:
															_A						=			int(input().strip())
															if N < 0:
																				print('\n********* Goodbye!! ************')
																				break
															else:
																				print(F"""The Catalan numbers from 0 through {N} are:""")
																				print(catalan_numbers(N))
																				print('Try another upper limit for the sequence: ', end='')
					except (NameError, ValueError):
										print('\n********* Invalid input, goodbye! ************\n')

					import doctest

					doctest.testmod()








"""simple docstring"""

def 		UpperCAmelCase (		a_,						a_      ):





		'''simple docstring'''


		while b:
				lowerCamelCase     ,   lowerCamelCase					:      Tuple          =   b, a % b
		return a
def 		UpperCAmelCase (		a_,						a_      ):





		'''simple docstring'''


		return a if b == 0 else euclidean_gcd_recursive(a_,						a % b      )
def 		UpperCAmelCase (		):





		'''simple docstring'''


		print(F"""euclidean_gcd(3, 5) = {euclidean_gcd(3,						5      )}"""      )
		print(F"""euclidean_gcd(5, 3) = {euclidean_gcd(5,						3      )}"""      )
		print(F"""euclidean_gcd(1, 3) = {euclidean_gcd(1,						3      )}"""      )
		print(F"""euclidean_gcd(3, 6) = {euclidean_gcd(3,						6      )}"""      )
		print(F"""euclidean_gcd(6, 3) = {euclidean_gcd(6,						3      )}"""      )

		print(F"""euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3,						5      )}"""      )
		print(F"""euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5,						3      )}"""      )
		print(F"""euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1,						3      )}"""      )
		print(F"""euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3,						6      )}"""      )
		print(F"""euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6,						3      )}"""      )


if __name__ == "__main__":
					main()






