CODEWITHSUNDEEP
pythonrecursionmax
DecafOyster208
DecafOyster208

Reputation: 135

finding the max item in a sequence using recursion

im trying to get a function to find the max item in a sequence using recursion but I keep getting an error,like when i try Max(range(100)):

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

Im a programming newbie btw so any help is much 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]

Upvotes: 0

Views: 911

Answers (2)

pjs
pjs

Reputation: 19855

This variant will reduce the stack size by slicing the problem in half at each level of the recursion, and recursively solving for both halves. This allows you to evaluate lists with thousands of elements, where the approach of reducing the problem size by one would cause stack overflows.

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]

Upvotes: 1

Ian
Ian

Reputation: 30813

You seem to forget 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, therefore it cannot be compared with s which is a list. Thus you got your error.

Side note, consider of using ternary 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 definite 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 a lot simpler.

Upvotes: 5

Related Questions