How to use an index variable in a recursion?

Question

I want to use an index variable inside a recursion, without sending it as a parameter when calling the function. However, if I reset it at the beginning (e.g i = 0), it will reset on every run. I want to use it as a counter (to count the function runs).

Solution 1

First of all, you will obviously want to initialize it only once. A common pattern in recursion is:

public void run(int opt) {
  run_helper(opt, 0);
}

private void run(int opt, int depth) {
  if (whatever) { run(opt, depth + 1); }
}

Where the outer method does nothing but some initialization.

A "solution" you will see suggested often (e.g. in the first comment to your question) will be to use static variables. This approach is a bad style, and will cause your program to fail in various weird way once you add multi-threading (e.g. by making a UI version, or run it in multithreading web server). And the worst is that it may at first appear to work, and only start misbehaving subtly when there are many users. So keep away from "static" for everything except constants!

With "static" it would commonly look like this:

static int counter;

public void start() {
  counter = 0;
  recurse();
}

public void recurse() {
  counter += 1;
  if (whatever) { recurse(); }
}

Now imagine that two users invoke start at the same time. They will overwrite each others counter! Because static means, it's shared amongst threads and users.

Here is a really simple to understand solution:

class MyTask {
  int counter = 0;

  public void recurse() {
    counter++;
    if (whatever) { recurse(); }
  }

  public int getIterations() {
    return counter;
  }
}

public void run() {
  MyTask task = new MyTask();
  task.run();
  System.out.println("Task took "+task.getIterations()+" itertions.");
}

You then create a task, run it, and retrieve the counter at the end. Clean, dead simple, efficient and reliable. If you have more than one thread/user, each will have a separate MyTask object, and you won't run into any problem.

Plus, you can add additional statistics, and they are all cleanly wrapped in the task object. "Average time per iteration"? "Average recursion depth"? No problem. The task object can also be used to store your result.

The use of ThreadLocal has been suggested here. I do not agree with this. It offers no benefits of the task object at all. Just try to implement it with ThreadLocal and the task object and you'll see the difference. Plus, ThreadLocal is empirically 10x slower than accessing heap values (see https://stackoverflow.com/a/4756605/1060350 ). For int it likely is even worse. So never ever call ThreadLocal#get in a performance critical codepath. If you intend to use ThreadLocal, use it outside of this codepath, and use a local variable (or a Task object) to feed the "local static" variable into your critical codepath.

Solution 2

You should separate it using two methods: one public to start the recursive iterations and initialize the counter to zero, and another private one, that is where the recursive calls are made. This way every time you call the public method the counter gets initialized. It would be something like this (in java):

public class Recursion{
    private int iterations=0;

    private int calcFactorial(int n){
        iterations++;
        if (n==2)
            return 2;
        else
            return n * calcFactorial(n-1);
    }

    public int factorial(int n){
        //initialize the counter
        iterations = 0;
        return calcFactorial(n);
    }

    public int getIterations(){
        return iterations;
    }
}

Comments

[Has QUIT--Anony-Mousse]

ThreadLocal<Integer> will perform quite bad, because it requires creating a lot of Integer objects, thus putting quite a load on the garbage collection.

[aioobe]

I'm smelling premature optimization.

[aioobe]

why do you propose to have a static variable in the first place?

[Has QUIT--Anony-Mousse]

There is a much simpler solution, see my reply. Wrap it into a task object. I have really bad experiences with frequently changing wrapped native types in Java. It has killed performance in too many sitations for me to keep away from it wherever possible. At least, change it to a Counter object that isn't immutable. In fact, I doubt that your code actually compiles. index++ should not work on ThreadLocal<Integer> objects...

[Has QUIT--Anony-Mousse]

Because that is the common solution people come up with. It needs to be discussed, and the drawbacks need to be pointed out. In particular, since Eclipse likes to suggest making variables static to "fix" access errors.

[aioobe]

I said it was pseudo code. Saying that ThreadLocals will perform poorly is completely ridiculus when not knowing how the rest of the method is implemented. Creating a seperate task object is fairly ok, but is a bit counterintuitive. A regular method call may look cleaner.

[aioobe]

I can't see why anyone would suggest to make this type of variable static though.

[Has QUIT--Anony-Mousse]

See the first comment posted on the question. It suggests using a static variable. And in fact, a static variable will work, as long as you are not reentrant or multithreaded. I.e. don't use a swing UI. That is usually when those static variables start failing on people, when they have an UI.

[aioobe]

I just fail to see the benefit of sharing the variable among all instances of the class.

[Has QUIT--Anony-Mousse]

He probably doesn't have a linear recursion. There are plenty of non-linear problems like this. For example in an XML tree, find the first (in document order) 10 nodes at depth 3 or more.

[Has QUIT--Anony-Mousse]

It's bound to break. That is well known. Search for "+static +java" on stackoverflow for a horror cabinet of misuses of static. But unless you tell them why not to use static, they'll use it because it appears to be the simplest solution to their problem.

[Has QUIT--Anony-Mousse]

If you'd go from simplified pseudocode to real code, it would be easy to see that ThreadLocal is not much more "intuitive" to use than just making a task object. In fact, it is pretty messy.