0

I'm trying to find the maximum element in a list using recursion. the input needs to be the actual list, the left index, and the right index.

I have written a function and can't understand why it won't work. I drew the recursion tree, ran examples of lists in my head, and it makes sense , that's why it's even harder to find a solution now ! (it's fighting myself basically).

I know it's ugly, but try to ignore that. my idea is to split the list in half at each recursive call (it's required), and while the left index will remain 0, the right will be the length of the new halved list, minus 1.

the first call to the function will be from the tail function.

thanks for any help, and I hope I'm not missing something really stupid, or even worse- not even close ! by the way- didn't use slicing to cut list because I'm not allowed. 

def max22(L,left,right):
    if len(L)==1:
        return L[0]
    a = max22([L[i] for i in range(left, (left+right)//2)], 0 , len([L[i] for i in range(left, (left+right)//2)])-1)
    b = max22([L[i] for i in range(((left+right)//2)+1, right)], 0 ,len([L[i] for i in range(left, (left+right)//2)])-1)
    return max(a,b)



def max_list22(L):
    return max22(L,0,len(L)-1)

input example - for max_list22([1,20,3]) the output will be 20.

Improve this question
5
  • Could you please add an example of a specific input list and the unexpected result / error message you get? Commented Dec 29, 2014 at 13:52
  • Why not L[left:(left+right)//2] instead of [L[i] for i in range(left, (left+right)//2)]? Too readable? Commented Dec 29, 2014 at 13:52
  • 1
    wasn't this your homework assigned ? Commented Dec 29, 2014 at 13:52
  • anmol, it is, but I tried many times and I'm asking for help. I'm a student, everything I do is homework ): Commented Dec 29, 2014 at 13:55
  • and Rawing, I can't use slicing, I know it's ugly looking, just searching to understand what's wrong with my code Commented Dec 29, 2014 at 13:56

3 Answers 3

Reset to default
5

First off, for the sake of clarity I suggest assigning your list comprehensions to variables so you don't have to write each one twice. This should make the code easier to debug. You can also do the same for the (left+right)//2 value.

def max22(L,left,right):
    if len(L)==1:
        return L[0]
    mid = (left+right)//2
    left_L = [L[i] for i in range(left, mid)]
    right_L = [L[i] for i in range(mid+1, right)]
    a = max22(left_L,  0 , len(left_L)-1)
    b = max22(right_L, 0 , len(left_L)-1)
    return max(a,b)

def max_list22(L):
    return max22(L,0,len(L)-1)

print max_list22([4,8,15,16,23,42])

I see four problems with this code.

  1. On your b = line, the second argument is using len(left_L) instead of len(right_L).
  2. You're missing an element between left_L and right_L. You should not be adding one to mid in the right_L list comprehension.
  3. You're missing the last element of the list. You should be going up to right+1 in right_L, not just right.
  4. Your mid value is off by one in the case of even sized lists. Ex. [1,2,3,4] should split into [1,2] and [3,4], but with your mid value you're getting [1] and [2,3,4]. (assuming you've already fixed the missing element problems in the previous bullet points).

Fixing these problems looks like:

def max22(L,left,right):
    if len(L)==1:
        return L[0]
    mid = (left+right+1)//2
    left_L = [L[i] for i in range(left, mid)]
    right_L = [L[i] for i in range(mid, right+1)]
    a = max22(left_L,  0 , len(left_L)-1)
    b = max22(right_L, 0 , len(right_L)-1)
    return max(a,b)

def max_list22(L):
    return max22(L,0,len(L)-1)

print max_list22([4,8,15,16,23,42])

And if you insist on not using temporary variables, it looks like:

def max22(L,left,right):
    if len(L)==1:
        return L[0]
    a = max22([L[i] for i in range(left, (left+right+1)//2)],  0 , len([L[i] for i in range(left, (left+right+1)//2)])-1)
    b = max22([L[i] for i in range((left+right+1)//2, right+1)], 0 , len([L[i] for i in range((left+right+1)//2, right+1)])-1)
    return max(a,b)

def max_list22(L):
    return max22(L,0,len(L)-1)

print max_list22([4,8,15,16,23,42])

Bonus style tip: you don't necessarily need three arguments for max22, since left is always zero and right is always the length of the list minus one.

def max22(L):
    if len(L)==1:
        return L[0]
    mid = (len(L))//2
    left_L = [L[i] for i in range(0, mid)]
    right_L = [L[i] for i in range(mid, len(L))]
    a = max22(left_L)
    b = max22(right_L)
    return max(a,b)

print max22([4,8,15,16,23,42])
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

thank you ! haha I don't insist on a fugly code (: great explanation, I'm so greatful
4

The problem is that you aren't handling empty lists at all. max_list22([]) recurses infinitely, and [L[i] for i in range(((left+right)//2)+1, right)] eventually produces an empty list.

Improve this answer

1 Comment

thank you, that really helps my understanding of things.
4

Your problem is that you don't handle uneven splits. Lists could become empty using your code, but you can also stop on sizes 1 and 2 instead of 0 and 1 whichi s more natural (because you return a max, zero size lists don't have a max).

def max22(L,left,right):

    if left == right:
        # handle size 1
        return L[left]

    if left + 1 == right:
        # handle size 2
        return max(L[left], L[right])

    # split the lists (could be uneven lists!)
    split_index = (left + right) / 2
    # solve two easier problems
    return max (max22(L, left, split_index), max22(L, split_index, right))

print max22([1,20, 3], 0, 2)

Notes:

Lose the list comprehension, you don't have to create new lists since you have indices within the list.

When dealing with recursion, you have to think of:

1 - the stop condition(s), in this case there are two because list splits can be uneven, making the recursion stop at uneven conditions.

2 - the easier problem step . Assuming I can solve an easier problem, how can I solve this problem? This is usually what's in the end of the recursive function. In this case a call to the same function on two smaller (index-wise) lists. Recursion looks a lot like proof by induction if you're familiar with it.

Python prefers things to be done explicitly. While Python has some functional features it's best to let readers of the code know what you're up to ratehr than having a big one-liner that makes people scratch their head.

Good luck!

Improve this answer

3 Comments

toda ! you really helped my and I'll make sure to remember your advice when dealing with recursion again.
@NiliSabbah Ein baaya :)
@NiliSabbah if you fuond an answer that solves your problems you should accept it :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.