Performance in C# recursion vs. F#

I did know that the F# compiler pulls some magic tricks with recursion, but I didn't know that it could affect performance like I've recently discovered. Me and my friend where discussing Project Euler #16, and where he did an iterative C# solution manipulating strings, I went for a recursive list mangling solution in F#.

Project Euler #16

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 2^1000?

Iterative string manipulating solution by Whettingstone

```public static void Run()
{
/2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?/

StringBuilder allDigits = new StringBuilder("1");
int carryOver = 0;
int temp;

for (int i = 0; i < 1000; i++)
{
for (int index = 0; index < allDigits.Length; index++)
{
//Multiply the digit by two
temp = int.Parse(allDigits[index].ToString()) * 2;

if (temp > 9)
{
//The result is 10 or larger so add digit and set carryOver
allDigits.Remove(index, 1);
allDigits.Insert(index, (temp % 10) + carryOver);
carryOver = 1;
}

if (temp <= 9)
{
//The result is less than 10 so add digit and reset carryOver
allDigits.Remove(index, 1);
allDigits.Insert(index, temp + carryOver);
carryOver = 0;
}

if ((index == allDigits.Length - 1) && carryOver == 1)
{
//This is the last index so add the carryOver to the StringBuilder and break the loop
allDigits.Append(carryOver);
carryOver = 0;
break;
}
}
}

//Calculation is done, let's sum it up
int sum = 0;

for (int i = 0; i < allDigits.Length; i++)
{
sum += int.Parse(allDigits[i].ToString());
}

Console.WriteLine("Sum of 2^1000: {0}", sum);
}```

This solution is pretty straight forward. Put the result in a string, double all the digits and span out overflowing number to next number in the string. At the end he sums it all up to an int. Mean execution time: 127 ms

Recursive F# solution by me

```let rec calc list exp =
let rec evenOut overhead l =
| [], 0 -> []
```match exp with
| 1 -&gt; list
| _ -&gt; calc (list |&gt; List.map (fun x -&gt; x * 2) |&gt; evenOut 0) (exp - 1)
```
calc [2] 1000 |> List.sum```

This is two recursive loops where the outer loop doubles every list item and the inner loop evens out the list with moving any number larger than 9 up the stack. Mean execution time: 5 ms

Recursive C# translation of the F# version

```private List<int> EvenOut(IEnumerable<int> numbers, int overflow)
{
Func<IEnumerable<int>, bool> empty = list =>
{
var enumerator = list.GetEnumerator();
return !enumerator.MoveNext();
};
```if (empty(numbers))
{
if (overflow &gt; 0)
return new List&lt;int&gt; { overflow };

return new List&lt;int&gt;();
}

var n = (overflow + head) % 10;
var newOverflow = (overflow + head) / 10;

var result = EvenOut(numbers.Skip(1), newOverflow);
result.Insert(0, n);
return result;
```
}

private IEnumerable<int> Calc(IEnumerable<int> numbers, int exp)
{
if (exp == 1)
return numbers;
```return Calc(EvenOut(numbers.Select(n =&gt; n * 2), 0), exp - 1);
```
}

[Test]
public void Pe16()
{
Assert.That(this.Calc(new[] { 2 }, 1000).Sum(), Is.EqualTo(1366));
}```

In order to explain to my friend whettingstone what I do with my F# code I translated it to C#. I was really suprised when I noticed that it took so much longer to execute. Mean execution time: 87235 ms

Conclusion

The F# compiler does some heavy optimizations to our recursion and going from F# to C# one must watch out, and not write pure functional constructs without thinking about the consequences. You could problably rewrite the C# recursive solution to be much faster, but an iterative solution is probably the preferred one here.