c - 我该如何解决这个递归溢出？

Question

#define MIN -2147483648


long max(long x,long y)
{

    long m=x;
    if(y>x)
        m=y;
    return m;
}

long f(int x,int y,int **p)
{

    long result;
    if(x<0||y<0)
        result = MIN;
    else 
        if(x==0&&y==0)
            result = p[0][0];
        else
            result = max(f(x-1,y,p),f(x,y-1,p))+p[x][y];
    return result; 
}

int main(void)
{

    int n;
    scanf("%d",&n);
    int** p = (int **)malloc(n*sizeof(int*));
    for(int i=0;i<n;i++)
    {
        p[i] = (int*)malloc(n*sizeof(int));
        for(int j=0;j<n;j++)    
            scanf("%d",p[i]+j);
    }
    printf("haha\n");
    printf("%ld\n",f(n-1,n-1,p));   
    return 0;
}

当我将 10 分配给 n 时，它运行良好。但是当我将 20 分配给 n 时，没有结果输出。我google了一下，我猜这个错误可能是递归溢出。那么我该如何解决这个问题呢？

Answer 1

您正在进行大量的递归调用。在每个级别，您调用的电话数量是前一级别的两倍。因此，当 N 为 20 时，您将进行 2^20 = 1048576 次函数调用。这需要很长时间。

这些调用中的大多数会一遍又一遍地重新计算相同的值。与其重新计算这些值，不如只计算一次。

这是一个非递归的方法:

long f(int x,int y,int **p)
{
    long **p2;
    int i, j;

    p2 = malloc(sizeof(long *)*(x+1));
    for (i=0;i<=x;i++) {
        p2[i] = malloc(sizeof(long)*(y+1));
        for (j=0;j<=y;j++) {
            if (i==0 && j==0) {
                p2[i][j] = p[i][j];
            } else if (i==0) {
                p2[i][j] = p2[i][j-1] + p[i][j];
            } else if (j==0) {
                p2[i][j] = p2[i-1][j] + p[i][j];
            } else {
                p2[i][j] = max(p2[i-1][j], p2[i][j-1]) + p[i][j];
            }
        }
    }
    return p2[x][y];
}

编辑:

如果您仍然想要递归解决方案，可以执行以下操作。如果尚未计算必要的值，这只会进行递归调用。

long f(int x,int y,int **p)
{
    static long**p2=NULL;
    int i, j;

    if (!p2) {
        p2 = malloc(sizeof(long*)*(x+1));
        for (i=0;i<=x;i++) {
            p2[i] = malloc(sizeof(long)*(y+1));
            for (j=0;j<=y;j++) {
                p2[i][j] = MIN;
            }
        }
    }

    if (x==0 && y==0) {
        p2[x][y] = p[x][y];
    } else if (x==0) {
        if (p2[x][y-1] == MIN) {
            p2[x][y-1] = f(x,y-1,p);
        }
        p2[x][y] = p2[x][y-1] + p[x][y];
    } else if (y==0) {
        if (p2[x-1][y] == MIN) {
            p2[x-1][y] = f(x-1,y,p);
        }
        p2[x][y] = p2[x-1][y] + p[x][y];
    } else {
        if (p2[x][y-1] == MIN) {
            p2[x][y-1] = f(x,y-1,p);
        }
        if (p2[x-1][y] == MIN) {
            p2[x-1][y] = f(x-1,y,p);
        }
        p2[x][y] = max(p2[x-1][y], p2[x][y-1]) + p[x][y];
    }

    return p2[x][y];
}