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

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

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

对于“静态”，它通常看起来像这样:

static int counter;

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

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

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

这是一个非常简单易懂的解决方案:

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.");
}

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

另外，您可以添加额外的统计信息，它们都干净利落地包装在任务对象中。 “每次迭代的平均时间”？ “平均递归深度”？没问题。任务对象也可用于存储您的结果。

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