1
$\begingroup$

In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to it's original state once all children have been recurred on. See the image below for an example.

enter image description here

However, when using a mutable type such as an integer this is impossible. If we try to 'modify' an integer by using a reference to it in memory a new integer will be created. This makes it impossible to backtrack with immutable types.

What is the best practice way around this? We could store the integer in a list like this [0] but then we would be using a list data structure for a very non list-like purpose which isn't ideal in my books.

Any ideas would be appreciated.

$\endgroup$

closed as off-topic by David Richerby, dkaeae, Evil, Discrete lizard Jul 18 at 18:55

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – David Richerby, dkaeae, Evil, Discrete lizard
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I am afraid that I failed to see a real problem. In fact, String is implemented as immutable type in Python although it looks like mutable. The usage of "String" in your example could be more accurately represented by "StringBuilder" in Java or C#, whose implementation is based on an array. Similarly, you could create "IntegerBuilder", a mutable type of integer similar to java.math.MutableBigInteger. Once you want to mutate an integer in-place, you will be using a list-like data structure. $\endgroup$ – Apass.Jack Jul 15 at 17:16