递归算法的调试

Question

我的问题是，是否有一些调试复杂递归算法的聪明方法。假设我们有一个复杂的例子(当递归计数器在每个“嵌套迭代”中减少时，不是一个简单的例子)。

我的意思是，当循环是可能的时候，就像递归遍历图形一样。

我需要检查一下我是否在某个地方得到了无尽的循环。而仅仅使用调试器这样做并不能给出确定的答案(因为我不确定算法是在无限循环中还是像它应该的那样只是在处理)。

没有具体的例子很难解释它。但我需要的是...

“为了检查在复杂的递归算法中是否没有出现无尽的循环”。

Answer 1

你需要形成一个理论来解释为什么你认为算法确实会终止。理想情况下，将理论证明为数学定理。

您可以查找问题状态的函数，该函数在每次递归调用时都会减少。例如，请参阅Wikipedia中关于阿克曼函数的以下讨论

A(m，n)的求值总是终止，这一点可能不会立即明显。然而，递归是有界的，因为在每个递归应用程序中，要么m减少，要么m保持不变而n减少。每次n达到零时，m就会减少，所以m最终也会变成零。(从技术上讲，在每种情况下，成对的(m，n)按字典顺序递减，这是一种良好的排序，就像单个非负整数的排序一样；这意味着一个人不能在排序中连续无限次下降。)然而，当m减少时，n可以增加多少没有上限-它通常会大大增加。

这就是你应该考虑应用于你的算法的推理类型。

如果您找不到任何方法来证明算法的终止性，请考虑寻找一种可以证明其终止性的变体。并不总是可以决定一个任意的程序是否终止。诀窍是编写可以证明其可终止性的算法。

Answer 2

最好的方法是通过前置条件和后置条件、变量和不变量来证明有限性。如果您可以指定一个(虚拟)公式，该公式的值在每次调用时都会增加，那么您就有了保证。

这与证明循环是有限的是相同的。此外，它可能会使复杂的算法更容易处理。

Answer 3

你需要计算递归调用的深度...然后，如果递归调用的深度达到某个阈值，则抛出异常。

例如：

void TheMethod(object[] otherParameters, int recursiveCallDepth)
{
   if (recursiveCallDepth > 100) { 
      throw new Exception("...."); }
   TheMethod(otherParameters, ++recursiveCallDepth);
}