Есть ли у рекурсивных функций ограничения? например: сколько слоев требуется для функции?

Сделал рекурсивную функцию, которая дает количество терминов в последовательности коллатца с заданным начальным номером, например, это код n = 13:

int collatz(long n,long o)
{
    if (n!=1) {
        if(n%2==0)
            return collatz(n/2,o+1);
        else
            return collatz((n*3)+1,o+1);
    } else
        printf("%ld\t",o);
}
void main()
{
    collatz(13,0);
}

функция работает как положено; однако с некоторыми целыми числами, такими как «n = 113383», что-то переполняется (я думаю) и возвращается:

Process returned -1073741571 (0xC00000FD)   execution time : 4.631 s
Press any key to continue.

Извините за нетехническое объяснение, большое спасибо!


c recursion stack-overflow collatz
person Takelovski    schedule 03.05.2019    source источник
comment
Функция ничего не возвращает для n==1.   -  person mch    schedule 03.05.2019
comment
Ваша функция не return получает значение, когда достигает printf. Вероятно, вам следует return o; вместо того, чтобы печатать значение внутри collatz и печатать результат в вызывающей функции.   -  person Bodo    schedule 03.05.2019
comment
0xC00000FD указывает на переполнение стека. Да, стек имеет конечный размер.   -  person 500 - Internal Server Error    schedule 03.05.2019
comment
включил main() для лучшего понимания функциональности   -  person Takelovski    schedule 03.05.2019
comment
@ 500-InternalServerError Спасибо, хотя моя система относительно мощная, стек статический? означает ли изменение громкости от системы к системе?   -  person Takelovski    schedule 03.05.2019
comment
На самом деле стек увеличивается по запросу от заданного начального размера до заданного максимального размера. Эти размеры обычно определяются компилятором/программистом и записываются в заголовке исполняемого файла.   -  person 500 - Internal Server Error    schedule 03.05.2019
comment
Между прочим: n==1 не только выводит вашу программу из конца функции (что изначально кажется здесь безвредным), но и может вызвать очень странный UB, как описано в этот пост (просто обратите внимание на длину заданного там вопроса и фактическую проблему).   -  person andreee    schedule 03.05.2019

Ответы (2)


arrow_upward
3
arrow_downward

В самом стандарте C нет ограничений на глубину рекурсии. Вы можете вызвать переполнение стека, но размер стека отличается в разных средах. Я думаю, что в Windows 1 МБ, а в Linux 8 МБ. Это также зависит от размера кадра стека для функции, который, в свою очередь, зависит от того, сколько у нее переменных и какого типа.

В вашем случае у вас есть две переменные long, каждая из которых, вероятно, составляет 8 байтов. У вас также есть строка "%ld\t" длиной 5 байт, которая может оказаться в стеке, но я не уверен. Кроме того, у вас есть накладные расходы на два указателя на адрес возврата функции и на предыдущий кадр стека, и каждый из них составляет 8 байтов в 64-битной системе. Таким образом, кадр стека для вашей функции будет примерно 32 байта или около того. Может быть, немного больше. Итак, в системе Linux я предполагаю, что ваша функция рухнет на глубине около 200 000.

Если это проблема, подумайте о том, чтобы переписать функцию в нерекурсивном варианте. Посмотрите на ответ Blaze, как это можно сделать для вашего случая. И как andreee прокомментировал ниже:

Дополнительное примечание: вы можете увеличить размер стека в Linux с помощью ulimit -s (также возможно: ulimit -s неограниченно), а в MSVC вы можете установить флаг компиляции /F, чтобы увеличить размер стека вашей программы. Для MinGW см. эту публикацию.

person klutt    schedule 03.05.2019
comment
Дополнительное примечание: вы можете увеличить размер стека под Linux с помощью ulimit -s <size> (также возможно: ulimit -s unlimited ), а в MSVC можно установить /F <size>/ /STACK:<size> флаг компиляции, чтобы увеличить размер стека вашей программы. Для MinGW см. эту публикацию. - person andreee; 03.05.2019

arrow_upward
2
arrow_downward

Здесь происходит переполнение стека. Это происходит потому, что каждый вызов функции создает новый кадр стека, и если их слишком много, память стека заканчивается. Вы можете исправить это, используя итерацию вместо рекурсии.

Кроме того, long может быть не в состоянии хранить числа, которые производит последовательность Collatz для начального значения 113383 (это не для меня с MSVC). Вместо этого используйте long long, это как минимум 64 бита. В целом это может выглядеть так:

void collatz(long long n)
{
    long o;
    for (o = 0; n > 1; o++) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n * 3 + 1;
    }
    printf("%ld\t", o);
    return;
}

int main()
{
    collatz(113383);
    return 0;
}

Обратите внимание, что вместо рекурсии у нас теперь есть цикл for.

person Blaze    schedule 03.05.2019
comment
Хороший ответ. Я немного улучшил форматирование. Надеюсь, ты не против. - person klutt; 03.05.2019
comment
@Броман Вовсе нет! Спасибо за исправление. Я также ценю ваш ответ, который дает ОП более техническую информацию. - person Blaze; 03.05.2019