How to simulate "tail recursion" in C#?

Question

No. Net, I know it is possible to make cause calls because the compiler of F#, when optimizing code, transforms a function with tail recursion into a function with a loop, thus avoiding stack bursts. To make it clearer I will use as an example a factorial function.

In F#:

let rec fatorial_iter n r : int64 =
  if n <= 1L then r else fatorial_iter (n - 1L) (n * r)

let fatorial n = fatorial_iter n 1L

This prevents stack bursts as the stack will always be the same size after optimization. Illustrating a call to fatorial(5):

fatorial(5, 1)   -> fatorial(5 - 1, 5 * 1)  ->
fatorial(4, 5)   -> fatorial(4 - 1, 4 * 5)  ->
fatorial(3, 20)  -> fatorial(3 - 1, 3 * 20) ->
fatorial(2, 60)  -> fatorial(2 - 1, 2 * 60) ->
fatorial(1, 120) -> 120

If we try to do this in C#, we can also make the recursive call on the tail, as in this example:

static long Fatorial(int n, long r = 1) {
    return n <= 1 ? r : Fatorial(n - 1, n * r);
}

But the C# compiler cannot optimize this code (at least not yet, using . Net Framework 4.5).

Is there any way, without losing the immutability of the code, to make this function cannot cause a stack overflow?

Answer 1

As others have mentioned, C# doesn’t give you a surety that a tail recursion will be optimized. I’m a huge fan of tail recursion but I think you’re focusing a little bit on the wrong direction - I think flexible flow control is a more crucial point of tail recursion than immutability and it changes the way we approach this problem a little bit.

In a simple loop case with your example, using tail recursion turns out to be as changeable and low-level as writing your code using Gotos. At each step you have to update the accumulator and the accountant and say that you will make a jump back to the beginning of the loop.

  int acc = 1;
  int i = N;
loop:
   if (i >= 0) {
     // finge que pode usar atribuição múltipla estilo Python
     i, acc = i-1, acc*i; goto loop;
   } else {
     return acc;
   }

The only advantage of tail recursion compared to Gotos is the assignment of more than one variable in one step and that the compiler will let you know if you forget to tell the new value to one of the variables. Anyway, a for loop ends up being more structured and high level, since you just need to take care of logic to update the product and the counter update and the Gotos comes for free. It is somewhat similar to programming using a fold instead of tail recursion

int acc = 1;
for (int i = N; i >= 0; i--){
   acc *= i;
}

Only tail recursion doesn’t just serve to make simple loops in which a function calls itself. The part where tail recursion makes the most difference is when you have more than one mutually recursive function. A forced example is this state machine defined in Haskell:

par 0 = True
par n = impar (n-1)

impar 0 = False
impar m = par (m-1)

The equivalent of this without recursion of cause is a state machine:

  int n;
  int m;
par:
  if (n == 0) {
    return true;
  } else {
    m = n - 1;
    goto impar;
  }
impar:
  if (n == 0) {
    return false;
  } else {
    n = m - 1;
    goto par;
  }

However in this version all functions have to be combined in a code snippet only, which hurts the encapsulation. For example, we need to declare all parameter variables at the top, which makes it possible for them to be used in the wrong place.

In addition, tail recursion is also present when we call a function that has been passed to us as a parameter. This is equivalent to a computed drop and cannot be translated into a static loop.

In the latter two cases it is when the language support for tail recursion is most needed. If you have to do something equivalent, the closest will be to use a "trampoline" pattern, but it is inefficient and quite boring to use.

Answer 2

This type of optimization is present only in 64-bit JIT in Release mode.

Test your x64 code in Release mode and Stackoverflow will no longer occur.

And of course, never trust a JIT optimization. You don’t know which framework, platform, or architecture your code will run on.

Code tested here:

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(Fatorial(2000000));
    }

    static long Fatorial(int n, long r = 1)
    {
        return n <= 1 ? r : Fatorial(n - 1, n * r);
    }
}

Answer 3

In this case the only guaranteed way not to cause a StackOverflow would be to use a non-rerecursive algorithm. For example:

static long Fatorial(int n) 
{
    long r = 1;

    for (; n > 1; n--)
    {
        r *= n;
    }

    return r;
}

Answer 4

I may be talking nonsense right now, but I believe Jcködel’s answer is incorrect.

I believe that you only managed to compute such a large factorial number precisely because you are using the 64-bit architecture and not because of any optimization.

NOTE: I had to post as an answer, I can’t "comment" on other answers yet, I don’t have enough reputation.