CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: How to debug a recursive algorithm?

1. Senior Member
Join Date
Jul 2005
Posts
1,030

## How to debug a recursive algorithm?

Any guru here can tell me what the best way to debug a recursive algorithm is? For example, the following is my code trying to merge sort an array, but it is somehow wrong. Do you know how to debug to find out where it went wrong? I am more interested in the approach to find out why. Thanks so much!

Code:
```void Merge(int a[], int l, int m, int r)
{
int i, j;
int b[100];
int k = l;

for(i=l, j=m+1;i<=m, j<=r;)
{
if(a[i] < a[j])
{
b[k++] = a[i++];
}
else
{
b[k++] = a[j++];
}
}

if(i>m)
{
while(j<=r)
{
b[k++] = a[j++];
}
}
else
{
while(i<=m)
{
b[k++] = a[i++];
}
}

for(i=l;i<=r;++i)
a[i] = b[i];
}

void MergeSort(int a[], int l, int r)
{
if(l>=r)
return;

int m = (l+r)/2;
MergeSort(a, l, m);
MergeSort(a, m+1, r);

Merge(a, l, m, r);
}

int main(int argc, char* argv[])
{
int a[] = {5, 1, 11, 7, 9, 14};

MergeSort(a, 0, 5);

return 0;
}```

2. ## Re: How to debug a recursive algorithm?

No different then debugging any other function. Step through the calls using your debugger.

Viggy

3. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: How to debug a recursive algorithm?

... and if you have problems following the debugger stack, you can setup an helper container ( to be used only for debugging purposes, of course ), something like

Code:
```void MergeSort(int a[], int l, int r)
{
static std::stack< std::pair<int,int> > step_stack;

step_stack.push( std::make_pair( l, r ) );

if(l>=r)
return;

int m = (l+r)/2;
MergeSort(a, l, m);
MergeSort(a, m+1, r);

Merge(a, l, m, r);

step_stack.pop();
}```
in this way, you can inspect the full function "state" without walking the debugger supplied function stack ...

4. Senior Member
Join Date
Jul 2005
Posts
1,030

## Re: How to debug a recursive algorithm?

Originally Posted by superbonzo
... and if you have problems following the debugger stack, you can setup an helper container ( to be used only for debugging purposes, of course ), something like

Code:
```void MergeSort(int a[], int l, int r)
{
static std::stack< std::pair<int,int> > step_stack;

step_stack.push( std::make_pair( l, r ) );

if(l>=r)
return;

int m = (l+r)/2;
MergeSort(a, l, m);
MergeSort(a, m+1, r);

Merge(a, l, m, r);

step_stack.pop();
}```
in this way, you can inspect the full function "state" without walking the debugger supplied function stack ...
Thanks for your suggestions. But I still don't understand how I can use these helper containers to dbug? Could you explain a little bit more? Thanks a lot.

5. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: How to debug a recursive algorithm?

first of all, I have not read your code, given that you said you are interested in "the approach to find out why" it's wrong.

now, I suppose you have problems with the recursive logic of your program, don't you ? because if you had issues with the non recursive part of your algorithm ( say, the Merge function ) then, as MrViggy suggested, it's the same as debugging any other function: simply put a breakpoint and check step by step if the algorithm does what you expects it to do.

otherwise, supposing you have problems with the recursive logic, you need to know when and how your recursive function is called; in my code snippet above, an empty static stack is constructed at the first MergeSort call, and at each call the relevant function arguments are pushed in and popped out before the function returns.

This means that the content of the step_stack variable ( that you can inspect interactively on most debuggers ) is the sequence of MergeSort arguments as they are called in your recursive function ( a "branch" of the recursion tree ), that you can check to see if your recursive logic is correct or not.

6. ## Re: How to debug a recursive algorithm?

Having spent some time writing in a language without access to a quality debugger, I would strongly advise you to use code review as your principle method of debugging. That is, read through the method and at every step rationalize why the algorithm does what it does at that step. Through this method, you can detect a large number of logic errors. Actually, this is good practice for ANY method (even non-recursive), but recursive methods are a bit trickier to interrogate with the debugger so code review is even more crucial.

If that fails though, there is the good ol' step-through-with-the-debugger as the others have pointed out.

7. ## Re: How to debug a recursive algorithm?

Oh, another trick is to add some statements that write to the console that tell you about the state of the function. Then you can make your own little callstack diagram on a piece of paper. While you could in principle do this stepping through with the debugger, sometimes it's easier to have a full record of what the program was doing in front of you while you build a diagram to help understand what's going on rather than trying to just keep it all in your head.

Sounds kind of... simple... but if that's useful, give it a go!
Last edited by BioPhysEngr; April 21st, 2011 at 02:59 AM. Reason: small edit

8. Junior Member
Join Date
Aug 2011
Posts
1

## Re: How to debug a recursive algorithm?

Please expand on this. What values are you giving them, and what are they returning?

9. ## Re: How to debug a recursive algorithm?

Originally Posted by latisha11
Please expand on this. What values are you giving them, and what are they returning?
Develop a simple test case (or, rather, several) that you know the return value. If all your test cases pass and you have done code review to try to detect more subtle bugs your cases might not have tested, then declare (at least temporary) victory. Otherwise, if it fails, try to figure out why your simple test is failing. Step through the code and the debugger and rationalize every choice made until the code demands the program do something different than what you'd expect.

Don't be afraid to test to make things you're already sure are going to work. If I had a nickle for every time I said 'well surely this will work...' and then identified the flaw as a result... well, I'd have quite a few nickles...
Last edited by BioPhysEngr; August 12th, 2011 at 04:42 AM. Reason: comma

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)

×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.