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

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?

• tail call optimization is a good if basic example but that only works if you have `return recursecall(args);` for the recursion, the more complex stuff is possible by creating an explicit stack and winding it down, but I doubt they will – ratchet freak Jun 27 '13 at 20:02
• @ratchet freak: Recursion does not mean "computation that is using a stack". – Giorgio Jun 27 '13 at 21:59
• @Giorgio I know but a stack is the easiest way to convert recursion to a loop – ratchet freak Jun 27 '13 at 23:20

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).

• I'm not sure that this is what the OP is asking. Just because the runtime does or doesn't consume stack space in a certain way, doesn't mean the function isn't recursive. – user39685 Jun 27 '13 at 20:08
• @MattFenwick How do you mean? "This leads me to ask whether or not compilers could automatically convert recursive functions to an equivalent non-recursive form" - the answer is "yes under certain conditions". The conditions are demonstrated, and there are some gotcha's in certain other popular languages with tail call optimizations that I mentioned. – user40980 Jun 27 '13 at 20:11