Why is the first timed function always measured to be faster with `Stopwatch`

Question

I am trying to establish is iteration or recursion is faster in C#. However, on a simple test, I cannot seem to get trustworthy results using StopWatch.

Code:

internal class Program
    {
        // The factorial of a number is the product of all the
        // integers from 1 to that number.
        // For example, the factorial of 6 is 1*2*3*4*5*6 = 720
        // Factorial is not defined for negative numbers, and the factorial of zero is one, 0! = 1 
        static void Main(string[] args)
        {
            Console.WriteLine("Please Enter a Number:");

            //read number from user
            int number = Convert.ToInt32(Console.ReadLine());
            
            double sw1Elapsed = 0d;
            double sw2Elapsed = 0d;
            double factorial = 0d;
            double factorial2 = 0d;

            Stopwatch sw = new Stopwatch();
            sw.Reset(); 
            for (int i = 0; i < 6; i++)
            {
                sw.Restart();
                factorial = Factorial(number);
                sw.Stop();
                sw1Elapsed = sw1Elapsed + sw.Elapsed.TotalMilliseconds;

                sw.Restart();
                factorial2 = FactorialByRecursion(number);
                sw.Stop();
                sw2Elapsed = sw2Elapsed + sw.Elapsed.TotalMilliseconds;

                //print the factorial result
                Console.WriteLine("Iteration:");
                Console.WriteLine("Factorial of " + number + " = " + factorial.ToString());
                Console.WriteLine("Iteration Time taken = " + sw1Elapsed);
                Console.WriteLine();
                Console.WriteLine("Recursion:");
                Console.WriteLine("Factorial of " + number + " = " + factorial2.ToString());
                Console.WriteLine("Recursion Time taken = " + sw2Elapsed);
                Console.WriteLine("-----------------------------------------------------\n");
            }
        }


        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;
        }

        public static double FactorialByRecursion(int number)
        {
            if (number == 0)
                return 1;
            return number * FactorialByRecursion(number - 1);//Recursive call

        }
    }
}

So there are two functions that do the same thing in two different ways.

And these yield these results:

---

Please Enter a Number: 6 Iteration: Factorial of 6 = 720 Iteration Time taken = 0.3171
Recursion: Factorial of 6 = 720 Recursion Time taken = 0.0616
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken = 0.3172
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.061700000000000005
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken =
0.31739999999999996
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.06180000000000001
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken =
0.31749999999999995
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.06190000000000001
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken =
0.31759999999999994
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.06200000000000001
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken =
0.3177999999999999
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.062100000000000016
-----------------------------------------------------
C:\Users\Dev\source\repos\SimpleRecursion\SimpleRecursion\bin\Debug\net6.0\SimpleRecursion.exe (process 26992) exited with code 0. To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops. Press any key to close this window . . .

---

But, if I move the second function to above the first in the loop, so the could would be:

static void Main(string[] args)
        {
            Console.WriteLine("Please Enter a Number:");

            //read number from user
            int number = Convert.ToInt32(Console.ReadLine());
            
            double sw1Elapsed = 0d;
            double sw2Elapsed = 0d;
            double factorial = 0d;
            double factorial2 = 0d;

            Stopwatch sw = new Stopwatch();
            sw.Reset(); 
            for (int i = 0; i < 6; i++)
            {
                sw.Restart();
                factorial2 = FactorialByRecursion(number);
                sw.Stop();
                sw2Elapsed = sw2Elapsed + sw.Elapsed.TotalMilliseconds;

                sw.Restart();
                factorial = Factorial(number);
                sw.Stop();
                sw1Elapsed = sw1Elapsed + sw.Elapsed.TotalMilliseconds;

                //print the factorial result
                Console.WriteLine("Iteration:");
                Console.WriteLine("Factorial of " + number + " = " + factorial.ToString());
                Console.WriteLine("Iteration Time taken = " + sw1Elapsed);
                Console.WriteLine();
                Console.WriteLine("Recursion:");
                Console.WriteLine("Factorial of " + number + " = " + factorial2.ToString());
                Console.WriteLine("Recursion Time taken = " + sw2Elapsed);
                Console.WriteLine("-----------------------------------------------------\n");
            }
        }

Then the results become:

Please Enter a Number:
6
Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0571

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.1066
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0571

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.1069
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0572

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.1071
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0572

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.1073
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0572

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.10750000000000001
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.057300000000000004

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.10770000000000002
-----------------------------------------------------


C:\Users\Dev\source\repos\SimpleRecursion\SimpleRecursion\bin\Debug\net6.0\SimpleRecursion.exe (process 26100) exited with code 0.
To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops.
Press any key to close this window . . . 

Can anyone explain the differences in the elapsed times and why/what is happening?

The point I am making is whichever function call is placed first in the loop produces the best time via Stopwatch. I am asking why that is? (btw, it does the same if using int for the factorial).

Answer 1

The point I was making is whichever function call comes first in the loop produces the best time via Stopwatch. I was asking why that is?

That is a good question, but you have to realize that all these numbers are profoundly absurd.

"Why is the number that is about ten thousand times as large as it should be always larger for A than for B?" has (honestly!) nothing to do with factorials – which your question focuses on.

Technically:

Try simply doing empty Restart(); Stop() pairs and you'll see that the issue is with your means of measuring time. In other words, for the time periods you care about, Stopwatch seems completely unsuitable. I'm not an .NET expert – but it would seem to me that it is not using a hardware high-resolution timer, and that ElapsedMilliseconds probably causes a context switch (goes from executing your application's code to executing code of the kernel), which would explain smaller results if you're freshly coming out of kernel context after a Consele.WriteLine.

Code-wise:

In imperative languages like C#, it's really never a question whether recursion for such a flat linear operation is faster than a loop – it's not; in the very best case, the compiler can optimize recursion to be as efficient as the loop is. That's simply because "calling into a function" and "returning from a function" have significant overhead compared to multiplying two integers. A highly optimizing compiler might, under circumstances, implement tail recursion optimization, in which it recognizes that not all the state of the function needs to be saved ("pushed onto the stack").

Calculating the faculty hence is a classical example of what not to do recursively in such programming languages. It's also often the first example shown to learners – because, for reasons unclear to me, some books insist in explaining recursive algorithms to people who will not use them, lacking understanding (yet) of the data structures for which they are appropriate.

Answer 2

I am trying to establish is iteration or recursion is faster in C#

This depends on the specific use case. There is no general rule that covers all use cases.

For a simple tasks, like summing all numbers in a list, iteration will almost certainly be faster, since you avoid the overhead of a method call for each item.

For more complex tasks, like traversing the tree, it becomes more complicated. You can transform the recursive implementation into an iterative by using an explicit stack instead of the implicit stack used to manage method calls. This might be faster, since the method call to push/pop the stack may be inlined. On the other hand, the CPUs are highly optimized to handle call stacks, since they are used in most languages, and that might give it the edge in some cases.

Another factor is development time, some tasks are just easier to solve with recursion, allowing you to spend more time optimizing other parts that might matter more. And in many cases the difference between recursion and iterations is small enough that it does not matter.

You also need to check the way you are measuring, you should at least

1. Run in release (without any debugger attached)
2. Do a "warmup" run to avoid measuring jitting time. Possibly many warmup runs in the case of tiered compilation
3. Ensure that the test runs long enough to minimize measurement variance. Typically by repeating the test say 1000 times.

But a better approach is to use Benchmark.Net, it does all of the above, and much more, to ensure the test results are reliable. But you need to test an an actual real world task. Making some synthetic test and declaring one or the other as the winner for all tasks is just wrong.