Why the variable getting same address in recursive calls?

Question

/* Calculating minimum and maximum element out of a list of elements using Recursion
Input: A list of numbers
Output: Minimum and Maximum number 
*/

#include<stdio.h>

int a[8]={6,2,3,9,1,0,11,8},size=8;

int * minmax(int beg,int end)
{
    int res[2],*x,*y,mid;
    printf("%d %d %p:",beg,end,res);
    if(beg==end)
    {
        res[0]=a[beg];
        res[1]=a[beg];  
        return res;    
    }      
    if(end-beg==1)
    {
        if(a[beg]<=a[end])
        {    
            res[0]=a[beg];
            res[1]=a[end];
        }
        else
        {
            res[0]=a[end];
            res[1]=a[beg];
        }
        printf("%d %d",res[0],res[1]);
        printf("\n");
        return res;
    }
    printf("\n");
    mid=(beg+end)/2;    
    x=minmax(beg,mid);
    y=minmax(mid+1,end);         
    if(x[0]<=y[0])
        res[0]=x[0];
    else if(x[0]>y[0])
        res[0]=y[0];   
    if(x[1]<=y[1])
        res[1]=y[1];
    else if(x[1]>y[1])
        res[1]=x[1];
    printf("OUT: %d %d %d %d WIN: %d %d\n",x[0],y[0],x[1],y[1],res[0],res[1]);
    return res;      
}

int main()
{
    int i,j,min,max,*ans;
    ans=minmax(0,size-1);
    printf("Ans=%d %d",ans[0],ans[1]);
    return 0;
}

In the above code to get minimum and maximum element using recursion, the array res is getting same address in successive recursive calls as shown below:

    0 7 0xbfa9cb08:
    0 3 0xbfa9cac8:
    0 1 0xbfa9ca88:2 6
    2 3 0xbfa9ca88:3 9 
    OUT: 3 3 9 9 WIN: 3 9
    4 7 0xbfa9cac8:
    4 5 0xbfa9ca88:0 1 
    6 7 0xbfa9ca88:8 11 
    OUT: 8 8 11 11 WIN: 8 11
    OUT: 8 8 11 11 WIN: 8 11
    Ans=8 11

At function calls minmax(0,1) and minmax(2,3) res gets same address and that is why it creates problem. Similar thing can be observed at minmax(4,5) and minmax(6,7)

Why this is happening and how can I modify the program to get minimum and maximum

Start by not invoking undefined behavior via returning the address of an automatic variable that fell out of scope. res is declared as int res[2] in your function, yet you return res; upon exit. . Any caller that utilizes the result, including yourself via recursion, invokes UB. — WhozCraig
– WhozCraig, Commented May 4, 2015 at 7:56
Calculating Min/Max is not a good problem for recursion! Much better to do this sequentially. — DrKoch
– DrKoch, Commented May 4, 2015 at 8:11
The real problem is that i need to return both min and max element,therefore i used a array and returned its address , though i did mistake as array was local. How to implement it correctly — obmjo
– obmjo, Commented May 4, 2015 at 8:18
I would do void minmax(int beg,int end, int *pMin, int *pMax) and not even use a struct. People seem to have an aversion to returning values through pointers. Is it because they learned Java first? — JS1
– JS1, Commented May 4, 2015 at 8:25

Community · Accepted Answer · 2017-05-23 11:51:02Z

3

You cannot return the address of an automatic variable. As WhozCraig commented, it is undefined behavior. BTW, if you enable all warnings and debug info (e.g. compile with gcc -Wall -Wextra -g if using GCC) you would have been warned.

You should return a struct of two numbers, e.g. declared as

struct myminmax_st {
   int mymin;
   int mymax;
};
struct myminmax_st minmax(int *arr, int beg, int end);

struct myminmax_st 
minmax(int *arr, int beg, int end)
{
   struct myminmax_st res = { INT_MIN, INT_MAX };
   if(beg==end) { 
       res.mymin = arr[beg];
       res.mymax = arr[end];
       return res;
   }

I leave up to you to complete that routine. You need to #include <limits.h> to get INT_MIN & INT_MAX

Notice that on Linux/x86-64 the ABI specifies that returning a struct with two integers is really quick: they are returned in two registers. (This is specific to struct with two scalar fields).

You could instead pass the address of the resulting min and max as formal arguments, as explained in MiteshMS answer (but that would be probably slower on Linux/x86-64 because then you go thru the memory).

Also in C arrays are decayed to pointers, so you cannot return an array (unless you pack it in some struct); you could return a pointer to some array (usually heap-allocated with malloc). In that case -of a heap-allocated array, returned as a pointer- you need some documented convention about who is in charge of free-ing it.

edited May 23, 2017 at 11:51

CommunityBot

11 silver badge

answered May 4, 2015 at 8:23

Basile Starynkevitch

1

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

1 Comment

obmjo Over a year ago

Yes I had struct as an alternative but I wanted to somehow manage it by using array/pointer. Anyway I am using struct now

oxalorg · Accepted Answer · 2015-05-04 08:30:50Z

This is another way to implement the MaxMin algorithm, here the max and min variables are updated with every recursive call.

This way ditches use of array or structure, similar to the way you wanted to code originally.

#include<stdio.h>
#include<stdlib.h>
void maxmin(int a[],int low,int high,int *min,int *max);
int a[8]={6,2,3,9,1,0,11,8}, n=8;

void main()
{
        int i,low,high,max,min;
        low=0;
        high=n-1;
        maxmin(a,low,high,&min,&max);
        printf("Minimum value is %d\n",min);
        printf("Maximum value is %d\n",max);
}

void maxmin(int a[],int low,int high,int *min,int *max)
{
    int mid,min1,max1,min2,max2;
    if(low==high)//For 1 element min and max will be same
    {
        *min=a[low];
        *max=a[high];
    }
    else if(low==high-1)//For two elements
    {
        if(a[low]>a[high])
        {
            *max=a[low];
            *min=a[high];
        }
        else
        {
            *max=a[high];
            *min=a[low];
        }
    }
    else//for more than 2 elements
    {
        mid=(low+high)/2;
        maxmin(a,low,mid,&min1,&max1);//Dividing
        maxmin(a,mid+1,high,&min2,&max2);
        if(min1<min2)//Combining
            *min=min1;
        else
            *min=min2;
        if(max1>max2)
            *max=max1;
        else
            *max=max2;
    }
}

I tried messing around with your code by declaring res[] in different ways. Declaring it as a structure will work as pointed out by Basile in another answer, but you can use the above code to stick to intuitive basic pointers.

Serge Ballesta · Accepted Answer · 2015-05-04 08:40:24Z

-2

C does not allow to return a pointer to an automatic array, because it goes out of scope at the end of the function and is freed before being used.

In that case (recursion), you cannot use static variables either, because all the stacked calls would use same variables.

So, you are left with only 2 way :

let the caller allocate the array and pass it to callee :

void minmax(int beg,int end, int *res)
{
    int x[2], y[2],mid;
    ...
    mid=(beg+end)/2;    
    minmax(beg,mid, x);
    minmax(mid+1,end, y);         
    ...
    printf("OUT: %d %d %d %d WIN: %d %d\n",x[0],y[0],x[1],y[1],res[0],res[1]);
}

int main()
{
    int i,j,min,max;
    int ans[2];
    minmax(0,size-1, ans);
    ...

use dynamic allocation in callee and pass the address of the dynamic allocated array, but then you must free it in caller

int* minmax(int beg,int end)
{
    int *res, *x, *y,mid;
    *res = calloc(2, sizeof(int));
    ...
    mid=(beg+end)/2;    
    x = minmax(beg,mid);
    y = minmax(mid+1,end);         
    ...
    printf("OUT: %d %d %d %d WIN: %d %d\n",x[0],y[0],x[1],y[1],res[0],res[1]);
    free(x);
    free(y);
    return res;
}

int main()
{
    int i,j,min,max;
    int *ans;
    ans=minmax(0,size-1, ans);
    printf("Ans=%d %d",ans[0],ans[1]);
    free(ans);
    return 0;
}

But I forgot a third way given by Basile Starynkevitch's answer : usage of a struct, because you can return an automatic struct.

edited May 4, 2015 at 8:40

answered May 4, 2015 at 8:35

Serge Ballesta

150k13 gold badges137 silver badges267 bronze badges

5 Comments

Basile Starynkevitch Over a year ago

Wrong, the third way (returning a struct) is probably more intuitive, and very probably faster on Linux/x86-64.

Serge Ballesta Over a year ago

@BasileStarynkevitch : I always forget it ... But you are right it is more intuitive for younger than me ...

Basile Starynkevitch Over a year ago

I am probably older than you are (I was born in 1959)

Basile Starynkevitch Over a year ago

Ok, you won. I was born in august 1959. But still, I quite often return small struct-s in C. It is often cheaper and faster (details depend upon the ABI).

Serge Ballesta Over a year ago

@BasileStarynkevitch : Hope I'll remember it next time ! Thanks for the lesson :-)

Collectives™ on Stack Overflow

Why the variable getting same address in recursive calls?

3 Answers 3

1 Comment

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related