Loop vs. Recursion

Whenever people start to implement recursive functions in C# they begin to discuss whether recursive function calls or loops are faster and which technique they should prefer. I have heard such discussion several times and therefore I want to do a short test within this article and measure the execution times of loops, recursive function calls and tail recursive function calls in C# and F#.

 
The Test Function
I want to do the comparison by using a simple function. Therefore I decided to write a function which calculates the sum of all integer values from 1 to x. There exists a simple formula for this calculation: (x+1)*x/2. But to test the speed of loops and recursive function calls, the calculation will be done without this formula.

 
C# Source code
The following source code shows a possible implementation for the loop and the recursive function call in C#.

public static long ExecuteLoop(int count)
{
    long total = 0;

    for (int i = 1; i <= count; i++)
    {
        total = total + i;
    }

    return total;
}

public static long ExecuteRecursive(int count)
{
    if (count == 1)
        return 1;
    else
        return count + ExecuteRecursive(count - 1);
}

 
Furthermore a tail recursive function is used. The tail recursive function has other parameters. Therefore this is a public function which will be called by a public function which has the same parameters like the previous functions for the loop and recursive call.

public static long ExecuteTailRecursive(int count)
{
    return ExecuteTailRecursiveInternal(count, 0);
}

private static long ExecuteTailRecursiveInternal(int count, long total)
{
    if (count == 0)
        return total;
    else
        return ExecuteTailRecursiveInternal(count - 1, total + count);
}

 
F# Source code
The next implementation shows the recursive function in F#.

let rec executeRecursive x = 
    if x = 1
    then 1
    else x + executeRecursive (x-1)

 
And of course, like in the C# solution, I have created a tail recursive function. This is also done with a little modification and by using an internal function.

let executeTailRecursive x = 
    let rec executeTailRecursiveInternal x total = 
        if x = 0
        then total
        else executeTailRecursiveInternal (x-1) (total+x)
    executeTailRecursiveInternal x 0

 
Measurement
The measurement is done by a little C# console application. Each of the five test methods will be executed several times (1000 or 10000 times) with the parameter 10000. Therefore 10000 loops or recursive functions calls will be executed for 1000 or 10000 times. Furthermore each test is done five times to get more test results. The following source code shows the console application.

static void Main(string[] args)
{
    Stopwatch watch;
    int test, functionCall;
    int tests = 5;
    int functionCalls = 10000;


    Console.WriteLine("CSharp.ExecuteLoop");

    for (test = 0; test < tests; test++)
    {
        watch = new Stopwatch();
        watch.Start();
        for (functionCall = 0; functionCall < functionCalls; functionCall++)
        {
            CSharp.ExecuteLoop(10000);
        }
        watch.Stop();
        Console.WriteLine(watch.ElapsedMilliseconds);
    }

    Console.WriteLine("CSharp.ExecuteRecursive");

    for (test = 0; test < tests; test++)
    {
        watch = new Stopwatch();
        watch.Start();
        for (functionCall = 0; functionCall < functionCalls; functionCall++)
        {
            CSharp.ExecuteRecursive(10000);
        }
        watch.Stop();
        Console.WriteLine(watch.ElapsedMilliseconds);
    }

    Console.WriteLine("CSharp.ExecuteTailRecursive");

    for (test = 0; test < tests; test++)
    {
        watch = new Stopwatch();
        watch.Start();
        for (functionCall = 0; functionCall < functionCalls; functionCall++)
        {
            CSharp.ExecuteTailRecursive(10000);
        }
        watch.Stop();
        Console.WriteLine(watch.ElapsedMilliseconds);
    }

    Console.WriteLine("FSharp.executeRecursive");

    for (test = 0; test < tests; test++)
    {
        watch = new Stopwatch();
        watch.Start();
        for (functionCall = 0; functionCall < functionCalls; functionCall++)
        {
            FSharp.executeRecursive(10000);
        }
        watch.Stop();
        Console.WriteLine(watch.ElapsedMilliseconds);
    }

    Console.WriteLine("FSharp.executeTailRecursive");

    for (test = 0; test < tests; test++)
    {
        watch = new Stopwatch();
        watch.Start();
        for (functionCall = 0; functionCall < functionCalls; functionCall++)
        {
            FSharp.executeTailRecursive(10000);
        }
        watch.Stop();
        Console.WriteLine(watch.ElapsedMilliseconds);
    }

    Console.ReadKey();
}

 
Measured execution time
The following table shows the execution time of 10000 loops or 10000 recursive function calls. These executions where done 1000 and 10000 times. It was not possible to combine these two loops, because such a high number of recursive functions calls will result in a Stack Overflow exception.

Test Execution time (in   seconds) of 1000 iterations Execution time (in   seconds) of 10000 iterations
C# Loop 41 410
C# Recursion 340 3370
C# Tail Recursion 340 3350
F# Recursion 77 770
F# Tail Recursion 34 340

 

These measurements are showing some interesting facts. Loops are very fast but recursion is slow in C#. Furthermore it looks like no optimization is done in C# even if tail recursive function calls are used. F# recursive calls are a little bit slower than C# loops. The reason may be the overhead to manage the stack. Tail recursive function calls lower this overhead. As a result the execution time of the tail recursive F# solution is even below the execution time of the C# loop. In this measurement the tail recursive functions calls in F# are the fastest of the five compared solutions. But they are not much faster than the loops in C#.

 
Summary
It is not easy to answer the question whether you should use loops or recursive function calls. As often the answer must be: It depends! If you want to work with data which has a tree structure, you should use recursion because this will increase the readability and therefore the quality of your source code. In this case it doesn’t matter whether you use C# or F#. Only if you have very large data structures and the execution time of you functions matters or if you get stack overflow exceptions, you have to think about an optimization of you source code. In this case you should use loops if you want to implement in C#, because C# is not optimized for recursion. Therefore if you want to implement recursive functions you may use F# instead. And please keep in mind, you can use F# assemblies in C#. So it is possible to implement you data analysis in an F# assembly and call these function in your C# application.

Advertisements
Dieser Beitrag wurde unter .NET, C#, F# abgelegt und mit verschlagwortet. Setze ein Lesezeichen auf den Permalink.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s