Compilers – Can Compilers Convert Recursive Logic to Non-Recursive Logic?

compilerprogramming-languagesrecursion

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?

Best Answer

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

Related Topic