Max function implementation explained in Python

max.py

# Input data
list_0 = [1, 3, 6, 7, 8, 9, 10, 2, 3, 4]
list_1 = [12, 56, 3, 78, 34, 56, 2, 10]
list_2 = [123, 567, 234, 890]
list_3 = [5, 7, 8, 9, 3, -2, -4, -2, 5, 6, 8, 11, 2]

# Iterative algorithm
def maximum(L):
    biggest_item = L[0]
    for item in L:
        if item > biggest_item:
            biggest_item = item
    return item

# Recursive algorithm
def rec_max(L):
    if L[1:]:
        recursed_max = rec_max(L[1:])
        if L[0] > recursed_max:
            return L[0]
        else:
            return recursed_max 
    elif not L:
        return
    else:
        return L[0]

# Tests
print("maximum(list_0)", maximum(list_0))
print("maximum(list_1)", maximum(list_1))
print("maximum(list_2)", maximum(list_2))
print("maximum(list_3)", maximum(list_3))

recursive_functions

def max(list):
    if list[1:]:
        if list[0] > max(list[1:]):
            return list[0]
        else:
            return max(list[1:])
    elif not list:
        return
    else:
        return list[0]

Isn't it will be better if we compute the recursive max element only once and operate on that?

The above function is calling the recursion twice for the same operation. At line 27 and at line 30.

if list[0] > rec_max(list[1:]): # Calling here once
  return list[0]
else:
  '''
  Calling here again, which will lead to recurse the function it already computed the value for.
  This will impact the time complexity of the function majorly for large lists.
  '''
  return rec_max(list[1:])

Instead of that, we can write it as below

recursed_max = rec_max(list[1:])
if list[0] > recursed_max:
  return list[0]
else:
  return recursed_max 

@hamzaafridi, @weiqiang333 and @Vir-al thanks for your feedbacks, I updated the gist 🙂