C- Fix Stack overflow in Recursion

Question

A code in C to find maximum of an array using divide and conquer but it keeps throwing "stack overflow exception" . Help would be appreciated!

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;
        }
    }
}

There are only limited variables and I don't see where the function can go into an infinite recursion.

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;
}

Does your stopping condition when h is 0 or 1 catch all the cases, if not then it will keep re-cursing infinitely. — Shafik Yaghmour
– Shafik Yaghmour, Commented Jun 19, 2013 at 15:38
There's something odd with your algorithm, consider l = 0 and h = 2: mid = (0+2)/2 = 1; y=find(0,1); z=find(2,2); - Which looks correct but then look what the find(2,2) will do: mid = (2+2)/2 = 2; y=find(0,2); <= We're back at our first test values. z=find(3,2); <= This just looks odd. — Julio Moreno
– Julio Moreno, Commented Jun 19, 2013 at 15:53
I guess this is an attempt to use divide and conquer to calculate finding the maximum element? — jxh
– jxh, Commented Jun 19, 2013 at 16:10

jxh · Accepted Answer · 2013-06-19 16:25:00Z

1

Consider the case where you call find(0, 2). Since h > 1, you enter the second else clause, and mid is 1. Then on the second recursive call, it is to find(2, 2). On this recursive call, you again enter the second else, since h is still 2. But the mid is also 2. Now, the first recursive call goes to find(0, 2), which enters an infinite loop.

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

It seems the intention of the if checks on h is to prevent the mid calculation from being the same as l. If so, then you can calculate the mid variable at the top of your function, and use that as the stopping condition.

It looks like this is an attempt to use divide and conquer to locate the position of the maximum element in the array a. If so, then your first recursive call should restrict itself to the range of [l..mid] instead of going back to 0.

Putting it all together:

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;
    }
}

edited Jun 19, 2013 at 16:25

answered Jun 19, 2013 at 15:42

jxh

70.8k8 gold badges116 silver badges204 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

jxh Over a year ago

@AlexandruBarbarosie: a is a global in the asker's question. It gets initialized by main.

Alexandru Barbarosie Over a year ago

my bad, I was inattentive. deleting my coment.

nitish712 · Accepted Answer · 2013-06-19 15:51:11Z

Here is your code modified, which is running successfully.. The problem is that you weren't checking the difference between l and h but only the value of h...

#include <iostream>
using namespace std;
int a[10];


int find(int l,int h)
{
int x;



if(h-l==0)
{

    return h;
}
else
{


    if(h-l==1)
    {
        if(a[l]>a[l+1])
        {

            return l;
        }
        else
            {

                return l+1;
            }
    }
    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()
{
a[0]=3;
a[1]=7;
a[2]=5;
cout<<find(0,2)<<endl;
return 0;
}

Daniele Milani · Accepted Answer · 2013-06-19 16:01:27Z

0

you're using wrong conditions, try:

first if: if(h==l)

second if: if(h-l==1)

third if:  
      if(a[h]>a[l])  {
         return h;
      } else {
         return l;
      }

edited Jun 19, 2013 at 16:01

answered Jun 19, 2013 at 15:56

Daniele Milani

5632 gold badges7 silver badges26 bronze badges

Collectives™ on Stack Overflow

C- Fix Stack overflow in Recursion

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related