0

Let's say I've got a C function:

unsigned int fact(unsigned int n, unsigned int acc) {
  if(n > 0) return fact(n - 1, n * acc);
  return acc;
}

Is there a way to tell GCC to tail call the recursive function, something like

unsigned int fact(unsigned int n, unsigned int acc) {
  if(n > 0) return __tail_call(fact, n - 1, n * acc);
  return acc;
}

I can make this happen with the -O2 flag passed to the compiler but I'd like the tail call behavior at lower optimization levels so I can compile more quickly.

The actual function is much more complicated, and I want to use TCO because this makes it explicit which state in an iteration can affect future iterations, and which state is reinitialized each iteration.

EDIT: This was flagged as a duplicate of this, but that thread a) doesn't have any answers for GCC, and b) isn't about placing something in the code to force TCO.

kerkeslager
  • 1,364
  • 4
  • 17
  • 34
  • 3
    Apparently something called `-foptimize-sibling-calls` is supposed to "Optimize sibling and tail recursive calls. Enabled at levels -O2, -O3, -Os. ". I haven't tried it. – Lundin Sep 12 '19 at 14:07
  • Oh, nice, thanks Lundin. I'd still like something in the code to do this because it makes it explicit when TCO is necessary for function. But that definitely is a good-enough solution. – kerkeslager Sep 12 '19 at 14:11
  • Possible duplicate of [Is it possible to force tail call optimization on GCC/Clang?](https://stackoverflow.com/questions/4785066/is-it-possible-to-force-tail-call-optimization-on-gcc-clang) –  Sep 12 '19 at 14:14
  • 1
    Well, if there is any doubt whether a recursive function get tail call optimized or not, the correct solution is to replace the recursion with a loop. That goes for recursion in general. – Lundin Sep 12 '19 at 14:15
  • @vaxquis Not a single answer in that link is about gcc though. – Lundin Sep 12 '19 at 14:16
  • @Lundin true, but one good soul answered it in comments, `You can force GCC to provide TCO with a compiler flag: -foptimize-sibling-calls` ; still, the lack of valid answers doesn't prevent this question from being a duplicate, sadly. Giving a bounty would be IMVHO better than re-asking a question again and again and again (using google through GCC docs & SO would be even better, though). As far as using iteration instead of recursion - 100% agree; as long as the problem is not trivial, there's usually little gain in using recursion in non-purely-functional languages IMO. –  Sep 12 '19 at 14:17
  • 1
    @vaxquis I didn't post it as an answer since I haven't used the option before and don't know how useful/buggy that option is. I merely searched for "tail" in RTFM, and behold... – Lundin Sep 12 '19 at 14:19
  • 1
    @vaxquis I would not say that they are duplicates. That other question asks specifically for enforcing TOC. This question asks for how to enable it without using `-O2`. – klutt Sep 12 '19 at 14:26

1 Answers1

2

as per https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html ,

-foptimize-sibling-calls

Optimize sibling and tail recursive calls.

Enabled at levels -O2, -O3, -Os.

further reading here: How do I check if gcc is performing tail-recursion optimization?