java - 递归算法的调试

Question

我的问题是，是否有一些聪明的方法可以调试复杂的递归算法。假设我们有一个复杂的情况（不是递归计数器在每次“嵌套迭代”中减少的简单情况）。

我的意思是当循环可能时递归遍历图形。

我需要检查我是否在某处没有无限循环。仅使用调试器执行此操作并不能给出确定的答案（因为我不确定算法是否处于无限循环或只是按其应有的方式处理）。

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

'检查是否在复杂的递归算法中没有发生无限循环'。

Answer 1

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

您可以查找问题状态的函数，该函数在每次递归调用时都会减少。例如，参见以下关于 Ackermann 函数的讨论，来自Wikipedia

A(m, n) 的计算总是终止可能不是很明显。但是，递归是有界的，因为在每个递归应用程序中，要么 m 减少，要么 m 保持不变而 n 减少。每次 n 达到零时，m 都会减小，因此 m 最终也会达到零。（更专业地表达，在每种情况下，对 (m, n) 在对上按字典顺序递减，这是一个良好的排序，就像单个非负整数的排序一样；这意味着一个不能在排序中下降连续无限多次。）但是，当 m 减小时，n 可以增加多少没有上限——而且它通常会大大增加。

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

If you cannot find any way to prove your algorithm terminates, consider looking for a variation whose termination you can prove. It is not always possible to decide whether an arbitrary program terminates or not. The trick is to write algorithms you can prove terminate.

Answer 2

最好的方法是通过前后条件、变体和不变量来证明有限性。如果您可以指定一个（虚拟）公式，每次通话都会增加价值，那么您就有保证。

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

Answer 3

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

例如：

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

Answer 4

如果你想检查无限循环，

在调用递归函数的下一行写一个System.out.println("no its not endless");。

如果循环是无限的，则该语句将不会被打印，否则您将看到输出

Answer 5

一个建议如下：

如果您有无限循环，那么在图形情况下，您将获得一个顶点数大于图形中顶点总数的路径。假设图中的顶点数是一个全局变量（我认为这是最常见的情况），如果深度已经高于顶点总数，则可以在递归开始时设置条件断点。

这是一个如何在 Eclipse 中为 java 设置条件断点的链接。