调试递归算法 [英] Debugging of a recursive algorithm

问题描述

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

My question is if there are some smart ways of debugging complicated recursive algorithms. Assume that we have a complicated one (not a simple case when recursion counter is decreased in each 'nested iteration').

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

I mean something like recursive traversing of a graph when loops are possible.

我需要检查一下我没有得到无尽的循环。使用调试器来做这件事并不能给出肯定的答案（因为我不确定算法是在无限循环中还是只是处理它）。

I need to check if I am not getting endless loop somewhere. And doing this just using a debugger gives not certain answer (because I am not sure if an algorithm is in endless loop or just process as it should).

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

It's hard to explain it without concrete example. But what I need is...

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

'to check if the endless loops don't occur in let's say complicated recursive algorithm'.

推荐答案

您需要形成一个理论，说明您认为算法终止的原因。理想情况下，将该理论证明为数学定理。

You need to form a theory for why you think the algorithm does terminate. Ideally, prove the theory as a mathematical theorem.

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

You can look for a function of the problem state that does reduce on each recursive call. For example, see the following discussion of Ackermann's function, from Wikipedia

A（m，n）的评估总是会终止，这可能不是很明显。然而，递归是有界的，因为在每个递归应用中，m减小，或m保持相同并且n减小。每当n达到零时，m减小，因此m最终也达到零。 （从技术上讲，在每种情况下，对（m，n）在对上的字典顺序中减少，这是一个良好的排序，就像单个非负整数的排序一样;这意味着一个不能在排序中下降无数次连续。）然而，当m减少时，n可以增加多少没有上限 - 并且它通常会大大增加。

It may not be immediately obvious that the evaluation of A(m, n) always terminates. However, the recursion is bounded because in each recursive application either m decreases, or m remains the same and n decreases. Each time that n reaches zero, m decreases, so m eventually reaches zero as well. (Expressed more technically, in each case the pair (m, n) decreases in the lexicographic order on pairs, which is a well-ordering, just like the ordering of single non-negative integers; this means one cannot go down in the ordering infinitely many times in succession.) However, when m decreases there is no upper bound on how much n can increase — and it will often increase greatly.

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

That is the type of reasoning you should be thinking of applying to your algorithm.

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

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.

这篇关于调试递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！