java - 如何在递归中使用索引变量？

Question

我想在递归中使用索引变量，而不是在调用函数时将其作为参数发送。但是，如果我在开始时重置它（例如 i = 0），它会在每次运行时重置。我想将它用作计数器（计算函数运行次数）。

Answer 1

首先，您显然只想初始化一次。递归中的一个常见模式是：

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

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

外部方法只做一些初始化。

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

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 3

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.

Answer 4

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 5

最自然的做法是使用您在帖子中描述的辅助参数，特别是如果它用于确定何时停止递归。如果依赖一个成员变量，你可以有一个帮助方法，在调用递归方法之前重置计数器，并在你想调用递归函数时调用帮助方法。

如果您更喜欢使用单一方法，则必须执行以下操作：

创建一个名为的成员变量insideMethod，默认设置为 false。调用该方法时，它会检查此变量。如果它是假的，它是第一次调用，计数器应该被重置，否则计数器应该只是递增。之后，insideMethod设置为true。返回时，insideMethod应将其设置回 false，仅当是此调用将其设置为 true 时。

记得makeinsideMethod和索引变量ThreadLocal。

伪代码：

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
}