Problem with Tail Recursion in g++

Tail call optimization in C or C++ is extremely limited, and pretty much a lost cause. The reason is that there generally is no safe way to tail-call from a function that passes a pointer or reference to any local variable (as an argument to the call in question, or in fact any other call in the same function) -- which of course is happening all over the place in C/C++ land, and is almost impossible to live without.

The problem you are seeing is probably related: GCC likely compiles returning a struct by actually passing the address of a hidden variable allocated on the caller's stack into which the callee copies it -- which makes it fall into the above scenario.

Try compilling with -O2 instead of -O3.

How do I check if gcc is performing tail-recursion optimization?

well, it doesn't work with O2 anyway. The only thing that seems to work is returning the result object into a reference that is given as a parameter.

but really, it's much easier to just remove the Tail call and use a loop instead. TCO is here to optimize tail call that are found when inlining or when performing agressive unrolling, but you shouldn't attempt to use recursion when handling large values anyway.

I can't get g++ 4.4.0 (under mingw) to perform tail recursion, even on this simple function:

static void f (int x)
  {
  if (x == 0) return ;
  printf ("%p\n", &x) ; // or cout in C++, if you prefer
  f (x - 1) ;
  }

I've tried -O3, -O2, -fno-stack-protector, C and C++ variants. No tail recursion.

I would look at 2 things.

1. The return call in the if statement is going to have a branch target for the else in the stack frame for the current run of the function that needs to be resolved post call (which would mean any TCO attempt would not be able overwrite the executing stack frame thus negating the TCO)

2. The numbers[] array argument is a variable length data structure which could also prevent TCO because in TCO the same stack frame is used in one way or another. If the call is self referencing (like yours) then it will overwrite the stack defined variables (or locally defined) with the values/references of the new call. If the tail call is to another function then it will overwrite the entire stack frame with the new function (in a case where TCO can be done in A => B => C, TCO could make this look like A => C in memory during execution). I would try a pointer.

It has been a couple months since I have built anything in C++ so I didn't run any tests, but I think one/both of those are preventing the optimization.

Try changing your code to:

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);

    if(j >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i, i + 1);
}

edit: removed unnecessary parameter as per comment from asker

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i)
{
    if (numbers[i] + numbers[i+1] == target || i >= (size - 1))
        return gen_Result(i, i+1, true);

    if(i+1 >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i);
}

Support of Tail Call Optimization (TCO) is limited in C/C++.

So, if the code relies on TCO to avoid stack overflow it may be better to rewrite it with a loop. Otherwise some auto test is needed to be sure that the code is optimized.

Typically TCO may be suppressed by:

• passing pointers to objects on stack of recursive function to external functions (in case of C++ also passing such object by reference);
• local object with non-trivial destructor even if the tail recursion is valid (the destructor is called before the tail return statement), for example Why isn't g++ tail call optimizing while gcc is?

Here TCO is confused by returning structure by value. It can be fixed if the result of all recursive calls will be written to the same memory address allocated in other function twoSum (similarly to the answer https://stackoverflow.com/a/30090390/4023446 to Tail-recursion not happening)

struct result
{
    int i;
    int j;
    bool found;
};

struct result gen_Result(int i, int j, bool found)
{
    struct result r;
    r.i = i;
    r.j = j;
    r.found = found;
    return r;
}

struct result* twoSum_Helper(int numbers[], int size, int target,
    int i, int j, struct result* res_)
{
    if (i >= (size - 1)) {
        *res_ = gen_Result(i, j, false);
        return res_;
    }
    if (numbers[i] + numbers[j] == target) {
        *res_ = gen_Result(i, j, true);
        return res_;
    }
    if (j >= size)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2, res_);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1, res_);
}

// Return 2 indexes from numbers that sum up to target.
struct result twoSum(int numbers[], int size, int target)
{
    struct result r;
    return *twoSum_Helper(numbers, size, target, 0, 1, &r);
}

The value of res_ pointer is constant for all recursive calls of twoSum_Helper. It can be seen in the assembly output (the -S flag) that the twoSum_Helper tail recursion is optimized as a loop even with two recursive exit points.

Compile options: g++ -O2 -S (g++ version 4.7.2).

I have heard others complain, that tail recursion is only optimized with gcc and not g++. Could you try using gcc.