CODEWITHSUNDEEP
pythonfunctionrecursion
Yannick
Yannick

Reputation: 1600

Does each call of a recursive function create a new frame?

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?

Upvotes: 0

Views: 453

Answers (3)

PM 2Ring
PM 2Ring

Reputation: 55479

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

Upvotes: 1

sethro
sethro

Reputation: 2127

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.

Upvotes: 0

cowbert
cowbert

Reputation: 3442

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.

Upvotes: 2

Related Questions