Существует ли какой-либо жесткий проводник на глубине рекурсии в C

Рассматриваемая программа пытается вычислить sum-of-first-n-natural-numbers с помощью recursion. Я знаю, что это можно сделать с помощью простой формулы n*(n+1)/2, но идея здесь заключается в использовании recursion.

Программа выглядит следующим образом:

#include <stdio.h>

unsigned long int add(unsigned long int n)
{
    return (n == 0) ? 0 : n + add(n-1); 
}

int main()
{
    printf("result : %lu \n", add(1000000));
    return 0;
}

Программа хорошо работала для n = 100,000, но когда значение n было увеличено до 1,000,000, это привело к Segmentation fault (core dumped)

Из сообщения gdb было взято следующее.

Program received signal SIGSEGV, Segmentation fault.
0x00000000004004cc in add (n=Cannot access memory at address 0x7fffff7feff8
) at k.c:4

Мой вопрос (ы):

Есть ли какой-либо жесткий проводник на recursion depth в C? или зависит от recursion depth от доступной памяти стека?
Каковы возможные причины, по которым программа получит сигнал reSIGSEGV?

Ответы

Ответ 1

Обычно предел будет размером стека. Каждый раз, когда вы вызываете функцию, определенное количество стека употребляется (обычно зависит от функции). Потребляемая сумма - это стек стека, и она восстанавливается, когда функция возвращается. Размер стека почти почти фиксирован, когда программа запускается, либо из-за того, что она указана операционной системой (и часто настраивается там), либо даже жестко запрограммирована в программе.

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

Не так просто понять, сколько пространства стека требуется для каждого вызова функции, и оно будет подлежать уровню оптимизации компилятора. Дешевый способ сделать это в вашем случае - печатать &n каждый раз при его вызове; n, скорее всего, будет в стеке (тем более, что прогаме нужно принять свой адрес, иначе он может быть в регистре), а расстояние между последующими местоположениями будет указывать размер кадра стека.

Ответ 2

Теоретического предела глубины рекурсии в C. Теорема ограничена тем, что вы выполняете, как правило, ограниченное пространство стека. (Обратите внимание, что стандарт C фактически не требует реализации на основе стека. Я не знаю никаких реализаций реального мира, которые не основаны на стеках, но помните об этом.)

A SIGSEGV может быть вызвано любым количеством вещей, но превышение вашего предела стека является относительно распространенным. Разделение плохой указатель - другое.

Ответ 3

Стандарт C не определяет минимальную поддерживаемую глубину для вызовов функций. Если бы это было так, что в любом случае было бы очень сложно гарантировать, это было бы упомянуто где-то в разделе 5.2.4 Environmental limits.

Ответ 4

1) Ожидается, что потребление стека будет уменьшено и записано как оптимизация хвостовой рекурсии.

gcc -O3 prog.c

#include <stdio.h>

unsigned long long int add(unsigned long int n, unsigned long long int sum){
    return (n == 0) ? sum : add(n-1, n+sum); //tail recursion form
}

int main(){
    printf("result : %llu \n", add(1000000, 0));//OK
    return 0;
}