Website development and design blog, tutorials and inspiration

Using Recursion in C#

Shooting yourself in the foot, over and over again

By , 10th November 2007 in C#

Recursion is the process whereby a method calls itself until an exit condition is met. Very useful, but also very easy to shoot yourself in the foot over and over and over again.
 

Recursion is used where a method processes items and calls itself repeatedly to process further items it finds. An example would be a directory tree listing. It first scans the root of the C: drive then calls itself for each directory found. If a subdirectory also contains directories another call to itself is made.

Recursion is also used in mathematics and scientific programming, node programming, artificial intelligence and some database applications.

Recursion is a good way of reusing code and processing multiple levels of data, however, it is very easy for the system to run away. You also need to pass data to the method that can get memory intensive. It will also have an impact on performance.

The following code sample illustrates a recursive method for listing a directory structure.

  1. using System;
  2. using System.Threading;
  3. using System.Text;
  4. using System.IO;
  5.  
  6. class Program
  7. {
  8. static void Main()
  9. {
  10. StringBuilder dirList = new StringBuilder();
  11.  
  12. dirList = directoryListing("c:/Inetpub", "");
  13. Console.WriteLine(dirList.ToString());
  14. }
  15.  
  16. static StringBuilder directoryListing(string path, string indent)
  17. {
  18. StringBuilder result = new StringBuilder();
  19. DirectoryInfo di = new DirectoryInfo(path);
  20. DirectoryInfo[] directories = di.GetDirectories();
  21.  
  22. foreach (DirectoryInfo dir in directories)
  23. {
  24. result.AppendLine(indent + dir.Name);
  25.  
  26. // Call the method again on the directories found
  27. result.Append(directoryListing(dir.FullName, indent + "..").ToString());
  28. }
  29. return result;
  30. }
  31. }

This routine will scan through the directory specified in the Main method, grab all the sub directories within that directory, add them to the result, and then call itself on each of the subdirectories found. It will recurse until a folder has no subdirectories. Finally, it returns the result back to the line that called the recursive method, until there are no more recursions to be processed. The result is then handed back to the Main method call.

Each time the recursive method is called you need to tell it where to start from, in this case, the folder to look in. In this example, I also use a parameter for the indent level. Each recursion adds two dots to the previous indent level so you can see the directory structure clearer.

It is very easy for a recursive method to run away with itself, an invalid parameter or start point will cause the method to call itself over and over again and never progress. In this case, you will eventually receive a StackOverflowException, which should be handled with a try catch block on the first call of the method.

Comments
  1. Gisle Aune
    Gisle Aune

    Isn't a for loop more effective when adressing each object in a collection? Like this?

    DirectoryInfo dir = null;
    for(int i = 0; int i < directories.length; i += 1)
    {
    dir = directories[i]
    result.AppendLine(indent + dir.Name);

    // Call the method again on the directories found
    result.Append(directoryListing(dir.FullName, indent + "..").ToString());

    }

    1. Tim Trott
      Tim Trott

      Yes, you are absolutely correct. Performance wise a for loop is much faster to execute and should be used for performance critical applications. It wasn't until I did some investigation that I found out just how much faster a for loop was. Time to rethink my foreach use!

      Thanks

Leave a Reply

Your email address will not be published.