Recursion, can't understand the output

Question

Why am I getting an additional 1 * 1 in the output and it's kinda backwards ? Kinda beginner here with recursion, would love a detailed answer.

class Program
{

    public static long Factorial(int n)
    {
        if (n == 0)
            return 1;

        Console.WriteLine("{0} * {1}", n, Factorial(n - 1));
        return n * Factorial(n - 1);    
    }
    static void Main(string[] args)
    {
       long a = 0;
        a = Factorial(3);
        Console.WriteLine(a);
    }
}

output

1 * 1
2 * 1
1 * 1
3 * 2
1 * 1
2 * 1
1 * 1
6

Answer 1

You're calling the function recursively twice, once in the output and then again on the next line. This is the reason the output is all jumbled, because you call it from the Console.WriteLine() method, and then immediately call it again in your return statement.

Also, the factorial of zero is one, so I added a little ternary statement check for that in the WriteLine() method so that the output would be mathematically correct.

Console.WriteLine("{0} * {1}", n, Factorial(n - 1));  // Calling it once
return n * Factorial(n - 1);    // Calling it again, oops!

Here's a slight tweak that will help:

public static long Factorial(int n)
{
    if (n == 0)
        return 1;
    Console.WriteLine("{0} * {1}", n, (n>1?n-1:n));
    return n * Factorial(n - 1);    
}

static void Main(string[] args)
{
   long  a = Factorial(3);
    Console.WriteLine(a);
}

Yields

3 * 2
2 * 1
1 * 1 
6

Answer 2

It's because there's a second factorial loop going on in the logging output:

Console.WriteLine("{0} * {1}", n, Factorial(n - 1));

This needs to calculate Factorial(n-1) before it prints anything. Because each step of the recursion is now triggering two recursions, it's a lot more complicated than you expected!

So Factorial(3):

• Starts to log "3 * Factorial(2)" -> but needs to work out Factorial(2)
  • Factorial(2) starts to log "2 * Factorial(1) -> but needs to work out Factorial(1)
    • Factorial(1) starts to log "1 * Factorial(0) -> but needs to work out Factorial(0)
      • Factorial(0) returns 1
    • Now Factorial(1) can print "1 * 1" (Your first line of output.)
    • Now Factorial(1) needs to calculate Factorial(0) for its return value...
      • Factorial(0) returns 1
  • Factorial(2) can log "2 * 1" (Your second line of output.)
  • Factorial(2) now needs to calculate Factorial(1) to return
    • Factorial(1) starts to log "1 * Factorial(0) -> but needs to work out Factorial(0)
    • ... etc. etc.

If you change it to something like:

Console.WriteLine("{0} * Factorial({1})", n, n - 1);

Then you'll get something more like the logging that you expect.

(If you're learning about recursion, it might be interesting for you to work through with a debugger and see how the flow of the program goes, and why it results in the output that you do see.)

Answer 3

As it happens, your mistake has nothing to do with recursion. You're problem is, that you call a method twice, instead of saving the value of it. You wouldn't even realize this, if you wouldn't print the result. As @JLK pointed out, you call it twice in this snippet:

Console.WriteLine("{0} * {1}", n, Factorial(n - 1));
return n * Factorial(n - 1);

Let's step through the code, so that we can understand the output:

Factorial (3);
-> output 3 * {Factorial (2)}          // 3 * 2 (4)
   -> output 2 * {Factorial (1)}       // 2 * 1 (2)
      -> output 1 * {Factorial (0)}    // 1 * 1 (1)
         <- 1 
         Factorial (0)
      <- 2
      Factorial (1)
         -> output 1 * {Factorial (0)} // 1 * 1 (3)
         <- 1
         Factorial (0)
      <- 1
   <- 1
   Factorial (2)
   -> output 2 * {Factorial (1)}       // 2 * 1 (6)
      -> output 1 * {Factorial (0)}    // 1 * 1 (5)
         <- 1
         Factorial (0)
      <- 1
      Factorial (1)
         -> output 1 * {Factorial (0)} // 1 * 1 (7)
         <- 1
         Factorial (0)
      <- 1
   <- 2

This might be a bit confusing, but that's normal for recursion. So basically all you have to do is to change the code snippet a little bit:

var factorial = Factorial (n - 1);
Console.WriteLine("{0} * {1}", n, factorial);
return n * factorial;

The output then is:

1 * 1
2 * 1
3 * 2
6

---

If you want to learn more about recursion, I'd suggest this site. It isn't about C#, but it's a great site to learn recursion in general. If you want to do much in recursion, I wouldn't suggest C# anyway, as it is an imperative language. For recursion functional languages are better suited. If you still want to keep close to C#, or at least use the .Net framework, I'd suggest to use F#, which is the functional equivalent of C#.

The main problem with C# and recursion is, that C# doesn't support Tail recursion. This can easily result in StackOverflows, when you do deeper recursive calls (like for example an infinite recursive loop). This is because everytime you call a function, the code address from which you called the function is pushed onto the stack. So everytime you do a recursive call, the code adddress is pushed to the stack. So if you have for example this function:

void rec () => rec();

You get a StackOverflow in less than a second in C# by calling it. Tail recursion however solves this problem at least partially: It doesn't push the code address of the caller if the recursive call was the last execution in a function. So in F# this runs forever:

let rec r () =
    r ()
r ()

(I won't go deeper into F# syntax, there are enough tutorials online). I said it solves the problem only partially, because this:

let rec r () =
    r ()
    ()
r ()

results in a StackOverflow once again. I'm not aware of any programming language, where this isn't the case, so you'll just have to get used to using tail recursion.

You can read more about functional / recursive languages in this post.

Answer 4

You should to copy right your homework from scoreboard. You must chage:

    Console.WriteLine("{0} * {1}", n, Factorial(n - 1));

by

    Console.WriteLine("{0} * {1}", n, n - 1);

This mistake make the wrong output.