Factorial Calculations using Recursive Method call

Question

This code is from the book: "C# 5.0 in a Nutshell" and is a sample on LinqPad. On page 39 it says:

"This method is recursive, meaning that it calls itself. Each time the method is entered, a new int is allocated on the stack, and each time the method exits, the int is deallocated."

Using the literal 5 yields and answer of 120 (3 yields 6)

Can someone explain how this works? I'm a VB programmer trying to learn C# and would like to understand constructs like this. I've single stepped through it many times and can't understand what happens after x == 0 and 1 is returned. Until x equals zero, the flow of execution is easy to understand. After that, the last return statement seems to be repeatedly executed (magically) until x increments back to it's original value and then returns to the point where it was originally called and produces the aforementioned (magical) numeric result.

static void Main()
{
    Console.WriteLine (Factorial(5));
}
static int Factorial (int x)
{
    if (x == 0) return 1;
    return x * Factorial (x-1);
}

Answer 1

Call Factorial(3) (which returns 3 * 2)
  x doesn't == 0
  return 3 * Factorial(2)  
             Calls Factorial(2) (which returns 2 * 1)
               x doesn't == 0
               return 2 * Factorial(1)  
                          Calls Factorial(1) (which returns 1 * 1)
                            x doesn't == 0
                            return 1 * Factorial(0)
                                       Calls Factorial(0) (which returns 1)
                                         x == 0 so return 1

An important point is that the recursive function must have a termination condition, otherwise it would call itself infinitely (until it runs out of stack space). In your example, the if (x == 0) return 1; is the termination condition. Since the function calls itself with a parameter value of one less than it was called with, eventually it will end up calling itself with 0, and that is when the recursion ends.

This brings out a problem with this code though. If you call with a negative number, it will call itself recursively with increasingly negative numbers, will never reach 0, and you'll eventually run out of stack space. How best to handle that is probably outside the scope of your question though.

Answer 2

Thanks for all the great replies to my question. I have a both a better understanding now of this piece of code works and a realization that I need to put a more in-depth study of recursion on my TO-DO list.

Answer 3

The concept of recursion is not really limited to any specific language. The idea behind it that the function calls itself.

Let's consider your example: factorial function. But for now let's put implementation aside and think of it in more abstract terms. The function consists of two elements:

i) Instruction how to calculate an element 'n'.

ii) Instruction how to calculate an initial element

So how do we calculate element n for factorial? We take n and multiply it by factorial of a previous element: n-1:

n * Factorial(n-1)

And there is only one initial item: 0. That is when n == 0 the result is 1 or in other words Factorial(0) gives 1.

The algorithm you provided contains really of these two steps

if (x == 0) 
    return 1;                      // Do this when calculating Factorial of 0
else
    return x * Factorial (x-1);    // Do this when calculating an element n

Ok. Now what happens when we want to calculate factorial of 4? Let's break it down to specific steps.

Factorial(4) -> 4 * Factorial(4-1) -> 4 * Factorial(3)

We invoked factorial of 4. So we multiply 4 by factorial of 4-1. To get the factorial of 4-1 we again invoke factorial function:

Factorial(3) -> 3 * Factorial(3-1) -> 3 * Factorial(2)

Now we need to calculate factorial of 2.

Factorial(2) -> 2 * Factorial(2-1) -> 2 * Factorial(1)

And of 1

Factorial(1) -> 1 * Factorial(1-1) -> 1 * Factorial(0)

Note that now we have to calculate factorial of 0. But here we have a special instruction: if the argument is 0 the result has to be 1. Let's wind back our calculations:

Factorial(0) is 1. Replace the result in the calculation for factorial of 1.

Factorial(1) -> 1 * Factorial(1-1) -> 1 * 1 which is also 1

Factorial(2) -> 2 * Factorial(1) -> 2 * 1 -> 2

Factorial(3) -> 3 * Factorial(2) -> 3 * 2 -> 6

Factorial(4) -> 4 * Factorial(3) -> 4 * 3 -> 12

You mentioned following explanation:

Each time the method is entered, a new int is allocated on the stack, and each time the method exits, the int is deallocated.

These steps when we go inside Factorial function to calculate factorial for a previous number is when a new int has to be allocated on the stack: for factorial of 4 the number 4 goes on the stack and the algorithm calculates factorial of 3, and so on. And when we get to the very end that is to factorial of 0 we can finally start deallocating numbers. We have factorial of 0, multiply the result by 1. Factorial of 1 is returned and 1 is deallocated. Same happens for 2, 3 and finally 4.

Hope that clarified whole concept a bit. I'm aware the explanation is extensive, but, on the other hand, it's tricky to grasp it at the beginning so I preferred to be too thorough.

Answer 4

There is one call to return for each call to Factorial. These are the recursive calls unwinding after x == 0.

I think this might be easier to see if you slightly modify your code, if only temporarily:

static int Factorial (int x)
{
    if (x == 0) return 1;
    else
    {
         int y = x * Factorial (x-1);
         return y;
    }
}

Answer 5

What it is doing is calling itself repeatedly.

What's effectively happening is the following.

We enter Factorial with x equal to 5 and since we're greater than 0 we multiply our 5 with the result of calling our self (Factorial) again with 5 - 1 which is 4. Inside this recursive call we find our selves doing another recursive call with 4 - 1 which is 3. We do this repeatedly until we call Factorial with 0, where it returns 1. Then that 1 returns to the recursion which multiplies it by 2, which returns to the recursion which multiplies it by 3, and then the next by 4, and then the next by 5.

In the end you return the result of 1 * 2 * 3 * 4 * 5 which is 120.

Answer 6

The method Factorial calls itself again, starting with 5, and decrements the argument (x-1), until the passed argument x is 0.

So the first call to Factorial passes 5, the second call 4, 3, 2, 1, 0.

And the math done is: 5*4*3*2*1 = 120.

Answer 7

It's recursive because this statement here:

return x * Factorial (x-1);

returns the result of x * the result of the call to Factorial (X-1)... It's calling itself to get the answer. It breaks out of the loop when x==0 simply by returning the value of 1.

But one thing to note, to whom does x==0 return the value? The answer is most likely the loop which is accumulating the values.