How to keep count of “things” in a recursive algorithm in Java?

Question

I have a recursive algorithm that goes through a string, character by character, and parses it to create a tree structure. I want to be able to track the index of the character the parser is in (for error messages, like everything else), but I'm not interested in implementing something like a tuple to handle multiple return types.

I tried using the Integer type, declared outside the method and passed to the recursive method, but since it is final, when I return, the “forgotten” increments of the recursive call are returned. (Since incrementing an Integer value makes the object an anchor point by default for the new object)

Is there a way to get something similar to a job that doesn't pollute my code?

Answer 1

Since you have already discovered a pseudo-mutable integer to “crack”, how about this option:

Does it make sense to make a separate Parser class? If you do this, you can save the current state in a member variable. You probably need to think about how you will deal with any thread safety issues, and this might be redundant for this particular application, but it might work for you.

Answer 2

It's kind of a hack, but sometimes I use AtomicInteger, which is modified to do such things. I also saw cases when an int [] of size 1 is passed.

Answer 3

The current solution I'm using is:

int[] counter = {0}; 

and then pass it to a recursive algorithm:

 public List<Thing> doIt (String aString, int[] counter) { ... } 

and when I want to increase it:

 counter[0]++; 

Not super elegant, but it works ...

Answer 4

Integers are immutable, which means that when passed as an argument, it creates a copy, not a link to the same element. ( explanation ).

To get the behavior you are looking for, you can write your own class, which is similar to Integer, just modified. Then just pass it to the recursive function, it will be incremented within the recursion, and when you run it again after the recursion is complete, it will still save its new values.

Edit: Note that using the int [] array is a variation of this method ... In Java, arrays are also passed by reference, not copied as primitives or immutable classes.

Answer 5

You can simply use a variable of a static type that increments with every call to the doIt method.

Answer 6

You can also do:

 private int recurse (int i) { if (someConditionkeepOnGoing) { i = recurse(i+1); } return i; } 

Answer 7

Honestly, I would recode the function to make it a linear algorithm that uses a loop. Thus, you have no chance to run out of the heap if you go through a very large line. In addition, you do not need to have an additional parameter to track the score.

It is also likely to make the algorithm faster because it does not need to make a function call for each character.

Unless, of course, there is a definite reason, it must be recursive.

Answer 8

One possibility that I can think of is to store the score in a member variable of the class. This, of course, assumes that the public doIt method is called by only one thread.

Another option is to reorganize the public method to invoke the private helper method. The private method takes a list as a parameter and returns a counter. For instance:

 public List<Thing> doIt(String aString) { List<Thing> list = new ArrayList<Thing>(); int count = doItHelper(aString, list, 0); // ... return list; } private int doItHelper(String aString, List<Thing> list, int count) { // ... // do something that updates count count = doItHelper(aString, list, count); // ... return count; } 

It is assumed that you can perform error handling in the public doIt method, since the count variable does not actually return back to the caller. If you need to do this, you can, of course, throw an exception:

 public List<Thing> doIt(String aString) throws SomeCustomException { List<Thing> list = new ArrayList<Thing>(); int count = doItHelper(aString, list, 0); // ... if (someErrorOccurred) { throw new SomeCustomException("Error occurred at chracter index " + count, count); } return list; } 

It's hard to see if this will help without knowing more about how your algorithm works.