Practical tips debugging deep recursion?

Logging. Log in your code extensively. In my experience, logging is THE solution for these types of problems.

When it's hard to figure out what your code is doing, logging it extensively is a very good solution, as it lets you output from within your code what the internal state is; it's really not a perfect solution, but as far as I've seen, it works better than using any other method.

Maybe you could convert the recursion into an iteration with an explicit stack for the parameters. Testing is easier in this way because you can directly log values, access the stack and don't have to pass data/variables in each self-evaluation or prevent them from falling out of scope.

2 this is the sanity-preserving solution; it also removes the inherent limits of the recursive solution (assuming a dynamic structure to hold the parameter queue) – Steven A. Lowe May 11 '09 at 19:03.

I would normally unit-test such algorithms with one or more predefined datasets that have well-defined outcomes. I would typically make several such tests in increasing order of complexity. If you insist on debugging, it is sometimes useful to doctor the code with statements that check for a given value, so you can attach a breakpoint at that time and place in the code: if ( depth = X && item.Id = 32) { // Breakpoint here }.

1 Well, a unit test at this point would just tell me it doesn't work, which I already know :p – JulianR May 11 '09 at 18:36 It allows you to work with the problem in a more controlled manner, I also edited with a few more detailed suggestions. – krosenvold May 11 '09 at 18:38 and not just that, when using a unit test you can usually reproduce problems with a much simpler problem space, maybe only a depth of 2. Even though logging seems to be the preferred solution in this thread, it's not a very good solution - logging does not retain much useful information for the future.

When your test coverage is good, log coverage typically goes down dramatically. – krosenvold May 12 '09 at 5:03.

One thing I have done in the past is to format your logs to reflect the recursion depth. So you may do a new indention for every recurse, or another of some other delimiter. Then make a debug dll that logs everything you need to know about a each iteration.

Between the two, you should be able to read the execution path and hopefully tell whats wrong.

I once had a similar problem when I was developing an AI algorithm to play a Tetris game. After trying many things a loosing a LOT of hours in reading my own logs and debugging and stepping in and out of functions what worked out for me was to code a fast visualizer and test my code with FIXED input. So, if time is not a problem and you really want to understand what is going on, get a fixed board state and SEE what your program is doing with the data using a mix of debug logs/output and some sort of your own tools that shows information on each step.

Once you find a board state that gives you this problem, try to pin-point the function(s) where it starts and then you will be in a position to fix it.

I know what a pain this can be. At my job, we are currently working with a 3rd party application that basically behaves as a black box, so we have to devise some interesting debugging techniques to help us work around issues. When I was taking a compiler theory course in college, we used a software library to visualize our trees; this might help you as well, as it could help you see what the tree looks like.In fact, you could build yourself a WinForms/WPF application to dump the contents of your tree into a TreeView control--it's messy, but it'll get the job done.

You might want to consider some kind of debug output, too. I know you mentioned that your tree is large, but perhaps debug statements or breaks at key point during execution that you're having trouble visualizing would lend you a hand. Bear in mind, too, that intelligent debugging using Visual Studio can work wonders.

It's tough to see how state is changing across multiple breaks, but Visual Studio 2010 should actually help with this. Unfortunately, it's not particularly easy to help you debug without further information. Have you identified the first depth at which it starts to break?

Does it continue to break with higher search depths? You might want to evaluate your working cases and try to determine how it's different.

Since you say that the traversal is not working as expected, I assume you have some idea of where things may go wrong. Then inspect the code to verify that you have not overlooked something basic. After that I suggest you set up some simple unit tests.

If they pass, then keep adding tests until they fail. If they fail, then reduce the tests until they either pass or are as simple as they can be. That should help you pinpoint the problems.

If you want to debug as well, I suggest you employ conditional breakpoints. Visual Studio lets you modify breakpoints, so you can set conditions on when the breakpoint should be triggered. That can reduce the number of iterations you need to look at.

I would start by instrumenting the function(s). At each recursive call log the data structures and any other info that will be useful in helping you identify the problem. Print out the dump along with the source code then get away from the computer and have a nice paper-based debugging session over a cup of coffee.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.