Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 14 down vote accepted

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

share|improve this answer
1  
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. –  Matt Fenwick Jun 27 '13 at 20:08
1  
@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. –  MichaelT Jun 27 '13 at 20:11
add comment

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

share|improve this answer
1  
Are you sure that this is what the OP is asking? As I posted under the other answer, just because the runtime does or doesn't consume stack space in a certain way, doesn't mean the function isn't recursive. –  Matt Fenwick Jun 27 '13 at 20:09
    
@MattFenwick that's actually a great point, in real terms it depends, The F# compiler emitting tail call instructions is maintaining the recursive logic completely, it's just instructing the JIT to execute it in a stack-space-replacing fashion rather than stack-space-growing, however other compilers may literally compile to a loop. (Technically the JIT is compiling to a loop or possibly even loopless fashion if the loop is total up front) –  Jimmy Hoffa Jun 27 '13 at 20:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.