A lookup object as an argument of a recursion

Question

We're using a recursion that iterates through tree nodes and does some computation that is a logical equivalent of something as

public static Result iterate(TreeNode node, Dictionary dictionary ) {
    Map<String, Result> accumulated = new HashMap<String, Result>();
    for (TreeNode child : node.getChildren()) {
        Result partialResult = iterate(child, dictionary);
        accumulated.put(child.getId(), partialResult);
    }
    return completeResult(accumulated);
}

Now the Dicitionary object is not mutated while the recursion is being done. Its simply used as a lookup table. The object is in fact quite big.

Does the fact that we have the dictionary as an argument of our recursive call have a negative impact on the memory/performance? Is this a bad design?

I can't see any recursion? A recursive method is one that calls itself. I can't see anywhere in this method where iterate() is called. Unless the call to iterate() is embedded in one of the other methods like assemble? — Ben Thurley, Mar 09 '16 at 11:05
The answer is no (and no): you just pass an object reference. — laune, Mar 09 '16 at 11:07
Have a look at this question http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value — Ben Thurley, Mar 09 '16 at 11:08
I'd be more concerned about this method being declared as static, but since it is just a "logical equivalent" I'll not harp on that. — laune, Mar 09 '16 at 11:11
please do, and thank you for your comment. I encourage you to make it an answer, it is helpfull for me, hence, I expect for others — learnAndImprove, Mar 09 '16 at 11:13

score 1 · Answer 1 · answered Mar 09 '16 at 11:21

I would say your design is correct, in that it should produce correct results. For its performance, you would really need to do some thorough testing to assess, with various combinations of sizes for your tree structure and dictionary. Also, the implementation of Dictionary will probably play a major role in the performance characteristics.

Memory-wise, your current implementation should be the most economical, as you use the existing structures, instead of copying to others, in order to use a faster algorithm.

Passing the dictionary as an argument has the benefit of isolating each recursive run, in the case that the dictionary can change between runs, and provided that you copy the dictionary for each run. Also, it gives you the capability of using the same code to do concurrent searches (using threads) on different trees using different dictionaries. Using a global dictionary wouldn't allow you to do this.

score 1 · Accepted Answer · answered Mar 09 '16 at 11:21

1

The really interesting issue is: "How is the Dictionary related to the Tree?"

If several Dictionaries need to be used with different iterations, you would indeed pass a Dictionary as a parameter to the iterate method, as you have it right now. (But why it "iterate" static?)

If a Dictionary is a stable property associated with some specific Tree object, its reference should be passed to the constructor and stored as an instance field. The iterate being a method could access it as any other instance field.

Possibly the Dictionary is universal and unique for all Tree objects? Then you might advocate setting the Dictionary as a static class field, and your iterate method would access it as a "global".

Technically, all of the above just passes a reference ("address") around; no copying of a potentially huge object is involved...

answered Mar 09 '16 at 11:21

laune

31,114
3
29
42

The whole question was "bad" in a sense that I thought that the method arguments will be placed in the stack, this I could have read before without asking, but I asked -1 for me +1 for you. About the static, the dictionary is universal and unique, and the method is static since it uses only arguments and does not interact with the instance variables. Or am I maybe wrong about it. Having dictionary as a static class field would be quite OK, but in general, from what I understood, the design as is is not "obviously" wrong? – learnAndImprove Mar 09 '16 at 11:30
The generally accepted way is to use a proper class even when only one object is planned/required within the app. Also, think about testing. – laune Mar 09 '16 at 11:45

score 1 · Answer 3 · answered Mar 09 '16 at 11:31

I think this question boils down to whether Java passes by reference or value. Somewhat confusingly Java always passes by value, but where an object is passed the value is the object reference.

So for your example the method iterate takes a parameter Dictionary dictionary. The internals of this object will be stored on the heap. This is an area of memory that is shared among all objects. Additionally your method will have it's own unique reference on the stack. The reference acts as a kind of pointer so your method can lookup the values of dictionary.

When you make the recursive call the JVM will make a new reference to the same dictionary object and put this reference on the stack for the new method call. So now you have two calls to iterate on the call stack, both with their own individual reference to the dictionary object, but only one actual dictionary object on the heap.

If you were to make changes to the dictionary object using either reference it would update the same underlying object so both methods would see these changes.

When the method returns, since the dictionary reference is local to the method it will be removed from the stack. This will reduce the reference count to this object by 1. If the total number of references reaches 0 then your object becomes eligible for garbage collection since nothing will be able to see it.

Back to your question about memory I don't think you need to worry. It's the object on the heap where all of the data will be. References are cheap by comparison (8 bytes for a Java reference). Each reference will in theory take up a little memory but you are only likely to hit problems if your recursive loop doesn't exit.

Thanks Ben, yes. In my mind I mistakenly thought that both local method variables and the passed in variable will end up in stack. Hence all the confusion. Nice reassuring though — learnAndImprove, Mar 09 '16 at 11:35
Well since Java is pass by value, if you passed a primitive type such as an int or boolean then it's true you would have a duplicate variable on the stack. This isn't likely to pose a problem either as these variables don't take up much memory. — Ben Thurley, Mar 09 '16 at 11:38

A lookup object as an argument of a recursion

3 Answers3