Почему я получаю ошибку переполнения стека в программе Рекурсивный C при вычислении элементов паскаль треугольника?

Question

Почему я получаю ошибку переполнения стека в программе Рекурсивный C при вычислении элементов паскаль треугольника?

Я пишу программу на C для вычисления (i, j) -го элемента в Pascular Triangle
т.е. f (n, 1) = f (n, n) = n и f (n, k) = f (n-1, k) + f (n-1, k-1) для 1 < К < N
Мне нужно напечатать значение по модулю 1000000007.
Кодекс следует:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

unsigned long int returnModPascal(unsigned long int n,unsigned long int k);

int main()
{
int t;
unsigned long int ans,n,k;
scanf("%d",&t);
while(t--)
{
scanf("%lu %lu",&n,&k);
ans=returnModPascal(n,k);
printf("%lu",ans);
}

return 0;
}

unsigned long int returnModPascal(unsigned long int n,unsigned long int k)
{
unsigned long int tempans,tempans1,tempans2;
if(k==1 || k==n)
tempans=n;
else
{
tempans1=returnModPascal(n-1,k);
if (tempans1>=1000000007)
tempans1=tempans1%1000000007;
tempans2=returnModPascal(n-1,k-1);
if (tempans2>=1000000007)
tempans2=tempans2%1000000007;
if (tempans1+tempans2>=1000000007)
tempans=tempans1+tempans2-1000000007;
else
tempans=tempans1+tempans2;
}

return tempans;
}

Когда я даю входные данные, например, 123456 3, как п & К
( Он отлично работает с меньшими целочисленными значениями, такими как 23 2 или 12 3 как n&К)
Ошибка идет

Необработанное исключение в 0x003C3D79 в DummyProject.exe: 0xC00000FD:
Переполнение стека (параметры: 0x00000001, 0x003D2F70).

Любая помощь приветствуется.

1

algorithm c++pascals-triangle stack-overflow

Решение

Другие решения

Типичные ограничения стека составляют около 1000 КБ. В Linux вы можете использовать

ulimit -a

знать свое (у меня около 8 МБ). Так как unsigned long int может доходить до (опять же, если предположить, что gcc) 18446744073709551615 (в 64-битной версии) или 4294967295 (в 32-битной версии) [я могу ошибаться, смотрите ваш limit.h], и ваш кадр одного стека должен иметь размер 2 слова переполнение стека довольно неизбежно.

Редактировать: Я вижу, вы хотите альтернативу. Вы рассматривали возможность использования комбинаторики? «Рассчитать» (i, j) -ю запись по ^яС_J. Под этим я подразумеваю, что на самом деле не находят факториалы и умножают, но отменяют все слагаемые, которые вы можете (целое значение всегда будет появляться), пока не останется только последовательность целых чисел (математический смысл). Используйте модульное умножение (мод 1000000007). Читайте об эффективном модульном умножении, используя показатели генератора.

1

Посмотрите на эту строку кода:

tempans1=returnModPascal(n-1,k);

Вы вызываете рекурсивную функцию в самом начале, это означает, что функция будет работать до самого конца цепочки рекурсии, прежде чем она получит какой-либо шанс для дальнейшей обработки ввода. Так что если вы вызываете эту функцию со сравнительно большим вводом, таким как 123456это означает, что функция должна будет «сложиться» 12345 раз, прежде чем она наконец получит оценку if состояние.

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

0

Источник

Accepted Answer

Так как вы сделали свой returnModPascal функция рекурсивная, в стеке должно быть место для каждого рекурсивного вызова.

Например, если вы читаете в 123456Ваш звонок returnModPascal в конечном итоге выделит кадр стека для n = 123456, n = 123455, n = 123454, и так далее. Недостаточно памяти для этого.

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

1