g++, std::string and tail recursion

[m4ster_r0shi]

I have two code snippets that involve recursive manipulation of std::strings.

code snippet 1

#include <iostream>
#include <string>

void print_stuff(int min_n, int max_n)
{
    struct local
    {
        static void build_stuff(
                        int min_n, int max_n, int cur_n,
                        int cur_c, int max_c, bool inc,
                        std::string & ret)
        {
            if (cur_c == max_c)
            {
                if (cur_n == min_n && !inc) return;

                ret += '\n';

                if (cur_n == max_n) inc = false;

                int new_n = inc ? cur_n + 1 : cur_n - 1;

                return build_stuff(
                        min_n, max_n, new_n,
                        0, new_n, inc, ret);
            }

            ret += '0' + cur_n;

            return build_stuff(
                    min_n, max_n, cur_n,
                    cur_c + 1, max_c, inc, ret);
        }
    };

    std::string stuff;

    local::build_stuff(
            min_n, max_n, min_n,
            0, min_n, true, stuff);

    std::cout << stuff;
}

int main()
{
    print_stuff(1,9);

    return 0;
}

code snippet 2

#include <iostream>
#include <string>

void insert_comma(const std::string & integer, std::string & result)
{
    struct local
    {
        static void insert_comma_helper(const std::string & integer,
                                        std::string & result)
        {
            int size = integer.size();

            if (size < 4) { result = integer + ',' + result; return; }

            return insert_comma_helper(
                    integer.substr(0, size - 3),
                    result = integer.substr(size - 3, 3) + ',' + result);
        }
    };

    int size = integer.size();

    if (size < 4) { result = integer; return; }

    return local::insert_comma_helper(
            integer.substr(0, size - 3),
            result = integer.substr(size - 3, 3));
}

int main()
{
    std::string integer;
    std::string result;

    while (true)
    {
        getline(std::cin,integer);
        if (integer == "") break;

        insert_comma(integer, result);
        std::cout << result << std::endl;
    }

    return 0;
}

When I compile with -O3, g++ performs tail call optimization on the former, but not on the latter.
Why does this happen? Is there anything I can do to get tail call optimization on the second one?

[Celtrix]

Optimization depends on your logic g++/gcc tries to optimize it with as little generated assembly as possible but if your logic demands that things must be done in a certain order it might not be possible to break it down any further without changing the logic. what im say is that while it may be possible to optimize one solution another might not be because the way gcc/g++ generates assembly it must think the way your code does so if you couldn't write a simpler version of it neither could gcc/g++.

this site explains it better than i can
http://www.azillionmonkeys.com/qed/asmexample.html

take a look at the generated gcc/g++ code its usually on the left then compare it to the one that was written by paul

[mike_2000_17]

The problem is this line:

return insert_comma_helper(
           integer.substr(0, size - 3),
           result = integer.substr(size - 3, 3) + ',' + result);

The reason why tail recursion is not done in this case is because you have temporary string variables in your recursive function call. That is the main difference between the two code snippets (the first only has integer temporaries). This makes a big difference because the std::string requires destruction, which will be executed just _after_ the return-statement, rendering tail-recursion impossible.

There are certainly ways in which you could allow tail-recursion in this case. The main idea is that all things that are not part of the parameter list or of primitive types should be already destructed (or not created yet) at the point of the return-statements. This can often be implemented using scopes and adding working variables as parameters to the function (which is OK most of the time since you usually write a recursive function as a local function (like you did) or some other form of "hidden" helper function, and thus, it doesn't affect the actual interface function that a user would call). With that in mind, I would think that this solution might have a much better chance of qualifying as a tail-recursion:

//here, I break const-correctness, but it does no harm since the function is
// local (the original "integer" can be copied by caller), and this gives 
// you a free string variable that doesn't ever get destructed in all recursions.
void insert_comma_helper(std::string& integer,
                         std::string& result)
{
  int size = integer.size();

  if (size < 4) { 
    result = integer + ',' + result; //this is OK, temporaries are destructed before 'return'. 
    return; 
  }

  result = integer.substr(size - 3, 3) + ',' + result;
  integer = integer.substr(0, size - 3);

  //at this point, no more temporary variables should exist, ready to tail-call.
  return insert_comma_helper(integer, result);
}

[m4ster_r0shi]

Awesome. It looks like it doesn't like temporaries that require ctor/dtor call at all, no matter where they appear. So, I tried this:

#include <iostream>
#include <string>

void insert_comma(std::string integer, std::string & result)
{
    struct local
    {
        static void insert_comma_helper(std::string & integer, std::string & result, std::string & temp)
        {
            int size = integer.size();

            if (size < 4)
            {
                temp = integer; temp += ','; temp += result;

                result = temp;

                return;
            }

            temp = integer; temp.erase(0, size - 3); temp += ','; temp += result;

            result = temp;

            integer.erase(size - 3, 3);

            return insert_comma_helper(integer, result, temp);
        }
    };

    int size = integer.size();

    if (size < 4) { result = integer; return; }

    std::string temp = integer; temp.erase(0, size - 3);

    result = temp;

    integer.erase(size - 3, 3);

    return local::insert_comma_helper(integer, result, temp);
}

int main()
{
    std::string integer;
    std::string result;

    while (true)
    {
        getline(std::cin,integer);
        if (integer == "") break;

        insert_comma(integer, result);
        std::cout << result << std::endl;
    }

    return 0;
}

Now, not only the optimization is made, but there is no symbol for the helper function; it's merged with its caller.
Though, the code now is somewhat complicated... Meh, I should just use a loop.

Thanks again!