Unexpected Value of None for Finding Maximum in a List - Python 3 Recursion

Question

I am trying to write a simple recursive function to find the maximum in a list without using any built in functions, with the exceptions being 'print' and 'len'. I made a simple linear search using recursion that compares each member of the list to the current Max.

x=[1,2,3]
Max=x[-1]

def Max_list(Max, x, c=2):

    if len(x)==1:
        return Max

    else:

        if c==(len(x)+1):
            print('hi')
            return Max

        elif x[len(x)-c]>Max:
            Max=x[len(x)-c]
            c+=1
            Max_list(Max, x, c)

        elif x[len(x)-c]<=Max:
            c+=1
            Max_list(Max, x, c)

print(Max_list(Max, x))

What confuses me is that my program prints 'hi' (this was a verification that my if condition was satisfied), but returns None. I could have made it attempt to return anything, and it would still return 'None'. I am wondering how to fix it obviously, but if anyone could give me an explanation as to why my code will always return None in its current state, that would be wonderful.

Making the recursive `Max_list(Max, x, c)` call doesn't also automatically return whatever the recursive call returns. You need to explicitly `return` it. — user2357112, Aug 02 '17 at 16:13
This confuses me a lot. This fixed my problem, but I don't understand when to return and when to just call. As you can see in the problem that I asked yesterday, I wasn't supposed to explicitly return the function — DrJessop, Aug 02 '17 at 16:15
This is unrelated to your question, and I'm trying to give you a satisfactory answer, but in the meantime: on the second line, you can grab the last element in the list with `x[-1]` — Patrick Gallagher, Aug 02 '17 at 16:19

score 2 · Accepted Answer · answered Aug 02 '17 at 16:29

2

As one of the users pointed out in the comments, you need to add a return statement to the two calls to Max_list(Max, x, c). Why is this the case?

In Python, if you have call a function that has no return statement, the default return value is None. If we look at your recursion, what it's actually doing is this:

    Initial Call:
    Max_list(3, x, 3)
              vvvvv
            Max_list(3, x, 4)
                      vvvvv
                     print('hi')
                     return 3 
            return None
    return None

Upon adding those return statements, we get something in the vein of:

    Initial Call:
    Max_list(3, x, 3)
               vvvvvv
            Max_list(3, x, 4)
                      vvvvv
                     print('hi')
                     return 3 
            return the value of the above (3)
    return the value of the above (3)

answered Aug 02 '17 at 16:29

Patrick Gallagher

193
2
13

Yesterday, I asked a question that used recursion in which I returned the function and it turns out that I wasn't supposed to do that for explanations posted in the forums. In the case of that question, why did my function return an output that wasn't None? – DrJessop Aug 02 '17 at 16:35
I took a glance, but if I found the correct question, I think you were using a for loop, and returning in the for loop would break the loop and thus the recursion. That was a more specific case and is not a generality of recursion. If you'd like a detailed runthrough, I can give you one. – Patrick Gallagher Aug 02 '17 at 16:37
1

That makes so much more sense! Thank you! – DrJessop Aug 02 '17 at 16:39

score 1 · Answer 2 · answered Aug 02 '17 at 16:26

1

As user2357112 said, you must explicity use return. Also Patrick Gallagher does make a good point about using x[-1] to retrieve the last element in the list.

x=[1,2,3]
Max=x[-1]

def Max_list(Max, x, c=2):

    if len(x)==1:
        return Max

    else:

        if c==(len(x)+1):
            return Max

        elif x[len(x)-c]>Max:
           Max=x[len(x)-c]
            c+=1
            return Max_list(Max, x, c)

        elif x[len(x)-c]<=Max:
            c+=1
            return Max_list(Max, x, c)

print(Max_list(Max, x))

answered Aug 02 '17 at 16:26

TheDetective

642
1
6
17

In that case, for me to accept your answer, can you go further with your explanation as to when I should explicitly return vs. call. I've been introduced to the idea of execution stacks, so if you could explain to me what my program is doing WITHOUT the return vs WITH the return, that would be fantastic. – DrJessop Aug 02 '17 at 16:30
Check my answer, I added an explanation with a hopefully non confusing diagram – Patrick Gallagher Aug 02 '17 at 16:31

Unexpected Value of None for Finding Maximum in a List - Python 3 Recursion

2 Answers2