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