CODEWITHSUNDEEP
javarecursion
user1220022
user1220022

Reputation: 12075

java retain information in recursive function

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.

Upvotes: 16

Views: 34841

Answers (8)

emory
emory

Reputation: 10891

I think this is called memoization. It looks like

class Fibonacci
{
     public Map < Integer , Integer > memorized = new HashMap < > ( ) ;

     public int fib ( int n )
     {
           if ( memoized . containsKey ( n ) )
           {
                 return memoized . get ( n ) ;
           }
           else
           {
                 int fib = // calculate recursively
                 memoized . put ( n , fib ) ;
                 return fib ;
           }
     }
}

You should be able to get decent (not optimal) performance out of this algorithm. The primary reason that the recursive fibonacci algorithm has horrible performance is b/c it is repeatedly calculating the same values. With recursion+memoization it never calculates any value more than once.

Thanks to @Aristide for pointing out the subtle difference between memorization and memoization.

Upvotes: 0

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 235984

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().

Upvotes: 31

Kannan
Kannan

Reputation: 136

You can pass an object to store the update for each recursive call. Something like the one below.

public static void fooHelper(int depth, HashMap map){
      map.put(depth, "Call " + depth);
      if (depth > 0)
      {
        fooHelper(depth-1, map);
      }
      return;
    }

Upvotes: 0

krishnakumarp
krishnakumarp

Reputation: 9295

Because the variable v is of primitive type, changes made to it will not be visible outside the function scope. You could declare the variable v inside a class, say State and pass the state object into the recursive function to get the required effect.

public void foo(){
    State state = new State();
    fooHelper(state, 2);
}

public void fooHelper(State state, int depth){
    state.v++;
    fooHelper(state, depth-1);
}

class State {
    int v;
}

Hope it helps.

Upvotes: 0

trutheality
trutheality

Reputation: 23455

You could return a list or a similar data structure:

public List<Integer> fooHelper( int v, int depth ){
    if( depth == 0 ) return new ArrayList();

    v++;
    List<Integer> result = fooHelper( v, depth-1 );

    result.add( new Integer(v) );

    return result;
}

Upvotes: 0

Shashank Kadne
Shashank Kadne

Reputation: 8101

Why not make it an instance variable(not necessarily static)...??

public class Recursive {
    int v = 0;
    public void foo(){

        fooHelper(2);
        System.out.println(v);
    }

    public void fooHelper(int depth){
        v++;
        if(depth-1!=0)//Added this because I was getting an StackOverflowError
        fooHelper(depth-1);
    }

    public static void main(String[] args) {
        Recursive r = new Recursive();
        r.foo();
    }
}

Upvotes: 0

ricochet1k
ricochet1k

Reputation: 1252

You can create a new class (yuck), or pass the variable as a parameter and return it in fooHelper.

Upvotes: 0

MByD
MByD

Reputation: 137272

A variable declared in a scope (for example method) is accessible only in this scope (e.g. not in another method).

If the information is relevant for the method only, keep the variable in the method. If the information is relevant for the whole object / class state, keep it a class member (static/non static).

For example:

public void someRecursiveMethod(int num) {
    while (num < 10) {
        num++;
        someRecursiveMethod(num);
        System.out.println("Current num = " + num);
    }
}

Upvotes: 1

Related Questions