Recursion

Calling a method recursively or implementing the method using recursion refers to use of a method that calls itself. Recursion is sometimes the simplest way to implement a particular algorithm. Listing 5.22 counts the lines of all the C# source files (*.cs) in a directory and its subdirectory.

Listing 5.22: Counting the Lines within *.cs Files, Given a Directory
1. using System.IO;
2.  
3. public static class LineCounter
4. {
5.     // Use the first argument as the directory
6.     // to search, or default to the current directory
7.     public static void Main(string[] args)
8.     {
9.         int totalLineCount = 0;
10.         string directory;
11.         if(args.Length > 0)
12.         {
13.             directory = args[0];
14.         }
15.         else
16.         {
17.             directory = Directory.GetCurrentDirectory();
18.         }
19.         totalLineCount = DirectoryCountLines(directory);
20.         Console.WriteLine(totalLineCount);
21.     }
22.  
23.     static int DirectoryCountLines(string directory)
24.     {
25.         int lineCount = 0;
26.         foreach(string file in
27.             Directory.GetFiles(directory, "*.cs"))
28.         {
29.             lineCount += CountLines(file);
30.         }
31.  
32.         foreach(string subdirectory in
33.             Directory.GetDirectories(directory))
34.         {
35.             lineCount += DirectoryCountLines(subdirectory);
36.         }
37.  
38.         return lineCount;
39.     }
40.  
41.     private static int CountLines(string file)
42.     {
43.         string? line;
44.         int lineCount = 0;
45.         // This can be improved with a using statement
46.         // which is not yet described.
47.         FileStream stream = new(file, FileMode.Open);
48.         StreamReader reader = new(stream);
49.         line = reader.ReadLine();
50.  
51.         while(line != null)
52.         {
53.             if(line.Trim() != "")
54.             {
55.                 lineCount++;
56.             }
57.             line = reader.ReadLine();
58.         }
59.  
60.         reader.Dispose();  // Automatically closes the stream
61.         return lineCount;
62.     }
63. }

Output 5.8 shows the results of Listing 5.22.

Output 5.8
104

The program begins by passing the first command-line argument to DirectoryCountLines() or by using the current directory if no argument is provided. This method first iterates through all the files in the current directory and totals the source code lines for each file. After processing each file in the directory, the code processes each subdirectory by passing the subdirectory back into the DirectoryCountLines() method, rerunning the method using the subdirectory. The same process is repeated recursively through each subdirectory until no more directories remain to process.

Readers unfamiliar with recursion may find it confusing at first. Regardless, it is often the simplest pattern to code, especially with hierarchical type data such as the filesystem. However, although it may be the most readable approach, it is generally not the fastest implementation. If performance becomes an issue, developers should seek an alternative solution to a recursive implementation. The choice generally hinges on balancing readability with performance.

Beginner Topic
Infinite Recursion Error

A common programming error in recursive method implementations appears in the form of a stack overflow during program execution. This usually happens because of infinite recursion, in which the method continually calls back on itself, never reaching a point that triggers the end of the recursion. It is a good practice for programmers to review any method that uses recursion and to verify that the recursion calls are finite.

A common pattern for recursion using pseudocode is as follows:

M(x)

{

   if x is trivial

     return the result

   else

     a. Do some work to make the problem smaller

     b. Recursively call M to solve the smaller problem

     c. Compute the result based on a and b

     return the result

}

Things go wrong when this pattern is not followed. For example, if you don’t make the problem smaller or if you don’t handle all possible “smallest” cases, the recursion never terminates.

{{ snackbarMessage }}
;