Home » Questions » Computers [ Ask a new question ]

Why does this recursion not work as expected in python -

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"

Asked by: Guest | Views: 104
Total answers/comments: 0