Finding the maximum element with a recursive function

Question

I wrote a function that tries to find out what has the maximum value in a list:

def maxElement(L):
    length=len(L)
    if L[length-1]>L[length-2]:
        del L[length-2]
        print L
    elif L[length-1]<L[length-2]:
        del L[length-1]
    return L

print maxElement([1,2,95754754745,3,1,8,444,2,42425])

My output is wrong:

>>> 
[1, 2, 95754754745L, 3, 1, 8, 444, 42425]
[1, 2, 95754754745L, 3, 1, 8, 444, 42425]
>>>

It doesn't even delete for me what I've ask for. What did I do wrong? I can't get it!

the function you wrote is not recursive. For a function to be recursive it has to call itself, that is within the def a_function() block have a a_function() call. As you probably know and simply because it is not stated so far, you can simply use max() and pass your list L to it like max_item = max(L). I assume you already know that though. — Ma0
– Ma0, Commented Jul 22, 2016 at 11:24
@Rawing Adding a while loop would not make this function recursive. — Jokab
– Jokab, Commented Jul 22, 2016 at 11:31

Jokab · Accepted Answer · 2016-07-22 11:29:31Z

6

You are not calling your function again, which makes recursion impossible. Furthermore you have no base case which would stop recursion, which in this case would be:

if length == 1:
  return L

Here is the fixed code:

def maxElement(L):
    length=len(L)
    if length == 1:
        return L
    elif L[length-1]>=L[length-2]:
        del L[length-2]
    elif L[length-1]<=L[length-2]:
        del L[length-1] 
    return maxElement(L)    

print maxElement([1,2,95754754745,3,1,8,444,2,42425])

This outputs:

python recursive.py
 > [95754754745L]

I also added <= and >= on the conditionals to avoid infinite recursion if there are two elements that share the maximum value.

edited Jul 22, 2016 at 11:29

answered Jul 22, 2016 at 11:24

Jokab

2,9361 gold badge17 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Lucia Over a year ago

thanks a lot but why it prints the L in the end: >>> [95754754745L] >>>

Jokab Over a year ago

@Lucia See this answer stackoverflow.com/questions/11764713/…

Sreyantha Chary · Accepted Answer · 2016-07-22 11:49:10Z

6

It did exactly what you asked it to do.

Your function is not recursive as you forgot calling it again towards the end.

Something like this is what you are looking for:

def maxElement(L):
    length=len(L)
    if L[length-1]>L[length-2]:
        del L[length-2]
        print L
    elif L[length-1]<L[length-2]:
        del L[length-1]
    if len(L) == 1:
        return L
    return maxElement(L)

print maxElement([1,2,95754754745,3,1,8,444,2,42425])

This would return:

[1, 2, 95754754745L, 3, 1, 8, 444, 42425]
[1, 2, 95754754745L, 3, 1, 8, 42425]
[1, 2, 95754754745L, 3, 1, 42425]
[1, 2, 95754754745L, 3, 42425]
[1, 2, 95754754745L, 42425]
[1, 95754754745L]
[95754754745L]
[95754754745L]

I would make it a bit more better as follows:

def maxElement(L):
    length=len(L)

    if length == 1:
        # Have this condition on the top because you are using length - 2 later
        # Just return the only element

        return L

    if L[length-1] > L[length-2]:
        # If the last element is greater than the last but one, delete the last but one
        del L[length - 2]

    else:
        # Simple else would suffice because you are just checking for the opposite
        # Also this condition saves you from:
        #       infinite looping when the last two elements are equal
        del L[length - 1]

    print L

    # Time to call it recursively.
    # But if you just don't want to unnecessarily increase the recursion
    # tree depth, check for length and return it

    if length == 1:
        return L
    return maxElement(L)

edited Jul 22, 2016 at 11:49

answered Jul 22, 2016 at 11:24

Sreyantha Chary

6564 silver badges13 bronze badges

2 Comments

Jokab Over a year ago

While this function produces the correct value for the input values provided in the question, it will cause infinite recursion if the max value is found in two or more indexes. See my answer.

Sreyantha Chary Over a year ago

Yep. Checked it and upvoted for the same :) Edited my answer to take care of it.

Frank · Accepted Answer · 2016-07-22 11:33:31Z

2

Why are you not simply using max()?

max([1,2,95754754745,3,1,8,444,2,42425])

95754754745L

answered Jul 22, 2016 at 11:33

Frank

211 bronze badge

1 Comment

Jokab Over a year ago

Perhaps OP wanted to practice recursion.

Collectives™ on Stack Overflow

Finding the maximum element with a recursive function

3 Answers 3

2 Comments

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related