Tail-recursion with objects

Question

I have a recursive function that I would like to make tail-recursive. My actual problem is more complex and context-dependent. But the issue I would like to solve is demonstrated with this simple program:

#include <iostream>

struct obj
{
    int n;

    operator int&() { return n; }
};

int tail(obj n)
{
    return tail(obj{ n + 1 > 1000 ? n - 1000 : n + 1 });
}

int main()
{
    tail(obj{ 1 });
}

It seems natural that this is tail-recursive. It is not, though, because the destructor of obj n has to be called each time. At least MSVC13 (edit:) and MSVC15 do not optimize this. If I replace obj with int and change the calls accordingly, it becomes tail-recursive as expected.

My actual question is: Is there an easy way to make this tail-recursive apart from just replacing obj with int? I am aiming for performance benefits, so playing around with heap-allocated memory and new is most likely not helpful.

Answer 1

Since you use a temporary, I assume you don't need the object after the recursive call.

One fairly hackish solution is to allocate an object, pass a pointer to it, and reallocate it before making the recursive call, to which you pass the object you newly constructed.

struct obj
{
    int n;

    operator int&() { return n; }
};

int tail_impl(obj*& n)
{
    int n1 = *n + 1 > 1000 ? *n - 1000 : *n + 1;
    delete n;
    n = new obj{n1};
    return tail_impl(n);
}

int tail(obj n)
{
  obj *n1 = new obj{n};
  auto ret = tail_impl(n1);
  delete n1;
  return ret;
}

int main()
{
    tail(obj{ 1 });
}

I've obviously omitted some crucial exception safety details. However GCC is able to turn tail_impl into a loop, since it is indeed tail recursion.

Answer 2

Short Answer: No.

Longer Answer: You might find a way to achieve this but certainly no easy one. Since tail call optimization is not required by the standard, you can never know for sure if some minor change to your program will make the compiler fail to optimize the code.

Worse, consider what happens when you need to debug your program. The compiler will almost certainly not optimize advanced tail calls with debugger flags, which means that your program will only work correctly in release mode. This will make the program much harder to maintain.

Alternative to tail recursion Just write a loop. It can always be done and it is likely to be much, much less convoluted. It also doesn't use the heap, so the overhead will be much smaller.