Tuesday 15 November 2011

The Yield and Recursion Statement in C#


Another often overlooked C# statement that was introduced in .NET 2.0 is yield. This keyword is used to return items from a loop within a method and retain the state of the method through multiple calls. That is a bit hard to wrap your head around, so as always, an example will help;

public static IEnumerable<int> Range( int min, int max )
{
   for ( int i = min; i < max; i++ )
   {
      yield return i;
   }
}

Each time Range is called, it will return one value in the given range. Of interest is that it maintains the state between calls. The best way to think of it is that for the first call to the method, execution starts at the first line and continues until it hits a yield statement at which time it returns the value. The subsequent runs through the method continue execution at the statement after the yield, continuing to yield values or exiting at the end of the method.
Using this, you can write the following code;

foreach ( int i in Range( 10, 20 ) )
{
   Console.Write( i.ToString() + " " );
}

Which will return the following;
10 11 12 13 14 15 16 17 18 19

The above example doesn’t really show you the power, so let’s try a more complex example, calculating prime numbers.

public static IEnumerable<int> Primes( int max )
{
   yield return 2;
   List<int> found = new List<int>();
   found.Add( 3 );
   int candidate = 3;
   while ( candidate <= max )
   {
      bool isPrime = true;
      foreach ( int prime in found )
      {
         if ( prime * prime > candidate )
         {
            break;
         }
         if ( candidate % prime == 0 )
         {
            isPrime = false;
            break;
         }
      }
      if ( isPrime )
      {
         found.Add( candidate );
         yield return candidate;
      }
      candidate += 2;
   }
}
Notice that there are multiple yields within this method and that the state is maintained through each call. You can now print out all of the prime numbers below 50 with;

foreach ( int prime in Primes( 50 ) )
{
   Console.Write( prime.ToString() + " " );
}

There is also the yield break statement. If a yield break statement is hit within a method, execution of that method stops with no return. Using this, the first method could be rewritten like this;

public static IEnumerable<int> Range( int min, int max )
{
   while ( true )
   {
      if ( min >= max )
      {
         yield break;
      }
      yield return min++;
   }
}

It is not as useful in this case, but I’ll leave it to you to find more interesting reasons to break out of a loop. Also, even though I used the generic IEnumerable<T> for all of my examples, you can also use IEnumerable.

What is recursion?
Basically, in simple terms, recursion is a function that calls itself iteratively until it reaches a stopping point. In another words, recursion is a common method of simplification to divide a problem into sub-problems of the same type. As a computer programming technique, this is called "divide and conquer" and is key to the design of many important algorithms particularly in Arterial Intelligence programming.
The file system is a very good example of recursive programming. Let us say we want to iterate through all the files in all the folders under C:\Program Files\Adobe\Acrobat 5.0 folder as in the above image, the following definition is correct:
ENU has some files and has a parent folder which is HELP. Similarly, HELP has some files and has a parent folder which is Acrobat 5.0 and so on until it reaches the target folder of C:\Program Files\Adobe\Acrobat 5.0. And it could be correct the other way around, i.e. C:\Program Files\Adobe\Acrobat 5.0 has some files and a child folder, Acrobat 5.0 has some files and a child folder until it reaches the final child ENU.
Therefore, if we write down the code to iterate though one of these folders and its files and call it repeatedly, then we have solved the problem. In other words, we are dividing the Bigger Problem of iterating through the Adobe folder to sub-problems which is just iterating through a single folder and calling it iteratively and the problem is resolved.

How recursion works?
Basically it is defining a problem in the form of itself and calling it repeatedly. However the important point to notice is that there should be a Stopping Point or 'End Condition'.

Advantages of recursion:
  • Game programming
  • Artificial Intelligence
  • Most of the mathematic functions can be presented in the form of recursion
  • For some problems, it very easy to understand them using recursion
Enough of the theory. Now let us have a look at some actual C# code.

namespace Recursion
{
    class IterateFolders
    {
       
        public    static void Main(string[] args)
        {
            //Create a Directory object using DirectoryInfo

            DirectoryInfo dir =
               new DirectoryInfo(@"C:\Program Files\Adobe\Acrobat 5.0");
            //Pass the Directory for displaying the contents

            getDirsFiles(dir);

        }

        //this is the recursive function

        public static void getDirsFiles(DirectoryInfo d)
        {
            //create an array of files using FileInfo object

            FileInfo [] files;
            //get all files for the current directory

            files = d.GetFiles("*.*");

            //iterate through the directory and print the files

            foreach (FileInfo file in files)
            {
                //get details of each file using file object

                String fileName = file.FullName;
                String fileSize = file.Length.ToString();
                String fileExtension =file.Extension;
                String fileCreated = file.LastWriteTime.ToString();

                io.WriteLine(fileName + " " + fileSize +
                   " " + fileExtension + " " + fileCreated);
            }
           
            //get sub-folders for the current directory

            DirectoryInfo [] dirs = d.GetDirectories("*.*");
           
            //This is the code that calls
            //the getDirsFiles (calls itself recursively)
            //This is also the stopping point
            //(End Condition) for this recursion function
            //as it loops through until
            //reaches the child folder and then stops.

            foreach (DirectoryInfo dir in dirs)
            {
                io.WriteLine("--------->> {0} ", dir.Name);
                getDirsFiles(dir);
            }
           
        }

    }
}


Posted By: Mr. Palash Paul

No comments:

Post a Comment