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.

  • $\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$ – John L. Jul 15 '19 at 17:16