Debugging of a recursive algorithm

Question

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'.

Answer 1

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

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

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.