How to debug a recursive algorithm?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

Thread: How to debug a recursive algorithm?

  1. #1
    Join Date
    Jul 2005
    Posts
    894

    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. #2
    Join Date
    Feb 2002
    Posts
    4,640

    Re: How to debug a recursive algorithm?

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

    Viggy

  3. #3
    Join Date
    Oct 2008
    Posts
    1,077

    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. #4
    Join Date
    Jul 2005
    Posts
    894

    Re: How to debug a recursive algorithm?

    Quote Originally Posted by superbonzo View Post
    ... 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. #5
    Join Date
    Oct 2008
    Posts
    1,077

    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. #6
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,000

    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.
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  7. #7
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,000

    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
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #8
    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. #9
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,000

    Re: How to debug a recursive algorithm?

    Quote Originally Posted by latisha11 View Post
    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
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

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


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center