The Little Fix for Big O

Thankfully, there’s an easy way to eliminate all these extra recursive calls. We’ll call max only once within our code, and save the result to a variable:

	def max(array):
	if not array:
	return None

	if len(array) == 1:
	return array[0]

	# Calculate the max of the remainder of the array
	# and store it inside a variable:
	max_of_remainder = max(array[1:])

	# Comparison of first number against this variable:
	if array[0] > max_of_remainder:
	return array[0]
	else:
	return max_of_remainder

By implementing this simple modification, we end up calling max a mere four times. Try it out yourself by adding the print("RECURSION") line and running the code.

The trick here is that we’re making each necessary function call once and saving the result in a variable so that we don’t have to ever call that function again.

The difference in efficiency between our initial function and our ever-so-slightly modified function is stark.