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, Jul 22 '16 at 11:24
@Rawing Adding a while loop would not make this function recursive. — Jokab, Jul 22 '16 at 11:31

Jokab · Accepted Answer · 2016-07-22T11:29:31.080

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 '16 at 11:29

answered Jul 22 '16 at 11:24

Jokab

2,939
1
15
26

thanks a lot but why it prints the L in the end: >>> [95754754745L] >>> – Lucia Jul 23 '16 at 10:44
@Lucia See this answer http://stackoverflow.com/questions/11764713/why-do-integers-in-database-row-tuple-have-an-l-suffix – Jokab Jul 24 '16 at 21:04

Sreyantha Chary · Answer 2 · 2016-07-22T11:49:10.203

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)

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. — Jokab, Jul 22 '16 at 11:48
Yep. Checked it and upvoted for the same :) Edited my answer to take care of it. — Sreyantha Chary, Jul 22 '16 at 11:49

score 2 · Answer 3 · answered Jul 22 '16 at 11:33

2

Why are you not simply using max()?

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

95754754745L

answered Jul 22 '16 at 11:33

Frank

21
1

3

Perhaps OP wanted to practice recursion. – Jokab Jul 22 '16 at 11:34

Finding the maximum element with a recursive function

3 Answers3

Linked