为什么我在计算帕斯卡三角形元素时在递归 C 程序中出现堆栈溢出错误

Question

我正在编写一个 C 程序来计算 Pascular 三角形中的第 （i，j） 个元素即 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 作为 n 和 k（它适用于较小的整数值，如 23 2 或 12 3 作为 n&k）错误即将到来

在虚拟项目中0x003C3D79未处理的异常.exe： 0xC00000FD： 堆栈溢出（参数：0x00000001、0x003D2F70）。

任何帮助不胜感激。

Answer 1

由于您使returnModPascal函数递归，因此每个递归调用的堆栈上都必须有空间。

例如，如果你读123456，你对returnModPascal的调用最终会为n = 123456、n = 123455、n = 123454等分配一个堆栈帧。没有足够的内存。

为了解决这个问题，你将不得不重写你的函数，这样你就不会对更大的输入进行这么多的递归调用。

Answer 2

典型的堆栈限制约为 1000 KB。在 Linux 中，您可以使用

ulimit -a

了解你的（我的大约是 8 MB）。由于无符号长 int 可以上升到（再次，假设 gcc）18446744073709551615（64 位）或 4294967295（32 位）[我可能错了，请参阅您的限制.h]，并且您的一个堆栈帧的大小必须为 2 个单词，因此堆栈溢出迫在眉睫。

编辑：我看到你想要一个替代方案。您是否考虑过使用组合数学？"计算"（i，j）第一项由ⁱC_j。我的意思是实际上不要找到阶乘和乘法，而是抵消所有你可以的项（整数值将始终出现），直到只剩下一个整数序列（数学意义）。使用模块化乘法（mod 1000000007）。阅读有关使用生成器指数的高效模块化乘法的信息。

Answer 3

看看这行代码：

tempans1=returnModPascal(n-1,k);

你在一开始就调用递归函数，这意味着该函数将一直到递归链的最末端，然后才有机会进一步处理输入。因此，如果您使用相对较大的输入（例如 123456）调用此函数，这意味着该函数必须"堆叠"12345 次才能最终评估if条件。

您应该尝试减少输入，或者更好的替代方法是在语句之后递归调用if函数。