c++ - 为什么我在计算 Pascal 三角形的元素时在递归 C 程序中出现堆栈溢出错误？

Question

我正在编写一个 C 程序来计算 Pascular Triangle 中的第 (i,j) 个元素即 f(n,1) = f(n,n) = n，并且 f(n,k) = f(n-1,k) + f(n-1,k-1) 对于 1 < k < 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)错误来了

Unhandled exception at 0x003C3D79 in DummyProject.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x003D2F70).

感谢任何帮助。

Answer 1

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

例如，如果您读入 123456，您对 returnModPascal 的调用将最终为 n = 123456 分配堆栈帧，n = 123455、n = 123454，依此类推。几乎没有足够的内存。

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