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

Question

Сделал рекурсивную функцию, которая дает количество терминов в последовательности Коллатца с заданным начальным числом, это код 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.

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

Answer 1

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

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

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

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

Answer 2

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

Кроме того, long может не содержать чисел, которые генерирует последовательность Коллатца, для начального значения 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.