0

So a have two functions that make recursive calls, first call modifies list l1 which is then passed to the second call. In f1 second recursive call receives modified list [1,1]:

b 2 []
b 1 []
a 1 [1, 1]
b 1 [1, 1]
a 1 [1, 1, 1, 1]
a 2 [1, 1, 1, 1, 1, 1]

but in f2 second call receives unmodified empty list:

b 2 []
b 1 []
a 1 [1, 1]
b 1 []
a 1 [1, 1]
a 2 [1, 1, 1, 1]

why? Aren't f2(f1) just called consecutively in both cases?

def f1(l1=[],num = 2):
    if num == 0: return[1]
    print('b',num,l1)
    l1 = [*l1, *f1(l1, num-1)]
    l1 = [*l1, *f1(l1, num -1)]
    print('a',num,l1)
    return l1

def f2(l1=[],num = 2):
    if num == 0: return[1]
    print('b',num,l1)
    l1 = [*l1, *f2(l1, num-1),*f2(l1, num -1)]
    print('a',num,l1)
    return l1

if list comprehension is a problem (you can't modify list within it), why here it is modified:

def f3(l1):
    print(l1)
    l1 +=[1]
    return l1
l1 = []
l1 = [*l1, *f3(l1), *f3(l1)]

print(l1)

[]
[1]
[1, 1, 1]
Аркадий Момосов
  • 3
  • 2
  • Not sure what you're trying to achieve. The functions f1 and f2 are functionally different. Thus, calling f1 and f2 consecutively with the same input values is likely to produce different results –  Nov 06 '21 at 16:41
  • I just want to understand why it works that way. And in the f3 example a modified list is past within list comprehension, although it looks pretty much like f2. – Аркадий Момосов Nov 06 '21 at 18:46
  • Not relevant here (you don't appear to be calling either function without a first argument), but don't use a list as a default parameter value. See https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument. – chepner Nov 06 '21 at 19:51

2 Answers2

0

In f1, the second call receives the modified content of l1 but in f2 it receives the original (unmodified) content because the list is not modified while the comprehension is being executed but only at the end once the resulting list is finished building.

Alain T.
  • 40,517
  • 4
  • 31
  • 51
0

The function f1 creates a whole new list, then uses that new list in a second call to f1. The function f2 only ever passes the original list to its calls to f2.

To expand, in f1, the logic looks like this:

def f1(l1=[],num = 2):
    if num == 0: return[1]
    print('b',num,l1)
    
    # Here, *f1(l1, num-1) uses the original value of
    # l1, then expands it.
    # *l1 expands the original value of l1.
    # The [...] creates a completely new list,
    # and finally, l1 = ... assigns that completely new
    # list to the value of l1.
    l1 = [*l1, *f1(l1, num-1)]
    
    # Here, the l1 in *f1(l1, num -1) refers to the
    # result of the assignment above, l1 = ...
    #
    # *l1 also refers to the result of the assignment
    # above.
    #
    # Again, [...] creates a completely new list,
    # then l1 = ... assigns that new list to the name l1.
    l1 = [*l1, *f1(l1, num -1)]
    print('a',num,l1)
    return l1
    
# This function is identical
def f1(first_list = [], num = 2):
    if num == 0: return [1]
    print('b', num, first_list)
    
    second_list = [*first_list, *f1(first_list, num - 1)]
    
    third_list = [*second_list, *f1(second_list, num - 1)]
    print('a', num, third_list)
    return third_list

In f2, the logic looks like this:

def f2(l1=[],num = 2):
    if num == 0: return[1]
    print('b',num,l1)
    
    # Here, both *f2(l1, num-1) calls refer to the original l1
    # passed in the argument list.
    #
    # *l1 refers to the original l1 passed in the argument list,
    # too.
    #
    # The [...] creates a whole new list,
    # then l1 = ... assigns that new list to the name l1.
    l1 = [*l1, *f2(l1, num-1),*f2(l1, num -1)]
    print('a',num,l1)
    return l1

# This function is identical
def f2(first_list = [], num = 2):
    if num == 0: return [1]
    print('b', num, first_list)
    
    second_list = [*first_list, *f2(first_list, n - 1), *f2(first_list, n - 1)]
    print('a', num, second_list)
    return second_list

The difference between f2 and f3 is, in f2, you are not calling any code which modifies the list: you are creating a whole new list, then re-assigning the name l1 to refer to the new list. In f3, you are not creating a whole new list, you are just modifying the list in-place.

Lets take a simplified example that demonstrates this:

>>> def set_value(first_list):
...     first_list = [ 2 ]
... 
>>> mylist = [3, 4]
>>> set_value(mylist)
>>> mylist
[3, 4]
>>> 
>>> def set_value(first_list):
...     first_list.clear()
...     first_list.append(2)
... 
>>> mylist
[3, 4]
>>> set_value(mylist)
>>> mylist
[2]
>>>

The += operator modifies the list on the left, while the = doesn't modify the list at all. l1 += ... adds ... to the end of the the list l1 refers to. l1 = ... just changes what the name l1 refers to: you could make it refer to an integer, or a dictionary, or an object, or anything else.

Marcus Harrison
  • 819
  • 6
  • 19
  • 1
    Alright i think i get it now. Rebinding name l1 doesn't change the real object it refers to (unlike += operator). But why doesn't f2 check what l1 refers to during it's second call in `l1 = [*l1, *f2(l1, num-1),*f2(l1, num -1)]` ? As if the unmodified list had been pasted to the second f2 before rebinding of name l1 took place (in a first f2 call). If that makes sense.... – Аркадий Момосов Nov 06 '21 at 20:59
  • It does: the problem is, what `l1` refers to is the _very last_ thing that's changed. First, one of the f2 calls is called, with l1 unchanged; then, another f2 is called, with l1 still unchanged; then, `*l1` unpacks the (still unchanged) l1, the results of the two f2 calls are unpacked, and a new list is created with [...] containing the results. Only then, finally, is the list that l1 refers to set to this brand-new list. – Marcus Harrison Nov 06 '21 at 21:04
  • In order to assign `l1` to the brand new list, the list first has to be created; in order to create the list, first the results of `*l1`, `*f2(...)` and `*f2(...)` need to be found. – Marcus Harrison Nov 06 '21 at 21:06
  • I meant reassignment of `l1` that takes place down the call stack, during first `f2` call (when it hits the `f2(l1,0)` case), so all new `l1` references down the call stack does not affect original `l1 = []` reference, they are just new lists "local to those down the stack calls"? – Аркадий Момосов Nov 06 '21 at 21:30
  • That's exactly right. If you modified the `l1` in-place, with `+=` or `.append` or similar, in those sub-calls, you would see that in the top call. However, each of those sub-calls just re-assigns the name `l1` _inside that call_ to a new list created _inside that call_. I'd advise against doing modifications like that in a recursive call though, since it makes the logic harder to reason about. Doing some processing, then returning a new value, then using that new value in the top call is much easier to understand. – Marcus Harrison Nov 06 '21 at 21:36