Skip to content

Instantly share code, notes, and snippets.

@yvan-sraka
Last active October 14, 2023 17:00
Show Gist options
  • Save yvan-sraka/52384523a92bb0910d770f0fdde59bbd to your computer and use it in GitHub Desktop.
Save yvan-sraka/52384523a92bb0910d770f0fdde59bbd to your computer and use it in GitHub Desktop.
Max function implementation explained in Python
# 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))
@weiqiang333
Copy link

weiqiang333 commented Aug 25, 2019

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]

@Vir-al
Copy link

Vir-al commented Mar 20, 2021

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 

@yvan-sraka
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment