Can and do compilers convert recursive logic to equivalent non-recursive logic?

Question

I've been learning F# and it's starting to influence how I think when I'm programming C#. To that end, I have been using recursion when I feel the result improves readability and I can't envision it winding out to a stack overflow.

This leads me to ask whether or not compilers could automatically convert recursive functions to an equivalent non-recursive form?

Answer 1

Yes, some languages and complilers will convert recursive logic to non-recursive logic. This is known as tail call optimization - note that not all recursive calls are tail call optimizible. In this situation, the compiler recognizes a function of the form:

int foo(n) {
  ...
  return bar(n);
}

Here, the language is able to recognize that the result being returned is the result from another function and change a function call with a new stack frame into a jump.

Realize that the classic factorial method:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

is not tail call optimizatable because of the inspection necessary on the return.

To make this tail call optimizeable,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compiling this code with gcc -O2 -S fact.c (the -O2 is necessary to enable the optimization in the compiler, but with more optimizations of -O3 it gets hard for a human to read...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

One can see in segment .L4, the jne rather than a call (which does a subroutine call with a new stack frame).

Please note this was done with C. Tail call optimization in java is hard and depends on the JVM implementation -- tail-recursion + java and tail-recursion + optimization are good tag sets to browse. You may find other JVM languages are able to optimize tail recursion better (try clojure (which requires the recur to tail call optimize), or scala).

Answer 2

Tread carefully.

The answer is yes, but not always, and not all of them. This is a technique that goes by a few different names, but you can find some pretty definitive information here and at wikipedia.

I prefer the name "Tail Call Optimization" but there's others and some people will confuse the term.

That said there are a couple important things to realize:

• To optimize a tail call, the tail call requires parameters that are known at the time the call is made. That means if one of the parameters is a call to the function itself, then it cannot be converted into a loop, because this would require arbitrary nesting of said loop which cannot be expanded at compile time.

• C# does not reliably optimize tail calls. The IL has the instruction to do so which the F# compiler will emit, but the C# compiler will emit it inconsistently, and depending on the JIT situation, the JIT may or may not do it at all. All indications are you should not rely on your tail calls being optimized in C#, the risk of overflow in doing so is significant and real