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

Answer 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.

Answer 2

The most natural thing to do, is to have an auxilliary parameter as you describe in your post, especially if it is used to determine when to stop the recursion. If relying on a member variable you could have a helper method that resets the couter before calling the recursive method, and call the helper-method whenever you want to invoke the recursive function.

If you prefer to stick with a single method you'll have to do something like this:

Create a member variable called insideMethod which is set to false by default. When the method is called, it inspects this variable. If it is false, it is the first call, and the counter should be reset, otherwise the counter should just be incremented. After that, the insideMethod is set to true. Upon returning, the insideMethod should be set back to false, only if it was this invokation that set it to true.

Remember to make insideMethod and the index variables ThreadLocal.

Pseudo code:

ThreadLocal<Boolean> insideMethod = false
ThreadLocal<Integer> index = 0

....

void recMethod(args) {
    boolean topCall = (insideMethod == false)
    insideMethod = true

    if (topCall)
        index = 0
    else
        index++

    // Body of the method...

    if (topCall)
        insideMethod = false
}

Answer 3

You can use an attribute, but why? Why not passing the value as parameter?

public class Empty {

    private int steps = 0;  

    public static void main (String args [])
    {
        Empty e = new Empty ();
        System.out.println (e.reverse ("This is a test"));
        System.out.println ("steps: " + e.steps);
    }

    public String reverse (String s) {
        ++steps;
        if (s.length () < 2) 
            return s;
        else return reverse (s.substring (1)) + s.charAt (0);
    }
}

From the comments I get, that you use it as counter, to detect when to end the recursion. That doesn't look very useful. Don't you have a condition which can be derived from the parameters, like list.length () or such?

Of course, calling the method twice will increase the counter further. You might reset it, if it isn't used by two thread concurrently, and a wrapped method in an inner object might help to prevent calling it without resetting the counter first.

But that is much more boilerplate than passing the counter around.

A parameter is a much cleaner solution for counting the invocations.

If you want to prevent stackoverflows while debugging, a curios alternative is to call a randomizer, and return in 1 of 10 000 cases.

Answer 4

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;
    }
}

Answer 5

I'd go with a simple parameter-based approach, given that the index is used as a stop condition. JavaScript implementation:

var recurse = function() {
    recurseHelper(0);
};

var recurseHelper = function(iteration) {
    // run for 100 iterations, 
    if (iterationCount > 100)
        return;

    // do stuff...


    recurseHelper(iteration + 1);
}

However, if you just want to invoke a function a certain number of times, why are you looking to use recursion in particular? You could just use a loop. Again in JavaScript:

for (var i = 0; i < 100; i++) {
    // do stuff...
}

Compilers can have more fun with unwinding loops than with recursion constructs, depending on the complexity of your recursion algorithm.