打破java中的递归

Breaking out of a recursion in java

提问by Stasis

The recursion is sort of a 'divide and conquer' style, it splits up while getting smaller (Tree data structure), and I want it to break completely if a violation is found, meaning break all the recursive paths, and return true. Is this possible?

递归是一种“分而治之”的风格，它在变小（树数据结构）的同时分裂，如果发现违规，我希望它完全中断，这意味着中断所有递归路径，并返回真。这可能吗？

采纳答案by Tom

You could return an error code, or modify some global variable so that each recursive instance knows to "kill itself".

您可以返回错误代码，或修改一些全局变量，以便每个递归实例知道“杀死自己”。

Something of the sort.

那种东西。

int foo(bar){
     int to_the_next;

      if (go_recursive){
            to_the_next = foo(whisky_bar);

            if (to_the_next ==DIE) return DIE;
      }

      if (something_unexpected_happened) return DIE;

      process;//may include some other recursive calls, etc etc
}

回答by Joe Phillips

You can do something similar by storing a variable that tracks whether the recursions should break or not. You'd have to check it every recursion unfortunately but you can do it.

您可以通过存储一个跟踪递归是否应该中断的变量来做类似的事情。不幸的是，您必须在每次递归时检查它，但您可以做到。

回答by Tom

If it's a single thread doing the recursion you could throw an exception. Bit ugly though - kind of using an exception as a goto.

如果它是执行递归的单个线程，则可能会引发异常。虽然有点丑 - 有点使用异常作为转到。

boolean myPublicWrapperMethod(...) {
    try {
        return myPrivateRecursiveFunction(...);
    } catch (MySpecificException e) {
        return true;
    } 
} 

A better approach would be to eliminate the recursion and use a Stack collection holding a class representing what would have been recursive state, iterate in a loop and just return true when you want.

更好的方法是消除递归并使用 Stack 集合，该集合包含一个表示递归状态的类，在循环中迭代并在需要时返回 true。

回答by Greg Case

Unless recursive calls are being evaluated in parallel, you probably just need to add some logic to check the first recursive call's value prior to making the second (and subsequent, if not a binary tree structure) recursive call.

除非并行评估递归调用，否则您可能只需要添加一些逻辑来检查第一个递归调用的值，然后再进行第二个（以及后续的，如果不是二叉树结构）递归调用。

public abstract class Tree {

    protected abstract boolean headIsViolation();

    protected abstract boolean isLeaf();

    public Tree getLeft();

    public Tree getRight();

    // Recursive
    public boolean checkViolation() {
        if(this.isLeaf()) {
            return this.headIsViolation();
        }

        // If needed, you could pass some sort of 'calculation state'
        // object through the recursive calls and evaluate the violation
        // through that object if the current node is insufficient
        if(this.headIsViolation()) {
            // Terminate the recursion
            return true;
        }

        // Fortunately, Java short-circuits ||
        // So if the left child is in violation, the right child will
        // not even be checked
        return this.getLeft().checkViolation() || this.getRight().checkViolation();
    }
}

回答by Kevin Day

No matter what you do, you are going to have to unwind the stack. This leaves two options:

无论您做什么，您都将不得不展开堆栈。这留下了两个选择：

1. Magic return value (as described by one of the Toms)
2. Throw an exception (as mentioned by thaggie)

1. 神奇的返回值（如其中一位汤姆斯所描述的）
2. 抛出异常（如 thaggie 所述）

If the case where you want things to die is rare, this may be one of those situations where throwing an exception might be a viable choice. And before everyone jumps down my throat on this, remember that one of the most important rules of programming is knowing when it's appropriate to break the rule.

如果您希望事情消失的情况很少见，这可能是抛出异常可能是一种可行选择的情况之一。在每个人都对此嗤之以鼻之前，请记住，最重要的编程规则之一是知道何时适合打破规则。

As it turns out, I spent today evaluating the zxing library from google code. They actually use exception throws for a lot of control structures. My first impression when I saw it was horror. They were literally calling methods tens of thousands of times with different parameters until the method doesn't throw an exception.

事实证明，我今天花了从谷歌代码评估 zxing 库。他们实际上对许多控制结构使用异常抛出。当我看到它时，我的第一印象是恐怖。他们实际上是用不同的参数调用方法数万次，直到方法不抛出异常。

This certainly looked like a performance problem, so I made some adjustments to change things over to using a magic return value. And you know what? The code was 40% faster when running in a debugger. But when I switched to non-debugging, the code was less than 1% faster.

这当然看起来像是一个性能问题，所以我做了一些调整，将事情改为使用魔法返回值。你知道吗？在调试器中运行时，代码速度提高了 40%。但是当我切换到非调试模式时，代码速度不到 1%。

I'm still not crazy about the decision to use exceptions for flow control in this case (I mean, the exceptions get thrown allthe time). But it's certainly not worth my time to re-implement it given the almost immeasurable performance difference.

我还没有疯狂的决定使用例外在这种情况下，流量控制（我的意思是，异常抛出所有的时间）。但是考虑到几乎不可估量的性能差异，我肯定不值得花时间重新实现它。

If your condition that triggers death of the iteration is not a fundamental part of the algorithm, using an exception may make your code a lot cleaner. For me, the point where I'd make this decision is if the entire recursion needs to be unwound, then I'd use an exception. IF only part of the recursion needs to be unwound, use a magic return value.

如果触发迭代终止的条件不是算法的基本部分，则使用异常可能会使您的代码更清晰。对我来说，我做出这个决定的重点是，如果整个递归需要展开，那么我会使用异常。如果只有部分递归需要展开，请使用魔术返回值。

回答by Emre

What you are asking is the definition of recursion.

你问的是递归的定义。

At some point all recursive paths should break. Otherwise it will be an infinite recursion and stack overflow exceptionoccurs.

在某些时候，所有递归路径都应该中断。否则会无限递归，发生堆栈溢出异常。

So you should designthe recursion function like that. An example binary search in a sorted array:

所以你应该这样设计递归函数。排序数组中的二分搜索示例：

BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + ((high - low) / 2)  // Note: not (low + high) / 2 !!
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
}

回答by Andreas Dolk

I'd recommend an exception handling. That makes clear, that the recursion was aborted because of some violation (or other exception):

我建议使用异常处理。这清楚地表明，由于某些违规（或其他异常），递归被中止：

public void outer() {
  try {
    int i = recurse(0);
  } catch (OuchException ouch) {
    // handle the exception here
  }
}

private int recurse(int i) throws OuchException {

    // for tree-like structures
    if (thisIsALeaf) {
       return i;
    }

    // the violation test
    if (itHurts)
       throw new OuchException("That really hurts");

    // we also can encapsulate other exceptions
    try {
       someMethod();
    } catch (Exception oops) {
       throw new OuchException(oops);
    }

    // recurse
    return recurse(i++);
}

Sure, it violates the initial requirement to return 'true' upon abortion. But I prefer a clean separation of return values and notification on abnormal behaviour.

当然，它违反了在流产时返回 'true' 的初始要求。但我更喜欢明确分离返回值和异常行为通知。

回答by roho

I was able to move out of all recursive calls using a global variable.

我能够使用全局变量退出所有递归调用。

boolean skipRecursivePaths = false;
private callAgain(){

if(callAgain){
  if(getOutCompletely){

    skipRecursivePaths = true;
    }
    if(skipRecursivePaths){
    return;
    }
}

回答by samdoj

The best way to get out of a recursive loop when an error is encountered is to throw a runtime exception.

遇到错误时退出递归循环的最佳方法是抛出运行时异常。

throw new RuntimeException("Help!  Somebody debug me!  I'm crashing!");

Of course, this kills your program, but you should employ range checking and algorithm analysis to make sure your recursion does not throw such an exception. One reason you might want to break out of a recursive algorithm is that you are running low on memory. Here, it is possible to determine how much memory your algorithm will use on the stack. If you are coding Java, say, compare that calculation to

当然，这会杀死你的程序，但你应该使用范围检查和算法分析来确保你的递归不会抛出这样的异常。您可能想要摆脱递归算法的一个原因是您的内存不足。在这里，可以确定您的算法将在堆栈上使用多少内存。如果您正在编写 Java，例如，将该计算与

getMemoryInfo.availMem().

Let's say you are using recursion to find n!. Your function looks something like this:

假设您正在使用递归来查找 n!。您的函数如下所示：

public long fact(int n)
{
    long val = 1;
    for (int i  = 1, i<=n,i++)
        return val *= fact(i);
    return val;
}

Before you run it, check that you have (number of bytes in a long, 8 in Java) * n bytes in memory to hold the whole stack. Basically, with range and error checking in advance of the recursive method/function, you shouldn't need to break out. Depending on your algorithm, however, you may need to signal to the whole stack that you're good to go. If that's the case, Tom's answer works.

在运行它之前，请检查您是否有（long 中的字节数，Java 中的 8 个）* n 字节的内存来保存整个堆栈。基本上，在递归方法/函数之前进行范围和错误检查，您不需要中断。但是，根据您的算法，您可能需要向整个堆栈发出信号，表示您可以开始了。如果是这种情况，汤姆的回答有效。

回答by itb

better to have a Boolean array

最好有一个布尔数组

that way there is no global state

这样就没有全局状态

if(stop[0]) return;