Recursion is one of the most elegant tools in programming: a function that calls itself to solve progressively smaller instances of a problem. For traversing tree structures — such as the filesystem, category trees or XML structures — it’s often the most natural and efficient solution. This article explains the concept and illustrates it with a concrete example in C#.

How Recursion Works

The underlying idea is simple: a function receives a node as a parameter, processes it, and calls itself as many times as there are child branches of the current node. The successive calls terminate when the “leaf” nodes are reached — those without children.

Without a well-defined exit condition, recursion generates an infinite loop that leads to a stack overflow. The function must therefore call itself only if there is still data to process.

Advantages and Limitations

• Main advantage: compact, expressive code for navigating hierarchical structures of arbitrary depth.
• Limitation 1: without correct management of the exit condition, it generates infinite loops.
• Limitation 2: each call adds a frame to the stack. On very deep structures, stack overflow is possible even with correct logic.
• Best practice: minimise the data passed as parameters — it’s better to pass references or indices than to copy entire objects.

Example: Recursive Filesystem Scan in C#

The example implements a recursive scan of filesystem folders. The ReadFolderFiles function receives a folder, traverses it, and for each subfolder found calls itself again with the subfolder as the new parameter. The algorithm terminates when there are no more subfolders to visit.

using System;
using System.IO;

namespace RecursionOnFS
{
    class Class1
    {
        [STAThread]
        static void Main(string[] args)
        {
            DirectoryInfo d = new DirectoryInfo(@"C:StartingDirectory");
            ReadFolderFiles(d);
        }

        static void ReadFolderFiles(DirectoryInfo pDir)
        {
            DirectoryInfo[] subd = pDir.GetDirectories();
            foreach (DirectoryInfo dd in subd)
            {
                if (dd.Attributes == FileAttributes.Directory)
                {
                    // Recursive call: descend into the subfolder
                    ReadFolderFiles(dd);
                }
                else
                {
                    Console.WriteLine(dd.FullName);
                }
            }
        }
    }
}

The same pattern applies to any hierarchical structure: category trees in a database, XML nodes, nested JSON structures, or acyclic graphs. The key is always the same — identify the exit condition and reduce the problem at each iteration.

Article originally published on itvirtualcommunity.net (2004), rewritten and updated in 2012.