recursive calls with list parameters (python)-CodePudding

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]

CodePudding user response：

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.

CodePudding user response：

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.