Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

java retain information in recursive function

Tags:

java

recursion

Is it possible to retain information via a helper function with java, without using static variables.

For example,

public void foo(){
    int v = 0;
    fooHelper(2);
}

public void fooHelper(int depth){
    v++;
    fooHelper(depth-1)
}

Namely I want to update variable v without loosing the information for each recursive case, without having to access a variable outside the function.

like image 886
user1220022 Avatar asked Apr 22 '12 05:04

user1220022


1 Answers

Forget about all the answers that tell you to declare attributes, or to update mutable objects in each recursive call. In a true functional, recursive style you "retain" information by passing it as parameters and/or return types.

Let me illustrate with a simple example, let's say that you want to recursively calculate the sum of the elements in an int[]. Here, the state (the information that needs to be retained between recursive calls) is the current index in the array and the sum so far. Here's how to do it:

public int sum(int[] array) {
    return sum(array, 0, 0); 
}

private int sum(int[] array, int idx, int acc) {
    if (idx == array.length)
        return acc;
    return sum(array, idx+1, acc+array[idx]);
}

Call it like this:

int[] array = {1, 2, 3};
System.out.println(sum(array));

As you can see, there's no need to declare (static or instance) attributes, and no need to pass and modify mutable objects (lists, maps) - I'm not even using local variables, because all the required information needed to solve the problem is present as method parameters.

In the code in your question the v variable is supposed to do what the acc parameter is doing in my answer, namely: modifying an accumulated value each time the recursion is called. In the end, you just need to return the accumulated value from the helper function (which must not have a void return type) and that's how you'll get the value in foo().

like image 178
Óscar López Avatar answered Oct 02 '22 18:10

Óscar López