打破java中的递归
递归是一种“分而治之”的风格，它在变小时分裂（树数据结构），如果发现违规，我希望它完全破坏，意味着打破所有递归路径，并返回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 } 无论你做什么，你都必须放松堆栈。 这留下了两个选择：
- 魔术回归值（由其中一个汤姆斯描述）
- 抛出exception（如thaggie所述）
如果您希望死亡的情况很少，这可能是抛出exception可能是一个可行选择的情况之一。 在大家对此嗤之以鼻之前，请记住，最重要的编程规则之一是知道何时违反规则。
事实certificate，我今天花了从谷歌代码评估zxing库。 它们实际上对许多控制结构使用exception抛出。 当我看到它时，我的第一印象是恐怖。 他们实际上用不同的参数调用方法数万次，直到该方法不抛出exception。
这当然看起来像一个性能问题，所以我做了一些调整，将事情改为使用魔法返回值。 你知道吗？ 在调试器中运行时，代码速度提高了40％。 但是当我切换到非调试时，代码速度不到1％。
在这种情况下，我仍然不会为在流量控制中使用exception的决定而疯狂（我的意思是，exception会一直被抛出）。 但鉴于几乎无法衡量的性能差异，重新实施它当然不值得我花时间。
如果触发迭代死亡的条件不是算法的基本部分，则使用exception可能会使代码更清晰。 对我来说，我做出这个决定的地方是，如果需要解开整个递归，那么我会使用exception。 如果只需要解开部分递归，请使用魔术返回值。
如果它是执行递归的单个线程，则可以抛出exception。 虽然有点丑陋 – 有点使用exception作为goto。
boolean myPublicWrapperMethod(...) { try { return myPrivateRecursiveFunction(...); } catch (MySpecificException e) { return true; } }
一种更好的方法是消除递归并使用一个Stack集合，该集合包含一个表示递归状态的类，在循环中迭代并在需要时返回true。
我建议进行exception处理。 这清楚地表明，由于某些违规（或其他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++); }
当然，它违反了在堕胎时返回“真实”的初始要求。 但我更喜欢清楚地分离返回值和exception行为的通知。
您可以通过存储跟踪递归是否应该中断的变量来执行类似的操作。 不幸的是，你必须检查每次递归，但你可以做到。
你要问的是递归的定义。
在某些时候，所有递归路径都应该中断。 否则将发生无限递归并发生堆栈溢出exception 。
所以你应该设计这样的递归函数。 排序数组中的示例二进制搜索 ：
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 }
除非并行计算递归调用，否则您可能只需要添加一些逻辑来检查第一个递归调用的值，然后再进行第二次（以及后续的，如果不是二叉树结构）递归调用。
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/
遇到错误时退出递归循环的最佳方法是抛出运行时exception。
throw new RuntimeException("Help! Somebody debug me! I'm crashing!");
当然，这会杀死你的程序，但是你应该使用范围检查和算法分析来确保你的递归不会抛出这样的exception。 您可能想要打破递归算法的一个原因是您的内存不足。 在这里，可以确定算法将在堆栈上使用多少内存。 如果您正在编写Java，请将该计算与之比较
getMemoryInfo.availMem().
假设您正在使用递归来查找n！。 你的function看起来像这样：
public long fact(int n) { long val = 1; for (int i = 1, i<=n,i++) return val *= fact(i); return val; }
在运行它之前，请检查内存中是否有（长的8个字节的字节数）* n个字节来保存整个堆栈。 基本上，在递归方法/函数之前进行范围和错误检查，您不需要突破。 但是，根据您的算法，您可能需要向整个堆栈发出信号，表示您很高兴。 如果是这样的话，汤姆的回答是有效的。
最好有一个布尔数组
这样就没有全球状态了
if(stop[0]) return;