2019-10-01

Python lists as local variables in recursion

Today I ran into a really interesting problem. Let's use Leetcode's Problem 77 combination as an example. I wanted write a function that prints all possible combinations (no order, unlike permutation).

So here is my function definition and call:
def helper(n, k, start, L):
    # L = list (L)  # make a copy 
    if len(L) == k:# all k elements have been drawn
        print L
    else:
        for i in range(start, n+1): 
            L.append(i)
            print "L before recursion", l
            helper(n,k,i+1, L) # down to next level
            print "L after recursion", l
            L = L[:-1] 

helper(3,2,1, []) # picking 2 from 3


But this was what I got:
L before recursion [1]
L before recursion [1, 2]
[1, 2]
L after recursion [1, 2]
L before recursion [1, 3]
[1, 3]
L after recursion [1, 3]   
L after recursion [1, 2]  --- l is supposed to be [1] here as quitting the inner recursion 
L before recursion [1, 2]
[1, 2]
L after recursion [1, 2]
L before recursion [1, 3]
[1, 3]
L after recursion [1, 3]

As you can see, L never came back to [1]. It became (at the 8th line of the print-out) [1,2] after executing helper(3,2,2, [1]). Further, there are unmatching numbers of "before" and "after" which made no sense to me.

It took me a couple of hours to think until I realized that maybe the reference of a list was the culprit. So I uncommented the "make a copy" line, and then things worked as expected:
L before recursion [1]
L before recursion [1, 2]
[1, 2]
L after recursion [1, 2]
L before recursion [1, 3]
[1, 3]
L after recursion [1, 3]
L after recursion [1]
L before recursion [2]
L before recursion [2, 3]
[2, 3]
L after recursion [2, 3]
L after recursion [2]
L before recursion [3]
L after recursion [3]

But I still had no clue why a copy fixed it, and even the in-and-out of recursions.
If you know why, let me know.

PS: An alternative fix is to let the function to return L[:-1]. In this way, the old l can be restored after a recursive call.

No comments: