在Java中跳出递归

Question

递归有一种“分而治之”的风格，它会在变小的同时进行拆分 (树形数据结构)，如果发现了违规情况，我希望它能完全中断，也就是中断所有递归路径，并返回 true。这种做法可行吗？

- Stasis

---

@Stasis：你所说的“所有递归路径”是什么意思？这似乎说明你没有理解递归的工作原理。请注意，如果您正在递归遍历树形结构，则不会同时探索树的分支...您是一次探索一个节点。因此，像Tom的答案那样做就可以了。如果您以某种方式使用多个线程来处理不同的分支，则需要保留一些全局状态，但我认为这不是您想要的。我们喜欢将递归视为探索许多路径，但请理解这并不是同时发生的。 - Tom

为了澄清，我在上面写的评论是指另一个发表答案的Tom。 - Tom

是的，但我最初想到的是终止这个递归“分支”，缺乏更好的词语，而不是去终止其他的，只是假装它没有发生，并返回false，而不是整数；或类似的东西。 - Stasis

停滞问题的重点是：你的“分支”是否是单独的线程，还是你正在运行单线程递归算法？ - DJClayworth

Answer 1

无论你做什么，你都需要解开堆栈。这留下了两个选择：

1. 魔术返回值（如 Toms 中的描述）
2. 抛出异常（如 thaggie 所述）

如果需要让事情死亡的情况很少见，那么抛出异常可能是可行的选择之一。在每个人都对此进行批判之前，请记住编程中最重要的规则之一是知道何时打破规则。

事实证明，我今天评估了来自 Google Code 的 zxing 库。他们实际上使用异常抛出来控制大量结构。当我看到它时，我的第一反应是恐惧。他们实际上在以不同的参数调用方法数以万计，直到该方法不抛出异常为止。

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

我仍然不太喜欢在这种情况下使用异常来进行流程控制（我的意思是，异常总是被抛出）。但是，考虑到几乎无法测量的性能差异，重新实现它并不值得我花时间。

如果触发迭代死亡的条件不是算法的基本部分，则使用异常可能会使代码更加清晰。对于我来说，做出这个决定的关键在于整个递归是否需要解开，如果是，则使用异常。如果只有部分递归需要解开，则使用魔术返回值。

- Kevin Day

---

OP写道：“如果发现违规行为，我希望它完全中断”，这听起来像是一个“异常情况”，而这正是异常处理的用途。 - DJClayworth

如果一个方法的契约是“返回此行中找到的条形码”，那么当没有找到时，你希望它返回什么？'null' 是逃避责任的做法，因为它什么都不返回。抛出异常是合适的。但你的论点是性能。另一位作者最初对此向我提出了质疑。如果你深入代码，就会发现我们使用一个单例异常来解决性能问题。 - Sean Owen

我总是从一个前提出发，即在异常情况下的性能并不重要。如果分析表明相反，我会改变我的想法。 - DJClayworth

@SeanOwen 刚刚注意到你的回复 - 这可能不是讨论设计的最佳场所，但一个不错的方法是让方法返回一个 BarCodeScanResult 对象，该对象本身具有 foundBarcode() 方法（如果为 true，则还调用 getResult() ）。完全同意返回 null 是个坏主意。BarCodeScanResult 的优点在于它可以包含其他信息（例如部分条形码只是碰巧未通过校验和等等）。 - Kevin Day

使用异常的另一个显著原因是能够直接从许多深度嵌套的方法中失败扫描。你的方法需要实现成百上千个自定义类，而异常可以直接将控制权抛到顶部而不需要 thunking。在这种情况下，它实际上更快。 - Sean Owen

Answer 2

你可以返回一个错误代码，或修改一些全局变量，使每个递归实例都知道要“自杀”。类似这样的操作。

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
}

- Tom

---

嗯，谢谢。我也想到了这个方法，但是我想知道是否有一种方法可以只终止所有递归步骤，但我会采用这种方法。 - Stasis

@Stasis：你总是需要用递归回溯，这就是它的工作原理。递归通过使用内存的栈区域来实现...你需要回溯函数调用以恢复最初递归的位置继续执行。这是递归的本质/魔力。看起来你可能需要更好地理解递归。 - Tom

@Tom：（指上面三个帖子的Tom...不是我，上一个帖子）......这是一种极其粗糙的优化，尤其在Java中根本不值得考虑。如果你真的无法承受开销，那么可以使用堆栈在循环中自己实现“递归”。此外，如果Java可以做到这一点，那么它可能是通过内置的内存管理类之一来实现的，但是使用这些类可能会增加开销。我永远不会建议在任何高级编程语言中这样做。不要养成思考这种不良的过早优化习惯。呕吐 :-P。 - Tom

嗨，回答这个问题的Tom...你觉得SO应该实现一个数字系统，在发帖时将ID附加到重复的用户名中吗？因此，如果我先发布，我的名字就是Tom。然后你发布，我的名字突然出现在所有地方，变成了Tom（1），而你会出现为Tom（2）...这样的东西会让事情变得不那么混乱...如果你认为这个想法不错，也许我可以提出一个功能请求。 - Tom

是的，这是首选的方式！谢谢。 - David H.

Answer 3

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

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

当然，这违反了在中止操作时返回“true”的初始要求。但我更喜欢在返回值和异常行为通知方面进行清晰的分离。

- Andreas Dolk

Answer 4

如果是单个线程递归，您可以抛出异常。 但这样有些丑陋 - 类似于将异常用作goto。

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

更好的方法是消除递归，使用一个堆栈集合来保存代表原先递归状态的类，通过循环迭代，只有当需要时才返回 true。

- Tom

Answer 5

你所询问的是递归的定义。

在某个时刻，所有递归路径都应该停止。否则就会出现无限递归，导致堆栈溢出异常。

因此，你应该像这样设计递归函数。一个例子是在排序数组中进行二分查找：

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
}

- Emre Köse

Answer 6

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

- Joe Phillips

Answer 7

当遇到错误时，从递归循环中跳出的最佳方法是抛出运行时异常。

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

当然，这会终止您的程序，但您应该使用范围检查和算法分析来确保您的递归不会抛出此类异常。您可能想要退出递归算法的一个原因是内存不足。在这种情况下，可以确定算法在堆栈上将使用多少内存。如果您正在编写Java代码，请将该计算与之进行比较。

getMemoryInfo.availMem().

假设您正在使用递归来查找n！。 您的函数看起来像这样：

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

在运行之前，请确保您有足够的内存来容纳整个堆栈（在Java中，长整型所占的字节数为8）* n字节。基本上，在递归方法/函数之前进行范围和错误检查，您就不需要退出了。但是，根据您的算法，您可能需要向整个堆栈发出信号，表明您已准备好开始执行。如果是这种情况，Tom的答案适用。

- samdoj

Answer 8

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

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

- Greg Case

Answer 9

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

boolean skipRecursivePaths = false;
private callAgain(){

if(callAgain){
  if(getOutCompletely){

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

- roho

Answer 10

也许你想避免递归并用堆栈替换它。这使您能够控制退出操作，同时能够执行类似于递归操作的操作。实际上，您只需自己模拟递归。

我在这里找到了一个不错的解释：http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx/

- murphy