Проблема с хвостовой рекурсией в g ++

Я возился с хвостовыми рекурсивными функциями в C ++, и у меня возникла небольшая проблема с g ++ компилятор.

Следующий код приводит к переполнению стека, когда размер чисел [] превышает пару сотен целых чисел. Изучение ассемблерного кода, сгенерированного g ++ для следующего, показывает, что twoSum_Helper выполняет рекурсивную инструкцию call для самого себя.

Вопрос в том, что из следующего вызывает это?

  • Ошибка в следующем что я упускаю из виду, что предотвращает хвостовую рекурсию.
  • Ошибка с моим использованием g ++.
  • Недостаток в обнаружении хвостовых рекурсивных функций в компиляторе g ++.

Я компилирую с g ++ -O3 -Wall -fno-stack-protector test. c в Windows Vista x64 через MinGW с g ++ 4.5.0.

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;
}

// 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)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1);
}
11
задан Swiss 21 December 2010 в 08:25
поделиться