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.

Easiest way: get a better compiler, yours is outdated anyway... — Marc Glisse
Can you elaborate what you mean by "the destructor of obj n has to be called each time"? Each obj n will be destructed as the stack unwinds from your recursive base case (which is currently absent). When/how do you want the destructor called? — AndyG
@SamVarshavchik I don't. A common test for tail-recursion is to check for stack overflow (the error, not this site :)) which is why I have designed it this way — IceFire

StoryTeller - Unslander Monica StoryTeller - Unslander Monica · Accepted Answer · 2016-12-30T14:12:57

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.

Tail-recursion with objects

2 Answers