Tracking the progress of a recursive method

Question

I'm writing an application that makes use of a tree structure, so of course I have some recursive methods that will iterate down every node of the tree and do something. The problem is sometimes these take a while, and I'd rather show a progress bar of some sort to the user rather then the program stop responding for a period of time.

If I'm iterating through a flat list I know how many items are in the list to begin with so it's easy to keep track of what number the loop is at and update a progress bar accordingly.

But with a recursive method iterating a tree structure I don't necessarily know how many nodes the tree has at the beginning. Should I first recursively read through the tree and just count all the nodes before running the actual recursive method that does whatever I want to do? Or maybe just keep track of a running total as nodes are added or removed from the tree? Is there a better option?

Answer 1

A common approach to this problem is to show a progress bar that is changing, but not updating an actual percentage. For example, the little loading icon in Firefox is a circle-thing that is just spinning -- you know it's doing something, but you don't know how long it's going to take. Maybe just do that and add a message that "this might take a moment depending on how much data there is..."

Answer 2

A good progressbar would be based on the number of nodes in total (by doing a recursive count). An annoying but perhaps more efficient progressbar wouldbe the one that increases the MaxValue with every step of the recursion (making your progress steps tinier as you go). These methods could be combined by making a rough estimate before you start your method and update it as you go.

A Microsoft approach I guess would be to use the running-from-start-to-end-in-a-loop progressbar.

Answer 3

You can do several things. You could adjust the data structure such that each node stores the size of the tree rooted at that node. Other than that:

• If the trees are generally big, then a separate run just to determine the tree size may not be such a good idea in terms of performance (esp. if the tree doesn't completely fit in the cache).

• If the trees are generally quite balanced, then after processing the kth subtree of a total of n subtrees, you have traversed approximately k/n*100 percent of the nodes. You can use this knowledge as a measure of progress.

Answer 4

What about using a status label that shows where you are at by some descriptor that would make sense to the useras the loop is being executed...

For example, if I were looping through an org chart, I'd know that my end users are familiar with most of the people on the org chart, so I would use the people's names. As an example, if I report to Bob, who reports to Joe, who reports to Sue, when my record was being processed, the label would say something like..

Currently processing Sue\Joe\Bob\David

So you update the status label's text on each node. Just be sure that you call Application.DoEvents() after changing the label's text so that the screen updates. If you really want to display how far along you are, a progress bar would be better, but this is an option that's worked for me in similar situations. It gives some feedback as to what's happening, and the user experience is what really counts.

One caveat, however, is that updating the label text and calling Application.DoEvents() actually slows down processing, but it pays off usually because the users can see what's happening and know that the program isn't just "froze".