Learning to Code — Part 5c: Method Overloading and Recursion

WARNING: This article starts out running along smoothly, and then I hit a wall! I had to do some research to understand what I was being taught, and then documented it. The first item I used didn’t result in understanding, so I continued to search until I found a resource that worked for me. Anyway, it goes on for a while.

Overloading sounds like something you shouldn’t do, but method overloading is useful in C# when you have multiple methods with the same name, but different parameters. I didn’t really understand this at first until seeing some code of what that would look like. My first thought was, won’t having more than one method with the same name confuse the program? How will it know which one to run?

Apparently, it’s pretty smart and, one example is when you’d like to have a variables of different data types, but want them to go through the same process.

static void Print(int a) {
     Console.WriteLine(“Value: “ + a);
}
static void Print(double a) {
     Console.WriteLine(“Value: “ + a);
}

Above, you see two methods with the same name, but can take in values of parameters of two different data types.

On a side note, the app also explains the plus sign (+) as a way of joining the word Value: with the value of the variable a. This is called concatenating.

A requirement of overloading methods is that they differ from each other by the types and/or number of parameters. When there are multiple methods of the same name, and they’re called, the specific method that will be used will be based on the data type of the arguments being sent.

Let’s add one more method called Print to go along with the other two above:

static void Print(string label, double a) {
     Console.WriteLine(label + a);
}

Next, our Main method will look like this:

static void Main(string[] args) {
     Print(11);
     Print(4.13);
     Print(“Average: “, 7.57);
}

So, here’s what’s going to happen:

• The first line of the Main method calls the Print method that will match up with the data type of the argument being sent. In this case, it’s the number 11, which is an integer. So, it will call the first method called Print (which has (int a) next to it), and then print Value: 11 to the screen.
• The second line of the Main method calls the Print method that will match up with the data type of the argument being sent. In this case, it’s the number 4.13, which is an double. So, it will call the second method called Print (which has (double a) next to it), and then print Value: 4.13 to the screen.
• The third line of the Main method calls the Print method that will match up with the data type of the argument being sent. In this case, since there are two arguments, it will call the third method called Print (which has (label + a) next to it). Average: will be the value assigned to the variable called label (which has string assigned as it’s data type), and 7.57 will be assigned to the variable called a (which has double assigned as it’s datatype). It will then print Average: 7.57 to the screen.

The app does go on to mention, however, that you cannot overload method declarations that differ only by return type. As an example, the following methods would result in an error:

int PrintName(int a) { }
float PrintName(int b) { }
double PrintName(int c) { }

I had to investigate a bit to understand why this would generate an error. I ended up find thing the following explanation on aStack Overflow page:

An overloaded method may or may not have different return types. But return type alone is not sufficient for the compiler to determine which method is to be executed at run time.

This cleared it up for me because what it’s saying is that with the methods shown above, they all take in integers. So although the return types for each are different, when the method PrintName is called, there’s no way to determine which one to use based in the parameter data type, because they all have the same data type: integer.

So that’s method overloading. Lastly, as mentioned, a recursive method is a method that calls itself. The example that the SoloLearn app gives as to when you’d need to do this, is when you’re calculating the factorial of a number. They describe the mathematical term factorial as:

…the product of all positive integers that are less than or equal to a specific non-negative integer.

Factorial is denoted with an exclamation mark (!), such as:

4! = 4 * 3 * 2 * 1, which equals 24.

I wanted to understand a bit more about how this worked and why you’d want to use it and, after some Googling, found myself on a page on the c-sharpcorner.com website. To jump to the end, you’d want to use it because it’s a cleaner, more efficient way of writing the code. For example, without recursion, the method that executes the factorial process would look like this:

Note: Before I show it, let’s say in the Main method, you asked the user for a number, and that number was assigned to a variable called number, whose data type was set to integer. Then, our new method (called Factorial) is called, it’s sent the value of the variable number, and the result of the running of that method (called Factorial) is assigned to a new variable called factorial, whose data type is double.

public static double Factorial(int number) {
     if (number == 0)
     return 1;
     double factorial = 1;
     for (int i = number; i >= 1; i — ) {
          factorial = factorial * i;
     } return factorial;
}

I tried to just look at the code to understand what was going on, but it didn’t work. So, let’s say the user enters the number 5, here’s what happens:

• A method called Factorial is declared, is public (which means any class can access it), is static (which means it cannot have any instances of itself created), will return a value whose data type is double and, when it’s sent an argument, the value of that argument will be stored in a variable called number, whose data type is integer.
• Next, there is a check to see if the value of the variable number is equal to 0. If it is equal to 0, then the method returns the value 1 to the place where it was called. Apparently, in “math” the factorial of 0 is 1…and that’s it. It doesn’t seem logical, but it is the case. If the value of number is not 0, then it moves on to the next line.
• A variable called factorial is created, assigned a data type of double, and given the value 1.

Next, there is a for loop which will start with the number that the user entered, and multiply it by the next lower, whole number, and then by the next lower whole number, and then by the next lower whole number, and so on, until it gets down to 1.

The for loop starts out by creating a variable called i, setting its data type to integer, and assigning it’s value equal to the value of the variable number. It establishes a condition to be checked against, which is whether or not the value of i is greater than or equal to 1. If it is, it runs through the next line, and then decrements the current value of i by 1. If it isn’t, then the current value of the variable factorial is set back to the place where it was called. Let’s continue on, remembering that the user entered the value 5, which was then assigned to the variable called number:

• The newly created, integer-based variable called i is set to the value of the variable called number (which is 5), so, i = 5.
• The condition of whether i is greater than or equal to 1 is checked, meaning, is 5 greater than or equal to 1? And the answer is, yes. So we move to the next line.
• The variable factorial, whose data type is double, is now set as equal to the current value of the variable factorial, which is 1, multiplied by the current value of i, which is 5. So, the variable factorial is 5 * 1, or 5. The value of i is now decremented by 1, meaning 5–1, so i is now equal to 4.
• The condition of whether i is greater than or equal to 1 is checked again, meaning, is 4 greater than or equal to 1? And the answer is still yes, so we move to the next line.
• The variable factorial is now set as equal to the current value of the variable factorial, which is 5, multiplied by the current value of i, which is 4. So, the variable factorial is 5 * 4, or 20. The value of i is now decremented by 1, meaning 4–1, so i is now equal to 3.
• The condition of whether i is greater than or equal to 1 is checked again, meaning, is 3 greater than or equal to 1? And the answer is still yes, so we move to the next line.
• The variable factorial is now set as equal to the current value of the variable factorial, which is 20, multiplied by the current value of i, which is 3. So, the variable factorial is 20 * 3, or 60. The value of i is now decremented by 1, meaning 3–1, so i is now equal to 2.
• The condition of whether i is greater than or equal to 1 is checked again, meaning, is 2 greater than or equal to 1? And the answer is still yes, so we move to the next line.
• The variable factorial is now set as equal to the current value of the variable factorial, which is 60, multiplied by the current value of i, which is 2. So, the variable factorial is 60 * 2, or 120. The value of i is now decremented by 1, meaning 2–1, so i is now equal to 1.
• The condition of whether i is greater than or equal to 1 is checked again, meaning, is 1 greater than or equal to 1? And the answer is still yes, so we move to the next line.
• The variable factorial is now set as equal to the current value of the variable factorial, which is 120, multiplied by the current value of i, which is 1. So, the variable factorial is 120 * 1, or 120. The value of i is now decremented by 1, meaning 1–1, so i is now equal to 0.
• The condition of whether i is greater than or equal to 1 is checked again, meaning, is 0 greater than or equal to 1? And the answer is now no, so we move to the next line after the for loop.
• The current value of the variable factorial, which is 120, is returned to the point where it was called.

So, this function takes the number input by the user, which was 5, and performs the factorial process on it, resulting in 120.

That was certainly a lot of steps and, while the recursive way of writing the code will come to the same result, it’s written in a cleaner, more efficient way. That said, let’s look at how to write out in a mathematical way:

5! = 5*(5–1)*(5–2)*(5–3)*(5–4) = 120

The code, therefore, is written like this:

if (number == 0)
     return 1;
     return number * Factorial(number-1);

Translated into English, this means:

….hmmm….

Yeah, I really don’t understand what’s happening here. I completely understand how factorial works, but can’t understand how the code above is executing it. Here’s what my mind sees when it goes through this loop 5 times:

return number * Factorial(((Factorial(Factorial(Factorial(Factorial-1)-1)-1)-1))-1);

And I guess, technically, that’s correct (I think), but how can it do all that without getting in an infinite loop?

…a little bit later…

After some Googling, I found a video on YouTube, by Jeff Chastine, called Tutorial 17.2 — introduction to recursion in c#.

The first thing he does is explain how factorial works, which we’ve done before. Just to go along with his tutorial, however, here’s what he says:

• 75! Is the equivalent of 75 * 74 * 73 * ….* 1

He then points out that this is really the same as saying:

• 75 * 74!

Which is, therefore, the same as saying:

• 75 * 74 * 73!

…and so on, all the way down to 1. But he also says the following sentence that really made it make sense to me:

To figure out 75 factorial, we really need to figure out 74 factorial. And to figure out 74 factorial, we really need to figure out 73 factorial. When would it stop? At some point we’d figure out that 1 factorial is just 1.

He then translated that into the following, generic, formula:

n! = n * (n-1)!

I also like two of the things he says next:

• Going to create “clones” of the function.
• Usually, the clone has a smaller problem to work.

Here’s, then, what he says the code would look like in C#:

int factorial (int n) {
     if (n == 1) {
          return 1;
     }
     else {
          return n * factorial(n-1);
     }
}
void Main () {
     int f = factorial(4);
}

That code is almost exactly the same as the code from the SoloLearn app. As I’ve been doing with my steps, here’s how he describes each line:

• To begin, the return type is integer, the method name is Factorial, and it takes in an integer that we’ll call n.
• Next, we’ll say that if n is equal to 1, we’ll just return a value of 1. Now, lower down we’re using the value 4, but if that value was 1, we already know the answer is 1, so no looking is necessary.
• If the value of n is not 1, then we’ll return the result of n (which, in this case, is 4) multiplied by the recursive call of the factorial of n-1.

Next, he rounds out the code, and puts in some Console.WriteLines so we can see what the value of n is as we move through it:

static int factorial (int n) {
     Console.WriteLine(n);
     if (n == 1) {
          return 1;
     }
     else {
          int result = n * factorial(n-1);
          Console.WriteLine(n);
          return result;
     }
}
void Main () {
     int f = factorial(4);
     Console.WriteLine(f);
}

At this point, I also decided to put this code into Visual Studio, so I wasn’t just randomly typing it here, and visually seeing the results on YouTube.

Then to help trace it through, and this is what really helped it sink in, he created something called a function stack, and says,

The idea here is that we’re going to call a function, and then push that onto the stack.

• So, in Main, we call the method called Factorial, and pass it a 4. He then put that on the stack, like this:

• Jumping up to the factorial function, and knowing that n is equal to 4, he puts that in the stack, like this:

• As it runs through, it hits the first Console.WriteLine saying to print the current value of n to the screen and, therefore, prints 4 to the screen.
• Next, it checks if n is equal to 1 and, since it’s not, it jumps to the next line.
• The next line says, calculate a result, which will be n * factorial(n-1), which translates into result being set equal to 4 * factorial(4–1) or 4 * factorial(3).

Here’s the key, and the reason why my brain got tripped up: the next two lines (Console.WriteLine(n);and return result;) cannot be done yet because there’s pending work. So, for now, he put it in the stack as follows, and noted that there was pending work:

In other words, the stack his helping us to keep track of the work that still needs to be done, while still allowing us to move onto the next step in the code. Then he says, now let’s figure out what the factorial of 3 is:

• At this point, n is equal to 3.

This got me stuck before, because I didn’t understand how the loop caused n to now be equal to 3. What is clear now, is that the loop really didn’t cause n to be equal to 3. At this point, we’re just trying to figure out the factorial of 3, with this: factorial(3). This translates into: call the method called factorial, and send it the value, 3. So, he updates the stack, like this:

• For this clone, at this point, we go to the top of the method called factorial, and hit the Console.WriteLine(n), or Console.WriteLine(3), and print 3 to the screen.
• Next, it checks if n is equal to 1 and, since it’s not, jumps to the next line.
• The next line says, calculate a result, which will be n * factorial(n-1), which translates into result being equal to 3 * factorial(3–1) or 3 * factorial(2).

Again, at this point, since this clone still has pending work, he updates the stack:

At this point, we’re just trying to figure out the factorial of 2, with this: factorial(2), so he updates the stack:

• For this clone, at this point, we go to the top of the method called factorial, and hit Console.WriteLine(n), or Console.WriteLine(2), and print 2 to the screen.
• Next, it checks if n is equal to 1 and, since it’s not, jumps to the next line.
• The next line says, calculate a result, which will be n * factorial(n-1), which translates into result being equal to 2 * factorial(2–1) or 2 * factorial(2).

Once again, since this clone still has pending work, he updates the stack:

At this point, we’re just trying to figure out the factorial of 1, with this: factorial(1), so he updates the stack:

• For this clone, at this point, we go to the top of the method called factorial, and hit Console.WriteLine(n), or Console.WriteLine(1), and prints 1 to the screen.
• Next, it checks if n is equal to 1 and, since 1 is equal to 1, the code says to return the value of 1, so he updates the stack as follows:

At this point, we’ve, as he puts it, terminated and, to use his words once again, the stack begins to collapse down to Main. Since we know, from the stack, that factorial(1) is 1, we can do a substitution, and the following happens:

Now, this run through of the code can move onto the next line, which is Console.WriteLine(n); Remember, at this point, n is equal to 2, so the line of code becomes Console.WriteLine(2); which prints 2 to the screen. We can then do the next substitution, which would cause the following:

Now, this run through of the code can move onto the next line, which is Console.WriteLine(n); Remember, at this point, n is equal to 3, so the line of code becomes Console.WriteLine(3); which prints 3 to the screen. We can then do the next substitution, which would cause the following:

Now, this run through the code can move onto the next line, which is Console.WriteLine(n); Remember, at this point, n is equal to 4, so the line of code becomes Console.WriteLine(4); which prints 4 to the screen. We can then do the final substitution, which would cause the following:

Now, the line return result; will send the final result, 24, back to where the original call was made, which was the Main method, which initially sent the value 4. We now know that that results in 24. It then moves to the next line, which is Console.WriteLine(f); (and remember, the initial call of the factorial method from the Main method set the result to a new variable called f, who had a data type of integer). Since f is equal to 24, the line of code becomes Console.WriteLine(24); which prints 24 to the screen.

Aaaand we’re done!

I know understand how recursion works and the key to it was the idea that it’s OK for there to be pending work. That all the work doesn’t have to be done…RIGHT NOW!

Hopefully you stuck along for that journey. As always, please let me know if I got anything wrong, and if anything needs further explanation.

Also, here’s the link to the previous post, Learning to Code — Part 5b: Arguments.