4

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.

Improve this question
12
  • Easiest way: get a better compiler, yours is outdated anyway... Commented Dec 30, 2016 at 13:49
  • msvc15 does not do it, either Commented Dec 30, 2016 at 13:51
  • 1
    How do you expect this tail recursion to terminate? Commented Dec 30, 2016 at 14:04
  • 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? Commented Dec 30, 2016 at 14:13
  • @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 Commented Dec 30, 2016 at 14:48

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

thank you! your answer is more straight to the point, StoryTeller's is more helpful in most cases, though, which is why I gave the flag to him. I hope this is understandable
Well... the useful thing would be to write a loop instead. I completely forgot to mention that in my answer, so I have added it now. :-)
Also a good thought, thank you. Sadly, I cannot upvote once again
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.

Improve this answer

4 Comments

Great idea, indeed! However, I indeed need the object not be changed. My true story is that I have parts that ought to be tail-recursive and others that do not... Maybe, your solution can be used anyways, I would still be looking for a non-reference solution - if there is any
How does the tail_impl recursion end?
@0x499602D2 - It doesn't, like in the OP's post. They use the infinite recursion to test if the code is replaced by a loop. If it doesn't, a stack overflow occurs.
Since there does not seem to be a better solution, I'll mark it as solved. Tail recursion might add significant benefits and passing objects by value is no bizarre use-case, so I hope this will be improved in future C++ compilers

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.