How to store values to array when doing recursion?

Question

For example, in this method, the method builds an array of sorted from a BST

public E[] inOrderSort(TreeNode tree){
    E[] array1 = new E[tree.size];
    inOrder(tree, array1, 0);
    return array1;
}

public void inOrder(TreeNode node, E[] array, int index){
    if(node == null){  
        return;
    }
    inOrder(node.getLeft(), array, index);  
    array[index++]= node.getData();          
    inOrder(node.getRight(), array, index);
}

Here, how am I getting the correct result when array1 is returned in the inOrderSort method? How did Java pass the array1 declared in the method inOrderSort to the inOrder method can fill up the values for array1 in inorder sort? I thought Java is pass by reference not pass by value?

Possible duplicate of [Is Java "pass-by-reference" or "pass-by-value"?](http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) — nhouser9, Sep 28 '16 at 05:55

score 1 · Answer 1 · answered Sep 28 '16 at 06:40

Primitive values are passed-by-value. So anything that is done to the index variable in inOrder won't have an effect in the caller. The array is not a primitive and is passed-by-reference, thus, any modification to it will be visible to the caller.

Now you have two options:

wrap the index position in an object (NOT an Integer because it's immutable, AtomicInteger would do, same as an int[] with one element) - But I wouldn't do it that way because the intention of the method is to apply ordering to the array and not updating the index. The index is nothing more than a hint for the sort function.
return the new index as result and use it in the following calls (I'd prefer this one)

For Example:

public int inOrder(TreeNode node, E[] array, int start){
  if(node == null){  
    return;
  }
  int index = inOrder(node.getLeft(), array, start);  
  array[index++]= node.getData();         
  return inOrder(node.getRight(), array, index);
}

Amber Beriwal · Answer 2 · 2016-09-28T09:56:13.587

0

Java uses call-by-reference for all object types, but primitive types are call-by-value.

In your case, index being a primitive type will not keep its value retained across recursions. index will act like a local variable and its scope is limited to function call stack trace, where array1 being an object will be passed as reference and can retain its values across recursion, because its scope is java heap.

Try using return values:

public E[] inOrderSort(TreeNode tree){
    E[] array1 = new E[tree.size];
    int index = 0;
    index = inOrder(tree, array1, index);
    if(index != tree.size){
        //error
    }
    return array1;
}

public int inOrder(TreeNode node, E[] array, int index){
    if(node == null){  
        return index;
    }
    index = inOrder(node.getLeft(), array, index);  
    array[index]= node.getData();         
    index++;
    index = inOrder(node.getRight(), array, index);
    return index;
}

edited Sep 28 '16 at 09:56

answered Sep 28 '16 at 06:23

Amber Beriwal

1,568
16
30

1

The _stack_ is made of _stackframes_, if the _stack_ would be the scope, than it would be visible to all or at least the subsequent frames. And if not heap, where are all the local variables supposed to be kept, in non-heap memory? And finally, how should an `Integer` help here when it is immutable? It's an object represention of a value and not a container for it. – Gerald Mücke Sep 28 '16 at 06:48
@GeraldMücke Thanks..Slipped the immutability factor so modified the code snippet. made correction in theory as well. – Amber Beriwal Sep 28 '16 at 09:58
@GeraldMücke Is there any place available for local variables other than stack frames? – Amber Beriwal Sep 28 '16 at 09:59
1

No, they are kept in the _frames_ and not in the _stack_ (stack only contains frames) or to be more precise in the local variable array of a frame. The variable array is only visible to the frame and not to the entire stack or other frames. Only values (including references) are passed between frames. So changing a value in a frame is only visible to the frame itself and not other. – Gerald Mücke Sep 28 '16 at 13:14
@GeraldMücke ok. Thanks :) – Amber Beriwal Sep 28 '16 at 13:21

score 0 · Answer 3 · answered Sep 28 '16 at 06:37

0

Variable array1 is a reference to array object. When you pass array1 to method you pass it by value (value of reference) and then you can modify object by that reference in inOrder() method.

answered Sep 28 '16 at 06:37

olsli

831
6
8

How to store values to array when doing recursion?

3 Answers3