Doing tail recursion in C++

Question

My function can be written much more simply if I do a tail call recursion (as opposed to a for (;;)...break loop). Yet I'm afraid I'll have performance problems if the compiler fails to optimize it, especially because it will be compiled by the end user.

Is there a way to tell the compiler "Make sure you optimize this tail call, or else give me an error" (e.g. Scala supports this)
If the compiler can't optimize it away, what are the performance limits? About how many tail calls can I expect to be able to run without breaking the stack?

UPDATE:

Compilers are gcc and MSVC.

Typically, I'll expect about a dozen tail calls. But the extreme case could have thousands. Platform is a typical low end laptop (eg Core i3 or i5).

How many tail calls are you expecting roughly? What compilers are you targeting? — Guvante, May 26 '15 at 23:31
If it is really tail recursive, and you need to know for sure the compiler will optimize away the recursion, it should be simple to code it as a loop yourself. — jxh, May 26 '15 at 23:34
See [this answer](http://stackoverflow.com/a/30090390/315052) to find some other reasons that a tail recursive function may not be optimized away. — jxh, May 26 '15 at 23:38

score 9 · Answer 1 · answered May 26 '15 at 23:42

No, there is no way to tell a compiler that tail recursion is required. Some compilers (none that I'm aware of) may support implementation-specific annotations, but that requires the user to use that specific compiler. Some other compilers, in some modes, intentionally never support tail calls, because they can provide a better debugging experience by not supporting tail calls. The user may be using such a compiler.

The allowed recursion depth is highly program-, function- and implementation-dependent, and no sensible numbers can be given for it. Given a specific platform, you can probably determine the default stack size, investigate the frame size for one particular compiler on that platform, and do a simple division to get a rough estimate of how many nested calls you can have.

I recommend rewriting it in a way that makes it clear to the reader what is happening, but does not rely on a compiler optimising tail calls. Although hated, the goto statement can be very useful for this.

Take a simple tail-recursive bit-counting function:

int bitcount(unsigned int n, int acc = 0) {
  if (n == 0)
    return acc;

  return bitcount(n >> 1, acc + (n & 1));
}

It can be trivially rewritten as

int bitcount(unsigned int n, int acc = 0) {
tail_recurse:
  if (n == 0)
    return acc;

  // tail return bitcount(n >> 1, acc + (n & 1));
  acc += n & 1;
  n = n >> 1;
  goto tail_recurse;
}

Of course this is a simple version that is trivially rewritten to avoid recursion entirely, and probably shouldn't even be implemented manually, but the specific transformation I've used here is one that you can apply to any function where tail recursion is possible and where you need tail recursion. The comment should make sure that the reader can still easily spot what's going on.

The example could also be easily written with while loop to make it even clearer, but it's nice to see not all are against goto when applicable. — Sami Kuhmonen, May 27 '15 at 01:33
@SamiKuhmonen Yeah, that's what I meant by "trivially rewritten to avoid recursion entirely". Thanks. :) — , May 27 '15 at 01:57

score 1 · Answer 2 · answered May 27 '15 at 08:42

With GCC you can add a runtime check using the backtrace() function:

#include <cassert>
#include <iostream>
#include <execinfo.h>

size_t start;

size_t stack_frames()
{
  void *array[16];
  size_t size = backtrace(array, 16);

  // std::cout << "Obtained " << size << " stack frames.\n";
  return size;
}

bool missing_tail()
{
  return stack_frames() > start + 2;
}

int bitcount(unsigned int n, int acc = 0)
{
  assert(!missing_tail());

  if (n == 0)
    return acc;

  return bitcount(n >> 1, acc + (n & 1));
}

int main()
{
  start = stack_frames();

  std::cout << bitcount(10) << '\n';

  return 0;
}

When compiled with a optimization level lower than -O2 (no tail recursion optimization) you get an assertion failure.

Doing tail recursion in C++

2 Answers2