C-修复递归中的堆栈溢出

Question

使用分治法找到数组最大值的 C 代码，但它不断抛出异常 “堆栈溢出异常”。帮助将不胜感激!

int a[10];
int find(int l,int h)
{
    int x;

    if(h==0)
    {
        x=0;
        return x;
    }
    else
    {
        if(h==1)
        {
            if(a[0]>a[1])
            {
                x=0;
                return x;
            }
            else
            {
                x=1;
                return x;
            }
        }
        else
        { 
            int mid,z,y;
            mid=(l+h)/2;
            y=find(0,mid);
            z=find(mid+1,h);
            if(a[y]<a[z])
            {
                x=z;
            }
            else
            {
                x=y;
            }
            return x;
        }
    }
}

只有有限的变量，我看不出该函数可以在哪里进入无限递归。

int main()
{
    int i,n,max,min,ans;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    ans=find(0,n-1);

    printf("the maximum element is- %d\n",ans);

    getch();
    return 0;
}

Answer 1

考虑调用 find(0, 2) 的情况。由于 h > 1，您输入第二个 else 子句，mid 为 1。然后在第二次递归调用中，它是find(2, 2)。在此递归调用中，您再次输入第二个 else，因为 h 仍然是 2。但是 mid 也是 2.现在，第一个递归调用转到 find(0, 2)，进入无限循环。

find(0, 2)
   h not 0
       h not 1
           mid = 1
           find(0, 1)
           find(2, 2)
               h not 0
                   h not 1
                       mid = 2
                       find (0, 2) <-- loop

对 h 进行 if 检查的目的似乎是为了防止 mid 计算与 l。如果是这样，那么您可以计算函数顶部的 mid 变量，并将其用作停止条件。

看起来这是一次尝试使用分治法来定位数组a中最大元素的位置。如果是这样，那么您的第一次递归调用应将自身限制在 [l..mid] 范围内，而不是返回到 0。

把它们放在一起:

int find(int l,int h)
{
    int mid = (l+h)/2;

    if (mid == l)
    {
        return (a[l] > a[h]) ? l : h;
    }
    else
    {
        int y = find(l, mid);
        int z = find(mid+1, h);
        return (a[y] > a[z]) ? y : z;
    }
}