Einsambr Einsambr - 1 year ago 41
Java Question

Is there a more efficient way passing object parameters in recursion?

I would like to do recursion in Java, passing object parameters. Something like this:

int recursion(Object object)
{
//do a little bit modification to the object
int i1= recursion(modified_object_1);
//do a little bit modification to the object
int i2= recursion(modified_object_2);
//do a little bit modification to the object
int i3= recursion(modified_object_3);
return max(i1, i2, i3);
}


Now, because objects are passed by reference, I have to clone the object parameters 3 times and pass the cloned objects to the next recursion. However, this can be extremely inefficient cause I'm doing the recursion tens of thousands of times and the object is complicatedly structured. Is there a more efficient way to do this other than cloning the object?

Thank you~

Answer Source

Firstly a bit of clarity regarding passing by value and reference (the OP seems clear on this but the commenters seem confused). Java objects are not automatically cloned when passed to a function - a reference to the object is passed by value - changing the object in a function will alter the object in the calling context.

So the OP correctly plans that to run his algorithm he needs to first clone the objects and then use the cloned copy to pass down the recursive function chain.

There is however one other possibility which can be easily implemented in SOME cases:

int recursion(Object object)
{
    //do a little bit modification to the object
    int i1= recursion(object);
    //undo the modification to the object
    //do a little bit modification to the object
    int i2= recursion(object);
    //undo the modification to the object
    //do a little bit modification to the object
    int i3= recursion(object);
    //undo the modification to the object
    return max(i1, i2, i3);
}

In cases where this is possible (for example when selecting a possible move when searching game decision trees) it works much more efficiently.

Note that the last undo the changes is required as otherwise the objects higher up the stack will go awry.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download