1

I wanted to see the impact of tail recursion optimization and want to write simple factorial function in a tail recursion optimized way. Is it possible to do this in the code without compiler supporting it?

Prince John Wesley
  • 62,492
  • 12
  • 87
  • 94
madu
  • 5,232
  • 14
  • 56
  • 96

2 Answers2

3

The compiler does the optimization. So it is not possible to test it without compiler support.

The only way to do this in code is to replace the recursion by iteration (but then of course you lose the recursion).

Stephan
  • 4,187
  • 1
  • 21
  • 33
  • Thank you. So compilers supporting tail recursion optimization automatically converts normal Factorial function in to an interation or do we manually need to provide the function? For example, a tail recursive version on Factorial will have the Factorial(value, accu) function (http://stackoverflow.com/questions/310974/what-is-tail-call-optimization). Basically, does the compiler automatically does it or we need to code it in such a way for the compiler to be able to do the optimization? Thank you. – madu Oct 05 '11 at 07:17
  • @madu g++ does tail recursion optimization automatically; you don't have to change the way you write the code (at least in simple cases like factorial). That's not the case for all compilers, however. – James Kanze Oct 05 '11 at 07:52
2

Tail recursion optimization turns functions with tail recursion property into iteration, to do it without compiler support, you have to do the recursion -> iteration manually. Note that you may lose readability of your code (recursive functions tend to be shorter and easier to understand) and need a lot of code change (thus turning your brains inside out). If I need to do this, I usually put the original recursive function in a comment above the converted iterative version.

LeleDumbo
  • 9,192
  • 4
  • 24
  • 38
  • 1
    *thus turning your brains inside out* which is a good exercise :) – Matthieu M. Oct 05 '11 at 06:56
  • It's also possible to write the iterative version in a way which makes it look as much as possible like the recursive version and thus be about as easy to understand. Basically put either a label or `while(1)` at the top of the function. Replace each tail-recursive call `return myfunc(arg1, arg2 ... arg_n);` with one line per function parameter to set the new value (if it differs from the current value), followed by a `goto` or `continue`. More changes needed if the function isn't simply tail-recursive, but those same changes are needed if the compiler optimizes only simple tail-recursion. – Steve Jessop Oct 05 '11 at 08:50