|
Why does this recursion not work as expected in python -
"res = []
A = [1,2,3]
def permute(idx, path):
if idx >= len(A):
# base case
print(path)
res.append(path)
return
for i in range(idx, len(A)):
path[i],path[idx] = path[idx], path[i]
permute(idx+1, path)
path[i],path[idx] = path[idx], path[i]
permute(0,A)
print(res)
So I'm trying to build all the permutations of an array using recursion. Here in the base case if I try printing the path variable, I'm getting something like this:
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]
But I am appending the same path to the global res array and I'm getting this in the res list :
[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]
I found a turn-around by doing res.append(list(path)) or a res.append(path[:]), it is working as expected. I'm having a hard time understanding how this is working. In the base case, I can see the changed path variable by printing it, does this not mean the same would be appended to the list?
Also, what is the best practice when I have to work with recursive functions and changing variables, is there any better way than not passing the entire variable every time?
python recursion global-variables permutation local-variables
ShareShare a link to this question Copy linkCC BY-SA 4.0
Follow
Follow this question to receive notifications
asked 6 mins ago
Piyush RautPiyush Raut
10133 bronze badges"
| 