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:
Post a Comment