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