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

How to use an index variable in a recursion?

提问by amiregelz

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

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

回答by Has QUIT--Anony-Mousse

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!

您经常会看到建议的“解决方案”（例如在您的问题的第一条评论中）将使用静态变量。这种方法是一种糟糕的风格，一旦您添加多线程（例如，通过制作 UI 版本，或在多线程 Web 服务器中运行它），就会导致您的程序以各种奇怪的方式失败。最糟糕的是，它可能一开始似乎可以工作，但只有在用户众多时才开始微妙地行为不端。因此，除了常量之外的所有内容都远离“静态”！

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 startat the same time. They will overwrite each others counter!Because static means, it's shared amongst threads and users.

现在想象两个用户同时调用start。他们将覆盖彼此的计数器！因为静态意味着，它在线程和用户之间共享。

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.

然后创建一个任务，运行它，并在最后检索计数器。干净、简单、高效、可靠。如果您有多个线程/用户，则每个线程/用户都有一个单独的 MyTask 对象，您不会遇到任何问题。

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 ThreadLocalhas 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 ThreadLocaland the task object and you'll see the difference. Plus, ThreadLocalis empirically 10x slower than accessing heap values (see https://stackoverflow.com/a/4756605/1060350). For intit likely is even worse. So never ever call ThreadLocal#getin 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.

ThreadLocal这里已经建议使用。我不同意这一点。它根本没有提供任务对象的任何好处。只需尝试使用ThreadLocal和 任务对象来实现它，您就会看到不同之处。另外，ThreadLocal凭经验比访问堆值慢 10 倍（参见https://stackoverflow.com/a/4756605/1060350）。因为int它可能更糟。所以永远不要调用ThreadLocal#get性能关键的代码路径。如果您打算使用ThreadLocal，请在此代码路径之外使用它，并使用局部变量（或任务对象）将“局部静态”变量提供给您的关键代码路径。

回答by joanlofe

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

您应该使用两种方法将其分开：一种是公共方法，用于启动递归迭代并将计数器初始化为零，另一种是私有方法，即进行递归调用。这样每次调用公共方法时，计数器都会被初始化。它会是这样的（在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;
    }
}

回答by Patrick Linskey

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

考虑到索引用作停止条件，我会采用简单的基于参数的方法。JavaScript 实现：

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:

但是，如果您只想调用某个函数一定次数，为什么要特别使用递归？你可以只使用一个循环。再次在 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.

编译器使用展开循环比使用递归构造更有趣，这取决于递归算法的复杂性。

回答by user unknown

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?

从我得到的评论中，您将其用作计数器，以检测何时结束递归。那看起来不是很有用。你没有可以从参数中导出的条件，比如 list.length() 之类的吗？

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.

如果您想在调试时防止堆栈溢出，一个古玩替代方法是调用随机数生成器，并在 10 000 种情况中的一种情况下返回。

回答by aioobe

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 methodyou'll have to do something like this:

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

Create a member variable called insideMethodwhich 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 insideMethodis set to true. Upon returning, the insideMethodshould be set back to false, only if it was thisinvokation that set it to true.

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

Remember to make insideMethodand the index variables ThreadLocal.

记得makeinsideMethod和索引变量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
}