Came across some pattern similar to this for a leetcode problem. Basically, both functions sums a list a recursively using a nonlocal value. The unassigned value only updates res
once it seems.
def assigned_sum(l: list[int]):
res = 0
def recurse(i: int):
nonlocal res
if i >= len(l):
return 0
assigned = recurse(i+1)
res += assigned
return l[i]
recurse(-1)
return res
def rvalue_sum(l: list[int]):
res = 0
def recurse(i: int):
nonlocal res
if i >= len(l):
return 0
res += recurse(i+1)
return l[i]
recurse(-1)
return res
test = [1,2,3,4,5]
f"expected={sum(test)}, lvalue={assigned_sum(test)}, rvalue={rvalue_sum(test)}"
When thrown into colab, I get 'expected=15, lvalue=15, rvalue=1'
The difference can be seen more clearly between these two variants:
(a):
res = res + recurse(i+1)
and (b):
res = recurse(i+1) + res
For your test run, (a) will return 1, while (b) will return the intended 15.
The difference is caused by the moment when the value of res
is taken: before the recursive call or after.
If it is taken before the recursive call, it will always be 0. This is because the assignment to res
only happens when unwinding out of recursion, not when entering it. So by consequence, all the reading of res
that happens at each recursion level, happens before any assignment to res
. Then when all the assignments happen to res
, they each overwrite the earlier results: 0 + 5, then 0 + 4, then 0 + 3, ... until 0 + 1 which is the final value that is assigned to res
.
In the correct version, the value of res
is read when unwinding out of recursion, so that means we read the value of res
after it has been updated by the recursive call, and so we assign to res: 1 + 0, 2 + 1, 3 + 3, 4 + 6, and finally 5 + 10.