Recursion – first visit

Now we have the basic workings of the TreeView and TreeNode objects sorted out we can move on to write the recursive algorithm that “walks” its way down the tree from the root – if you want to think of it as walking up the tree from its root you can.

Recursion is often a lot easier to work with if you use the strategy of imagining  that you have already solved all of the problems. If we could wave a magic wand what we would create is a function that given a directory specification returns the amount of storage used by all the files and sub-directories it contains. That is, suppose we have a function like:

subTree(TreeNode)

which returns the total storage, a long integer, used by all of the directories starting at TreeNode and working down the hierarchy, then we would write the Analyze button click event handler with no real difficulties as:

private void button1_Click(
           object sender, EventArgs e)
{

First get the path to the root directory:

 string RootDir = drvCombo1.Text;

Next create a new TreeNode object to store the details of the directory within the hierarchy that we are about to build up:

 TreeNode Root = new TreeNode();

The Tag property is now used to store a DirectoryInfo object which represents the root directory:

 Root.Tag = new DirectoryInfo(RootDir);

The new TreeNode is now added to the TreeView control to act as the root of the tree structure we are about to build up:

 treeView1.Nodes.Add(Root);

Now we simply call our subTree function to get the total storage used by everything from and below the root directory:

 long total = subTree(Root);

Finally we set the text property of the Root node to indicate the total amount of storage used on the disk:

 Root.Text = total.ToString();
}

That’s it – job done! Of course it isn’t as we don’t actually have a function called subTree and creating one is our next task.

Recursion - second visit

Recursive algorithms are often developed by assuming that you have a function that does everything you want and then moving on to create it. The recursion comes about by using the function, again as if it already existed, within its own definition. I agree it sounds an unlikely method but, as you will see it does work.

The function starts off in a standard fashion and its first task is to discover how much storage is used by all of the files stored in the current directory:

private long subTree(
              TreeNode currentNode)
{

We first get the DirectoryInfo object stored in the currenNode and set the Text property to display its name:

 DirectoryInfo currentDir =
       (DirectoryInfo)currentNode.Tag;
 currentNode.Text = currentDir.Name+" ";

Using this we create an array of FileInfo objects representing all of the files stored in the directory:

 FileInfo[] File =currentDir.GetFiles();

One we have this array a simple foreach loop sums the file sizes in bytes:

 long total = 0;
 foreach (FileInfo f in Files)
 { 
  total += f.Length; 
 }

Now we have the space the files take we need the space used by each of the subdirectories and we proceed in a very similar way to processing the files. First we get an array of directories stored in the current directory:

 DirectoryInfo[] Dirs =
     currentDir.GetDirectories();

Each one of these subdirectories has to be added to the Nodes collection of the currentNode and to do this we need a temporary variable and a foreach loop:

 TreeNode node;
 foreach (DirectoryInfo Dir in Dirs)
 {

Creating the Treenode for each directory proceeds as for the original root directory -we set the Tag property to the DirectoryInfo object and add it to the current node:

  node = new TreeNode();
  node.Tag = Dir;
  currentNode.Nodes.Add(node);

To let the user see the node being added, so they can track the progress of the analysis, we also expand the node and to keep the application responsive we yield control and let the system process any pending events:

 currentNode.ExpandAll();
 Application.DoEvents();

Now we come to the part that many find mysterious. We need to work out the total amount of space used by the current subdirectory. How can we do that? Well it is just a matter of using the subTree function again:

 total += subTree(node);
}

Notice the use of the C# += operator, which adds the value returned by subTree to the running total. Once the foreach loop completes the running total is the total storage used by the current directory and all of the directories below it. This is our final result for this directory and we can add it to its TreeNode’s text property:

 currentNode.Text =
   currentNode.Text + total.ToString();

Finally we return the result as the value of the function:

 return total;
}

That’s all we need to do and now everything is complete.

If you run the program you will see a directory hierarchy build up one directory at a time.

Part of the directory hierarchy

How it works

You might be feeling a little cheated, or even bewildered, at how the program works. The answer is all about understanding that when you call a function a complete new copy is created before it starts working. So when subTree calls itself, it isn’t really calling itself, it’s calling another fresh copy of itself. In this way a call chain of copies of subTree is created and sooner or later a copy is created that doesn’t have any sub-directories to process. This final copy simply counts the space used by the files and returns this as its result. This, and other results of the finished subTree functions, slowly propagates back up the call chain until we reach the first copy, which returns the final answer to the program that started it all off.

<ASIN:0596519222>

<ASIN:0321524039>

<ASIN:0470191376>