Why does this recursion code work?

Question

def permutation(li,result=[]):
    print(li, result)               # I added this print statement as a diagnostic.
    if li == [] or li == None:      # As coded, I expected each recursive call to
        return                      # reinitialize 'result=[]' because there is no
                                    # second argument being passed in the recursive
    if len(li) == 1:                # call below.
        result.append(li[0])
        print(''.join(result))
        result.pop()
        return

    for i in range(0,len(li)):
        result.append(li[i])
        permutation(li[:i] + li[i+1:])          # I would have thought that the
       #permutation(li[:i] + li[i+1:], result)  # recursive call needed to be this.
        result.pop()        

test=list('123')
permutation(test)

Results:

['1', '2', '3'] []
['2', '3'] ['1']
['3'] ['1', '2']
123
['2'] ['1', '3']
132
['1', '3'] ['2']
['3'] ['2', '1']
213

The key when using default arguments is that the default value is referencing the same list each time not constructing a new one. And since lists are mutable, that list is not the same from call to call. — cmd, Apr 15 '13 at 21:54

score 1 · Answer 1 · edited May 23 '17 at 11:50

because result is a mutable list. to put it simply, if you append items to a list, the item is still there unless the list or the item is garbage-collected. in your code, result points to same list object that is declared as a default argument of permutation function. you do not build a new list for result upon every call of permutation function. Because you push/pop item(s) for every permutation, you might think(and it looks like) your function is 'stateless', but it is not.

Why does this recursion code work?

1 Answers1