Learn Programming With C#

Recursion - say what?!

Here you are going to learn one of the most fundamental concepts of programming: recursion. Let’s look at recursion in the context of a factorial. Do you remember what a factorial is? You may remember it from math class, and it looks a lot like this:

5! = 5 * 4 * 3 * 2 * 1

4! = 4 * 3 * 2 * 1

3! = 3 * 2 * 1

Do you remember how to do that now? Well, the way a factorial works will give us a great example on how recursion works in C#. Another way to write it would be:

N! = N * (N-1)!

In other words, using numbers, it looks a little bit like this:

5! = 5 * (5-1)! which gives us 5! = 5 * (4)! , and finally5! = 5 * 4! .

But, following the formula, we can also write 4! as 4 * (4-1)!, which gives us 4 * 3!. We can plug this back into 5! = 5 * 4! to get: 5! = 5 * (4 * 3!).

Wait, but looking at our new version, 3! can also use the formula! That will eventually get us to: 5! = 5 * 4 * (3 * 2!). We can do the same thing over again with 2!.

Even if you're not a math person, you can see that the factorial formula is used repeatedly. From a coding perspective, you can create a function that runs over and over just like this until you have a complete answer. How can you write a factorial in C# using operators? Let's try it out:

// Define classes
class RecursionInCSharp
{
   public static int Factorial(int n)
   {
      n = n * Factorial (n - 1);
   }
}

If you look carefully at the line n = n * factorial(n-1), you will see that the the factorial method is called within itself. This is called recursion because the method runs over and over as it calls itself.

Do you remember conditional if/else statements? They keep a statement from going on until infinity by stopping the method for a reason. Why would you want to stop the method? When you do the factorial equation, it ends at 1. Essentially, you have to create a conditional statement that will end the recursion when n is 1.

This will do two things:

1. It will stop the factorial method from running after n reaches 1.

2. If the original number is 1, it will just return 1.

Let's see how how this looks:

// define classes
class RecursionInCSharp
{
   public static int Factorial(int n)
   {
      if (n == 1)
      {
         return 1;
      }      
      else
      {
         return n * Factorial(n - 1);
      }
   }
}

Let's go back to the book example from the video. 📚 If you want to count the books in each category, subcategory, and so on, you need to make sure you take into account all the various layers. To address this, you can create a function that will go through the one level of categories. Then, once it’s finished, that function will call itself again, but this time making it work with the subcategories of one of the original categories. That iteration would go further and call itself again to process sub-subcategories until a category at the level in question has no subcategories. This way you can go all the way down to the very last sub-level of each original category. And when a category has no subcategories, your function will return to your starting point.

Here's what the code looks like in C#:

class BookStore
{
   // define a recursive function
   public static int CountBooks(Categories categories)
   {
      int c = 0;
      foreach (Categories category in Categories)
      {
         c += Category.numberOfBooks;
         CountBooks(Category.subCategories);
      }
      return c;
   }
}

// call the recursive function
int numberOfBooks = BookStore.CountBooks(BookStore.categories);
Console.WriteLine("The bookstore has " + numberOfBooks + " books");

Very efficient, isn't it?

In technical terms, recursion is an action that's initialized within itself. It keeps descending down layer upon layer until a condition is met and then bubbles back up to the first layer.

Let's recap!

• Recursion is an action that's initialized within itself.

• Recursion is used to go through layered structures.