0

[Re-writing my question, due to ambiguity.]

Why is it that I can instantiate a HashMap and a Boolean (or even an Integer), pass them to a recursive helper function, peek at my various stack frames and "see" that operations on the HashMap in one frame are detectable in different frames, but I can't also see changes to the Boolean in different frames?

My goal is to be able have a "fast runner" make it to the end of a tree path, while a slower one awaits a "signal" that the "end was reached" and to return whatever node it's on. I could obviously use the hashmap, but why can't I simply pass an Integer (not int), a Boolean, etc.

In my code here, I simulate using a simple counter to recurse 5 times, deposit "3" into a hashmap, and when stack frame 3 "sees" the entry in the hashmap, it knows to return -1, not 0. THIS WORKS FINE. I'm confused why the Boolean baseCaseHit stays FALSE in all but the 5th frame, where it's flipped to TRUE.

static int recursionTest(Integer counter) { // assume 1 is passed in
    Boolean ok = false;
    return recursionTestHelper(counter, ok, new HashMap<Integer, Integer>());
}

// Goal is to recurse 5 times, growing counter, and after two stack frame pops, return -1, else 0
static int recursionTestHelper(int counter, Boolean baseCaseHit,
                               HashMap<Integer, Integer> memo) {

    if (counter == 5) {     // Let this recurse 5 time
        **baseCaseHit** = true; // This Boolean only changes in frame #5
        memo.put(0, 3); // Store 3 at key 0, for stack frame 3 to catch later.
    }
    else {
        int result = recursionTestHelper(counter + 1, baseCaseHit, memo);
    }

    int stackFrameToImpact = memo.get(0);
    if (counter == stackFrameToImpact)  // *This works fine.*
        return -1;      // This signals that all worked as hoped.

    return 0; // This signals that we're still just popping off stack frames.
}


public static void main(String[] args) {
    System.out.println( recursionTest(1) );
}
BlakeSaraDad
  • 5
  • 3
  • The description for this question is very unclear. Try posting some of your code, and provide a better description of the actual problem. Also what do you mean "telling" the other method invocation? Is this a multi-threaded operation? – flakes May 06 '19 at 01:18
  • It sounds like you want to memoize some previous solutions to reduce recursion. For example, if I am computing factorials, I can just check to see if one is computed and return that. Otherwise I start with the largest one I have and continue from there saving each new intermediate value for future calls. Is this correct? – WJS May 06 '19 at 01:22
  • 2
    The answer to your first question is that Java passes all arguments *by value*. `memo` is a reference to a data structure which is mutable. `baseCaseHit` is a reference to an immutable object (`Boolean`). In both cases reassigning the *reference* itself has no impact on what was passed in, because the value of the reference is copied into the function. So you have a copy of the reference, both of which initially point to the same object. Then you change the *copy* to point to a different object. Only by modifying the state of that object will changes be reflected back to the caller. – Mark Peters May 06 '19 at 19:16
  • ^ this comment is the right answer. – shay__ May 06 '19 at 19:19
  • Possible duplicate of [Is Java "pass-by-reference" or "pass-by-value"?](https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) – shay__ May 06 '19 at 19:20
  • 1
    As a practical suggestion, I've often found it's useful to write a recursive algorithm as its own class (possibly a nested private class). Then you can use fields in that class to store variables that are scoped to a single recursive invocation. You'd start a new recursive call by instantiating the class and calling a method. For example: `new RecursiveFunction().start()`. – Daniel Pryden May 06 '19 at 19:36
  • I'm embarrassed (or I like to say, "ember-assed"). I didn't realize that wrapper classes are immutable. So...besides passing my HashMap as a way to notify a stack frame of something that occurred in higher/later frame, it appears I should just pass my own custom object -- but I seek simplicity! (I've seen contributors here say that's "ugly", however, and wonder what's a better solution.) – BlakeSaraDad May 06 '19 at 19:37
  • @BlakeSaraDad: If you're looking for a threadsafe mutable boolean, `AtomicBoolean` might be an option. However I would caution that most recursive algorithms are most clear if you find a way to maintain functional purity, that is, information is passed only via function inputs and outputs. Sometimes that means returning a pair of values rather than a single value, which in Java (due to it lacking language-level *tuple* support) might require a simple data class. – Mark Peters May 06 '19 at 19:50

0 Answers0