first-time questioner here so do highlight my mistakes.
I was grinding some Leetcode and came across a behavior (not related to the problem) in Python I couldn't quite figure out nor google-out. It's especially difficult because I'm not sure if my lack of understanding is in:
- recursion
- the
=
operator in Python or variable assignment in general - or Python's pass-by-sharing behavior
- or just something else entirely
Here's the simplified code:
class Holder:
def __init__(self, val=0):
self.val = val
class Solution:
def runThis(self):
holder = Holder()
self.diveDeeper(holder, 5)
return
def diveDeeper(self, holder, n):
if n==0:
return 1
# 1) Doesn't result in mutation
holder.val = self.diveDeeper(holder, n-1)
# 2) Also doesn't result in mutation
# holder.val = holder.val self.diveDeeper(holder, n-1)
# 3) !! Results in mutations
# returnVal = self.diveDeeper(holder, n-1)
# holder.val = returnVal
print(holder.val)
return 1
a = Solution()
a.runThis()
So yeah my main source of confusion is how (1) and (3) look semantically identical to me but results in two completely different outcomes:
================ RESTART: Case 1 ===============
1
1
1
1
1
>>>
================ RESTART: Case 3 ===============
1
2
3
4
5
>>>
From (2), it doesn't seem related to the =
operator and for brevity, I haven't included the tens of variations I've tried but none of them have given me any leads so far. Would really appreciate any pointers in the right direction (especially in case I get blindsided in job interviews lmao)
PS: In case this is relevant, I'm using Python 3.8.2
CodePudding user response:
You struggled me a bit but the answer is really simple. Let me rephrase why that happened.
holder.val = holder.val self.diveDeeper(holder, n - 1) # prints 1 1 1 1 1
holder.val = self.diveDeeper(holder, n - 1) holder.val # prints 1 2 3 4 5
I hope you see now what is going on - in case of =
it evaluates to first variant. In every recursion step, holder.val
will be 0 when executing that line. That's why we will assign 5 times holder.val = 0 1
.
With changed order, we first mutate holder.val
and then use it to calculate new one. The passing by reference works as expected.
CodePudding user response:
In Python, if you have expression1() expression2()
, expression1()
is evaluated first.
So 1 and 2 are really equivalent to:
left = holder.val
right = self.diveDeeper(holder, n - 1)
holder.val = left right
Now, holder.val
is only ever modified after the recursive call, but you use the value from before the recursive call, which means that no matter the iteration, left == 0
.
Your solution 3 is equivalent to:
right = self.diveDeeper(holder, n - 1)
left = holder.val
holder.val = left right
So the recursive call is made before left = holder.val
is evaluated, which means left
is now the result of the sum of the previous iteration.
This is why you have to be careful with mutable state, you got to understand the order of operations perfectly.
CodePudding user response:
I thinks it comes from the way you're using recursion.
When you call holder.val = self.diveDeeper(holder, n-1)
the holder you pass to the dive deeper method is the one without updated val.
So you will call n times the diveDeeper function without modifying the holder val, and you will return 1 in the end.
Your example will execute as follow:
- call self.diveDeeper with holder unmodified, n = 5;
- call self.diveDeeper with holder unmodified, n = 4;
- call self.diveDeeper with holder unmodified, n = 3;
- call self.diveDeeper with holder unmodified, n = 2;
- call self.diveDeeper with holder unmodified, n = 1;
- call self.diveDeeper with holder unmodified, n = 0;
- return 1
- print holder.val 5 times which as not been modified, since your last recursion return 1
In (3), after the recursion is done, when you unwrap your call, you will get 1 from the last diveDeeper call, then add it to holder. In the next unwrapping you'll do the same, resulting in incrementing your val from 1, on each recursion.
CodePudding user response:
for case 1.
holder.val = self.diveDeeper(holder, n-1)
here intial value of holder.val
is 0. so effectivly holder.val
should be equal to the value of self.diveDeeper(holder, n-1)
since this function only return 1 and holder.val
remain local variable it will remain 0 (initally) in all funciton call ie
WHEN N=5
holder.vaL = 0 self.diveDeeper(holder, 5)
= 0 (0 self.diveDeeper(holder, 4))
= 0 (0 (0 self.diveDeeper(holder, 3)))
= 0 (0 (0 (0 self.diveDeeper(holder, 2))))
= 0 (0 (0 (0 (0 self.diveDeeper(holder, 1)))))
= 0 (0 (0 (0 (0 1))))
= 1
note in each function call value is not stored anywhere
whereas in case 3
returnVal = self.diveDeeper(holder, n-1)
holder.val = returnVal
here, for each call returnVal
will have value of 1.
ie
n = 5, returnVal = self.diveDeeper(holder, 4)
= self.diveDeeper(holder, 3)
= self.diveDeeper(holder, 2)
= self.diveDeeper(holder, 1)
= self.diveDeeper(holder, 0)
= 1
so we got returnVal = 1
. not comes the `holder.val part
since holder
is an object and during function call this is keep passing in the functional calls, it will remain intact throughout
so for last call when n=0, holder.val = returnVal
make holder.val
= 1.
now when it return 1 , and goes to recursive chain when n=1, holder.val
is updated to 1 and is not 0 anymore so
holder.val = 1 self.diveDeeper(holder, 1)
ie all the reference to holder.val
got update to latest call and is no more 0
ie when n = 0, holder.val = 0
n =1, holder.val = holder.val ( value of holder.val when n= 0, ie 0) 1 (1 is value of self.diveDeeper(holder, 0)
n= 2 holder.val = holder.val ( value of holder.val when n= 1, ie 1) 1 (1 is value of self.diveDeeper(holder, 1)
n= 3 holder.val = holder.val ( value of holder.val when n= 2, ie 2) 1 (1 is value of self.diveDeeper(holder, 2)
n= 4 holder.val = holder.val ( value of holder.val when n= 3, ie 3) 1 (1 is value of self.diveDeeper(holder, 3)
n= 5 holder.val = holder.val ( value of holder.val when n= 4, ie 4) 1 (1 is value of self.diveDeeper(holder, 4)
CodePudding user response:
View bytecode with dis
:
>>> from dis import dis
>>> dis('a.b = c()')
1 0 LOAD_NAME 0 (a)
2 DUP_TOP
4 LOAD_ATTR 1 (b)
6 LOAD_NAME 2 (c)
8 CALL_FUNCTION 0
10 INPLACE_ADD
12 ROT_TWO
14 STORE_ATTR 1 (b)
16 LOAD_CONST 0 (None)
18 RETURN_VALUE
>>> dis('''r = c()
... a.b = r''')
1 0 LOAD_NAME 0 (c)
2 CALL_FUNCTION 0
4 STORE_NAME 1 (r)
2 6 LOAD_NAME 2 (a)
8 DUP_TOP
10 LOAD_ATTR 3 (b)
12 LOAD_NAME 1 (r)
14 INPLACE_ADD
16 ROT_TWO
18 STORE_ATTR 3 (b)
20 LOAD_CONST 0 (None)
22 RETURN_VALUE
An obvious difference is that the former has already loaded the value of a.b
before calling the function, which will be 0 in each recursion. Because the number is an immutable object, the number loaded in advance will not be changed after each addition and storage. The latter is the value of a.b
loaded after calling the function, which causes the value of a.b
to be updated after each recursion.