Python Recursion Backtracking Variable

Question

I am writing some recursive function. Consider its prototype to be:

def path(a, row=0, col=0, weight=0, cumulative=[])

I am trying to find some path in the matrix a. The weight adds the values of that path so far and cumulative keeps track of the path.

At some point, this is invoked:

return path(a, row+1, col, weight, cumulative) + path(a, row+1, col+1, weight, cumulative)

Now the base case is as follows:

cumulative.append(a[row][col])
weight = weight + a[row][col]
return weight

which adds the current matrix element into cumulative, adds the weight and returns the weight. The problem is that each time cumulative calls append, it adds to the very same instance of cumulative. How can I ensure that each recursive stack frame takes a different copy of cumulative?

So when append is called in the base case, I want the value of cumulative called to be of the frame caller and not the previous recursive stack frame.

Any suggestions? Thanks.

It would be helpful to see your whole function if you don't mind posting :) — Michael Mior
– Michael Mior, Commented Nov 12, 2012 at 14:30
One thing I'll point out in case you weren't aware. When a default parameter is set to a mutable value such as a list (e.g. cumulative=[]), that value is only initialized once when the function definition is read. That means any time you call path without specifying cumulative, the same list will be used. — Michael Mior
– Michael Mior, Commented Nov 12, 2012 at 14:33
Thanks Michael - yes I'm aware of that. mux below answered it. I needed a separate instance of cumulative for each frame. Apparently Python passes by reference (something I'm going to read about now). — darksky
– darksky, Commented Nov 12, 2012 at 14:34

iabdalkader · Accepted Answer · 2012-11-12 14:31:42Z

1

you could call with a copy of cumulative:

return path(a, row+1, col, weight, list(cumulative)) + 
       path(a, row+1, col+1, weight, list(cumulative))

answered Nov 12, 2012 at 14:31

iabdalkader

17.4k4 gold badges51 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python Recursion Backtracking Variable

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related