Finding the maximum element in a sequence using recursion

Question

im trying to get a function to find the maximum element in a sequence using recursion, but I keep getting an error, for example, when I try to max (range (100)):

TypeError: unorderable types: int() > list() 

I am a btw novice programmer, so any help is greatly appreciated.

 def Max(s) if len(s) == 1: return s[0] else: m = Max(s[1:]) if m > s: return m else: return s[0] 

Answer 1

You seem to have forgotten to put the index:

 def Max(s): if len(s) == 1: return s[0] else: m = Max(s[1:]) if m > s[0]: #put index 0 here return m else: return s[0] 

m is a single number, so it cannot be compared with s , which is list . So you got your error.

Side note, consider using the triple operation [true_val if true_cond else false_val] to simplify your notation. Also, you do not need the last else block, since your if clause has a specific return before leaving the block:

 def Max(s): if len(s) == 1: return s[0] m = Max(s[1:]) return m if m > s[0] else s[0] #put index 0 here 

Then your code will become much easier.

Answer 2

This option will reduce the size of the stack, cutting the problem in half at each recursion level and a recursive solution for both halves. This allows you to evaluate lists with thousands of items, where the approach to reducing the size of the problem by one will lead to a stack overflow.

 def Max(lst): l = len(lst) if l > 1: mid = l / 2 m1 = Max(lst[:mid]) # find max of first half of the list m2 = Max(lst[mid:]) # find max of second half of the list # max of the list is the larger of these two values return m1 if m1 > m2 else m2 return lst[0]