Python: Functions where a variable with the same name of the input is generated

Question

Apologies for any possible confusion about the title. I will try my best to illustrate my question.

Context:

I just finished working on an interesting coding problem on CodeWars where I was asked to write a function to simplify a list of directions.

The input will look like ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

The 'SOUTH' 'NORTH' and 'EAST' 'WEST' that are next to each other shall both be deleted since it makes little sense to go north and then immediately south. And the list shall be simplified until it can't be simplified anymore.

For instance:

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

shall be simplified to

['WEST']

Dummy OP wrote a clunky function that does it. But my question is about a really clever answer posted by someone else.

Code:

def dirReduc(arr):
 dir = " ".join(arr)
 dir2 = dir.replace("NORTH SOUTH",'').replace("SOUTH NORTH",'').replace("EAST WEST",'').replace("WEST EAST",'')
 dir3 = dir2.split()
 return dirReduc(dir3) if len(dir3) < len(arr) else dir3

I played with it and see that it works but just couldn't wrap my head around how.

I see that in the return statement, it shall run again unless the result has the same length as input, which is understandable. But the code uses dirReduc(dir3) which seems wrong to me.

If I run dirReduc(dir3) then my input will be dir3, but then inside the frame of the function, another dir3 is created. So now when the function goes to the final return statement it shall be return dirReduc(dir3) if len(dir3) < len(dir3) else dir3. And since len(dir3) == len(dir3)', it will just returndir3`.

In my understanding, the function will be run twice, max with each input, which is not the truth. So which part of my understanding is wrong?

Sorry for the sheer volume of words, I think after all this is a simple problem. There must be a very fundamental thing that I'm getting wrong.

• juanpa.arrivillaga: dir3 are local variables to each function execution, they are unrelated to each other.
• Bowen Liu: @juanpa.arrivillaga Thanks for the quick response. Would you care to elaborate a little bit please. The dir3 generated inside the function is local variable? Which is unrelated to which? And when the return statement evaluates len(dir3), hasn't it been changed to the local variable already?
• kyrill: this solution fails for ['NORTH', 'WEST', 'SOUTH']
• Bowen Liu: @kyrill because they will only be deleted if they are RIGHT NEXT to each other. Sorry for not making it clear enough.
• chepner: That's boring :)

Answer 1

Local variables in different stack frames are completely unrelated to each other, even if they share the same name. Each recursive call creates a new stack frame, so dir3 in one call is completely different from dir3 in another.

Imagine you had a non-recursive function that only reduced the path by one step:

def dirReducOneStep(arr):
 dir = " ".join(arr)
 dir2 = dir.replace("NORTH SOUTH",'').replace("SOUTH NORTH",'').replace("EAST WEST",'').replace("WEST EAST",'')
 dir3 = dir2.split()
 return dir3
print(dirReducOneStep(dirReducOneStep(dirReducOneStep(path))))

The only difference is that dirReduc calls itself on a reduced path, rather than forcing the caller to decide whether or not to call it again on the previous output.

• kyrill: I would argue that the second problem is in fact less interesting. Its optimal solution runs in Ө(n) time and Ө(log n) auxiliary space. However, the given solution to the original problem requires Ο(n^2) time, albeit only Ө(1) space (assuming tail-call optimization, which à propos is not the case with Python, so it's in fact Ο(n) space). An alternative solution would require Ө(n) time and Ο(n) space (to maintain a stack of counters, one for each N/S or E/W level).
• chepner: Yes, but why would you only want a partially compressed path, instead of the shortest possible path? That's what I meant by "more interesting".
• kyrill: Imagine you are at coordinate (0,0). You need to go 2 units to the east -- to (0,2), but there is an obstacle at (0,1). So you cannot just "compress" N-E-E-S to E-E because you would run into the obstacle. Imagine the input directions describe a walk in a directed graph (en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#walk); what you want to do is make it into a simple path (en.wikipedia.org/wiki/Simple_path).
• chepner: Ok, that's a good point. I was thinking of a fully connected space.
• Bowen Liu: Thanks. I forgot about the basic concept of stack frame. Please lemme know if I'm understanding correctly. After the first iteration, when the function is going to run dirReduc(dir3), this dir3 is established in the first stack frame, and in the run of dirReduc(dir3), the return statement will be dirReduc(dir3(2nd stack frame) if len(dir3(2nd stack frame)) < len(dir3(first stack frame). Did I get it right? Thanks again.

Answer 2

It is a basic concept. Every function has its own stack, or let's say scope.

You can image that a function is a box. Local variables are inside the box. So if there are many functions, then there are many boxes. Every box has its own local variables. That's like:

BoxA
--variable_a
BoxB
--varibale_a

Although these two variables have the same name, they are in different boxes. So they are different varibales at all.

Further, BoxA(Actually functionA) cannot access the variable_a in BoxB, it is outside of its scope, so it is safe even these two variables have the same name.

• Bowen Liu: Gotcha, thanks a lot. I didn't think the concept of stack frame is important when I learned it. Now I know.