调试递归算法

Question

我的问题是,是否有一些智能的方法来调试复杂的递归算法.假设我们有一个复杂的(不是一个简单的情况,当递归计数器在每个'嵌套迭代中'减少').

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

我需要检查一下我是否没有得到无限循环.仅仅使用调试器来做这件事并没有给出肯定的答案(因为我不确定算法是在无限循环中还是只是应该处理).

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

'检查无限循环是否发生在让我们说复杂的递归算法'.

Answer 1

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

\n\n

您可以寻找问题状态的函数，该函数在每次递归调用时都会减少。例如，请参阅维基百科中对阿克曼函数的以下讨论

\n\n

\n

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

\n

\n\n

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

\n\n

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

\n