递归有一种“分而治之”的风格,它会在变小的同时进行拆分 (树形数据结构),如果发现了违规情况,我希望它能完全中断,也就是中断所有递归路径,并返回 true。这种做法可行吗?
递归有一种“分而治之”的风格,它会在变小的同时进行拆分 (树形数据结构),如果发现了违规情况,我希望它能完全中断,也就是中断所有递归路径,并返回 true。这种做法可行吗?
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
}
我建议使用异常处理。这可以清楚地表明,递归是因为某些违规(或其他异常)而被中止:
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”的初始要求。但我更喜欢在返回值和异常行为通知方面进行清晰的分离。
如果是单个线程递归,您可以抛出异常。 但这样有些丑陋 - 类似于将异常用作goto。
boolean myPublicWrapperMethod(...) {
try {
return myPrivateRecursiveFunction(...);
} catch (MySpecificException e) {
return true;
}
}
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
}
你可以通过存储一个变量来跟踪递归是否应该中断来实现类似的操作。不幸的是,你必须在每次递归时检查它,但你可以做到。
当遇到错误时,从递归循环中跳出的最佳方法是抛出运行时异常。
throw new RuntimeException("Help! Somebody debug me! I'm crashing!");
getMemoryInfo.availMem().
public long fact(int n)
{
long val = 1;
for (int i = 1, i<=n,i++)
return val *= fact(i);
return val;
}
除非递归调用正在并行评估,否则您可能只需要添加一些逻辑来在进行第二个(以及后续的,如果不是二叉树结构)递归调用之前检查第一个递归调用的值。
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();
}
}
boolean skipRecursivePaths = false;
private callAgain(){
if(callAgain){
if(getOutCompletely){
skipRecursivePaths = true;
}
if(skipRecursivePaths){
return;
}
}
也许你想避免递归并用堆栈替换它。这使您能够控制退出操作,同时能够执行类似于递归操作的操作。实际上,您只需自己模拟递归。
我在这里找到了一个不错的解释:http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx/