C ++ рекурсия выходит без видимой причины

Question

Я написал функцию, используя рекурсию. Во время тестирования выяснилось, что функция убита без какой-либо очевидной причины, а рекурсия все еще работает.

Чтобы проверить это, я написал бесконечную рекурсию.

На моем ПК эта функция закрывается примерно через 2 секунды, а последний выходной сигнал составляет около 327400. Последний номер не всегда одинаков.

Я использую Ubuntu Lucid Lynx, компилятор GCC и Eclipse в качестве IDE. Если у кого-то есть идея, в чем заключается проблема и как я могу предотвратить выход из программы, я был бы очень рад.

#include <iostream>

void rek(double x){
    std::cout << x << std::endl;
    rek(x + 1);
}

int main(int argc, char **argv) {
    rek(1);
}

Answer 1

Скорее всего, вы переполняете стек, и в этот момент ваша программа будет уничтожена. Глубина стека всегда будет ограничивать сумму, которую вы можете получить, и если вы достигаете этого предела, это означает, что ваш алгоритм должен измениться.

Answer 2

Я думаю, вы правы, ожидая, что код будет работать вечно, как объяснено в

Как проверить, выполняет ли gcc оптимизацию хвостовой рекурсии?

ваш код должен работать вечно, если gcc выполняет хвостовую рекурсию. На моей машине это выглядит так: -O3 фактически заставляет gcc генерировать хвостовые вызовы и фактически выравнивать стек. : -)

Полагаю, вы установили флаг оптимизации на O2 или O3.

Answer 3

Вы вызываете переполнение стека (из-за недостатка места в стеке), потому что вы не предоставили условие выхода.

Answer 4

Если вы хотите избежать переполнения стека с помощью бесконечной рекурсии, вам, к сожалению, придется углубиться в какую-то сборку, чтобы изменить стек так, чтобы новая запись активации не постоянно помещалась в стек, что после какая-то точка вызовет переполнение. Поскольку вы делаете рекурсивный вызов в конце функции, он вызывается в других языках, где рекурсия популярна (т. Е. В Lisp, Scheme, Haskell и т. Д.), Для оптимизации с помощью trail-call. Это предотвращает переполнение стека, в основном превращая хвостовой вызов в цикл. Это будет примерно так в C (примечание: я использую встроенную сборку с gcc на x86, и я изменил ваши аргументы на int с double, чтобы упростить сборку. Также я изменил на C с C ++, чтобы избежать искажения имен имен функций. Наконец, "\ n \ t" в конце каждого оператора не является фактической командой сборки, но требуется для встроенной сборки в gcc):

#include <stdio.h>

void rek(int x)
{
    printf("Value for x: %d\n", x);

    //we now duplicate the equvalent of `rek(x+1);` with tail-call optimization

    __asm("movl 8(%ebp), %eax\n\t"   //get the value of x off the stack
          "incl %eax\n\t"            //add 1 to the value of x
          "movl 4(%ebp), %ecx\n\t"   //save the return address on the stack
          "movl (%ebp), %edx\n\t"    //save the caller's activation record base pointer
          "addl $12, %ebp\n\t"       //erase the activation record
          "movl %ebp, %esp\n\t"      //reset the stack pointer
          "pushl %eax\n\t"           //push the new value of x on the stack for function call
          "pushl %ecx\n\t"           //push the return value back to the caller (i.e., main()) on the stack
          "movl %edx, %ebp\n\t"      //restore the old value of the caller's stack base pointer
          "jmp rek\n\t");            //jump to the start of rek()
}

int main()
{
    rek(1);
    printf("Finished call\n");  //<== we never get here

    return 0;
}

Скомпилированный с gcc 4.4.3 в Ubuntu 10.04, он работал «бесконечно» в бесконечном цикле без переполнения стека, где, как и без оптимизации хвостового вызова, он довольно быстро падал с ошибкой сегментации. Из комментариев в разделе __asm видно, как пространство записи активации стека «перерабатывается», чтобы каждый новый вызов не занимал пространство в стеке. Это включает в себя сохранение значений ключей в старой записи активации (базовый указатель записи активации предыдущего абонента и адрес возврата) и их восстановление, но с изменением аргументов для следующего рекурсивного вызова функции.

И снова, другие языки, в основном функциональные языки, выполняют оптимизацию хвостового вызова в качестве базовой функции языка. Так что рекурсивная функция хвостового вызова в Scheme / Lisp / etc. не будет переполнять стек, поскольку этот тип манипуляции со стеком выполняется для вас скрытно, когда новый вызов функции выполняется как последний оператор существующей функции.

Answer 5

Это забавно, говорить о переполнении стека на stackoverflow.com.;) Стек вызовов ограничен (вы можете настроить его в настройках проекта), но в какой-то момент, когда у вас будут бесконечные вызовы цикла, он будет превышен, и ваша программа завершится.

Answer 6

Ожидаете ли вы, что это будет работать вечно?

Не будет. В какой-то момент у вас закончится стек.

Answer 7

Каждый рекурсивный метод должен реализовывать условие выхода, в противном случае вы получите переполнение стека и программа прекратит работу.

В вашем случае нет условия для параметра, который вы передаете функции, следовательно,он работает вечно и в конечном итоге падает.

Answer 8

Итак, вы определили бесконечную рекурсию и переполнение стека, что убивает ваше приложение.Если вы действительно хотите напечатать все числа;затем используйте цикл.

int main(...)
{
   double x = 1;
   while (true)
   {
       std:cout << x << std::endl;
       x += 1;
   }
 }