打破java中的递归

Question

递归是一种"分而治之"的风格,它在变小(树数据结构)时分裂,我希望它在发现违规时完全破坏,意味着打破所有递归路径,并返回true.这可能吗？

Answer 1

无论你做什么,你都必须放松堆栈.这留下了两个选择:

1. 魔术回归值(由其中一个汤姆斯描述)
2. 抛出异常(如thaggie所述)

如果您希望死亡的情况很少,这可能是抛出异常可能是一个可行选择的情况之一.在每个人都对此嗤之以鼻之前,请记住,最重要的编程规则之一是知道何时违反规则.

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

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

我还没有疯狂到使用异常在这种情况下,流量控制的决定(我的意思是,异常抛出所有的时间).但鉴于几乎无法衡量的性能差异,重新实施它当然不值得我花时间.

如果触发迭代死亡的条件不是算法的基本部分,则使用异常可能会使代码更清晰.对我来说,我做出这个决定的地方是整个递归是否需要解开,然后我会使用异常.如果只需要解开部分递归,请使用魔术返回值.

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
}

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”的最初要求。但我更喜欢将返回值和异常行为通知完全分开。

Answer 4

如果它是执行递归的单个线程,则可能抛出异常.虽然有点难看 - 有点使用异常作为goto.

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

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