0

I was trying to solve a problem consisting in finding the max value of a list with several level of depth. I tried several ideas but no luck. So I found this online. I actually had this idea myself but I discarded it without testing it for the reason I'll mention right after.

def get_max(my_list):
    m = None
    for item in my_list:
        if isinstance(item, (list, tuple)):
            item = get_max(item)
        if not m or m < item:
            m = item
    return m

Sample run:

>>> get_max(((10, (1,2), [[1],[9]])))    
>>> 10

So I did discard this idea because I thought that if the value of m is reset to None at each recursive steps, it's not going to find the max value I need. I ran it in Python Tutor but I still don't understand how m would remember the value 10 as it as been reset to None several times.

Could somebody explain to me please?

Does every recursive step create a new frame somehow?

Yannick
  • 1,550
  • 4
  • 18
  • 27
  • The `m = None` at the beginning, then `if not m or m < item:` trick just sets the value of `m` to the first value of `item`. That is all. – juanpa.arrivillaga Jul 31 '17 at 23:08
  • 5
    "Does every recursive step create a new frame somehow?" Yes, somehow. – kindall Jul 31 '17 at 23:08
  • *as it as been reset to None several times.* Each call to `get_max` does not "reset" m, because each call has its own stack frame. Also I'm pretty sure this exact problem has shown up at least a dozen times in the last few days or so, must be a homework problem? – rlbond Jul 31 '17 at 23:09
  • Recursive function calls are the same as other function calls. They create frames in the same way and for the same reasons. There is nothing about recursion that is special or magic. – Alex Hall Jul 31 '17 at 23:09
  • Also, note, as written, this function only recurses into *lists*, not `tuple`s, as you have a mix of both here. You are clearly using Python 2, or else this would have thrown an error when you tried to compare a `tuple` to an `int` – juanpa.arrivillaga Jul 31 '17 at 23:12
  • Yes, thats homework, sorry if the question was posted too much. I handle simple recursive function so far but I practice and hopefully one day its going to be easier, thanks. – Yannick Jul 31 '17 at 23:15
  • Oh yes I had to adapt it a little bit to handle tuples, I'm going to edit thanks @juanpa.arrivillaga – Yannick Jul 31 '17 at 23:16
  • @Yannick instead of `or` you can just use `isinstance(item, (list, tuple))` – juanpa.arrivillaga Jul 31 '17 at 23:29
  • much better, thx @juanpa.arrivillaga – Yannick Jul 31 '17 at 23:31
  • It would be better to do `if m is None` rather than `if not m`, in case you need to handle `m==0`. – PM 2Ring Jul 31 '17 at 23:48

3 Answers3

2

Does every recursive step create a new frame somehow?

Yes, each recursive call to max creates a new frame. There are actual ramifications to this (as in: what happens if the recursion depth is very large or possibly infinite? By default, CPython sets the maximum recursion depth to 1000. See also: What is the maximum recursion depth in Python, and how to increase it?)

m is a local variable. So the m in the first parent call of max is not the same m that is assigned in a child call of max. The "remembering" is because the child m is returned as item to the parent.

cowbert
  • 3,212
  • 2
  • 25
  • 34
  • Thank you very much for the explanation. That makes sense, a function call creates a frame. I was just confused by the fact that all these frame have the 'same name' so to speak.. so to me it had to be the same frame... – Yannick Jul 31 '17 at 23:20
1

As others have mentioned your recursion does the right thing because each call of get_max gets its own local variables, my_list, m, and item.

FWIW, here's a minor variation on your code. It should be a little more efficient because it uses the built-in max rather than computing the maximum with a Python loop (although we're still looping in that generator expression). It also eliminates the need to do m = None, and hence the need to test if m is initialised every time we update it.

def get_max(obj):
    is_seq = isinstance(obj, (list, tuple)) 
    return max(get_max(u) for u in obj) if is_seq else obj

data = (10, (1, 2), [[1], [9], [4, 7]])
print(get_max(data))

output

10

We can also write it using map instead of a generator expression in the max call.

def get_max(obj):
    is_seq = isinstance(obj, (list, tuple)) 
    return max(map(get_max, obj)) if is_seq else obj
PM 2Ring
  • 54,345
  • 6
  • 82
  • 182
0

The recursive call appears to be for lists within the current list. So, the base case for this function is a list that only contains non-list items. In other words, there is only a new function call, and thus an instance of the m variable, when a new list is found.

Each call to get_max() will have its own variable m which will hold the max value at that level and below.

sethro
  • 2,127
  • 1
  • 14
  • 30