info

[pdk123]

In the following c code, the num_elements is gobal.
But if i make it as local and return , it gives strange value just before return it becomes '0' ...can anybody explain why ?

int num_elements =0;
//generates a psuedo-random integer between min and max
int randint(int min, int max)
{
    if (min>max)
    {
        return max+int((min-max+1)*rand()/(RAND_MAX+1.0));
    }
    else
    {
        return min+int((max-min+1)*rand()/(RAND_MAX+1.0));
    }
} 

unsigned int sample(unsigned int m, unsigned int n, unsigned int *set)
{
	unsigned int t, i;
	unsigned int j,l;

	if (m==0)
		return 0;
	else
	{
		l=sample(m-1, n-1, set);
      
		t = randint(1,n);
         
		if(num_elements !=0)
		{
		   for (i=0; i <num_elements; i++)
		   {
		      if ( t == set[i])
		      {
		       	/* add t to s */
			     set[num_elements] = t;
		      }
		      else
		      {
			     /* add to n to s; */
			     set[num_elements] = n;
			     break;
		      } 
		   }
		}
		else
		{
			set[num_elements] = t;
		}

	}
	    j= num_elements++;
        printf("%d", num_elements);
		return j;
}

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned int a = 2, b=4;
	unsigned int set[10];
	num_elements=0;
    sample(a, b, set);

	printf("%d", num_elements);

	Sleep(10000);

	return 0;
}

[Narue]

In your current code you declare num_elements both in the global scope, and locally within main. When multiple variables from different scopes have the same identifier, the one from the most local scope will be used. So the num_elements in main is hiding the global num_elements. sample does indeed work with the global num_elements, but when printing the value, main uses the local num_elements, which is never given any value other than 0.

Here's a program that might make it more clear what's happening:

#include <stdio.h>

int foo = 1;

int main ( void )
{
  int foo = 2;

  {
    int foo = 3;

    /* Prints the most local foo (3) */
    printf ( "%d\n", foo );
  }

  /* Prints the most local foo (2) */
  printf ( "%d\n", foo );

  return 0;
}

[pdk123]

Thanks a lot for the reply.

But let me rephrase, i never define num_elements globally.

Lets say the following code, (which i modified), can you please comment on what is wrong with the following code ?

//generates a psuedo-random integer between min and max
int randint(int min, int max)
{
    if (min>max)
    {
        return max+int((min-max+1)*rand()/(RAND_MAX+1.0));
    }
    else
    {
        return min+int((max-min+1)*rand()/(RAND_MAX+1.0));
    }
} 

unsigned int sample(unsigned int m, unsigned int n, unsigned int *set)
{
	unsigned int t, i, num_elements =0;
	unsigned int j,l;

	if (m==0)
		return 0;
	else
	{
		l=sample(m-1, n-1, set);
      
		t = randint(1,n);
         
		if(num_elements !=0)
		{
		   for (i=0; i <num_elements; i++)
		   {
		      if ( t == set[i])
		      {
		       	/* add t to s */
			     set[num_elements] = t;
		      }
		      else
		      {
			     /* add to n to s; */
			     set[num_elements] = n;
			     break;
		      } 
		   }
		}
		else
		{
			set[num_elements] = t;
		}

	}
	    num_elements++;
		return num_elements;
}

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned int a = 2, b=4;
	unsigned int set[10];
	unsigned int num=0;
    num= sample(a, b, set);

	printf("%d", num);

	Sleep(10000);

	return 0;
}

[pdk123]

Note this is a recursive function..

[pdk123]

num_elements is returned by each call recursively, will it be overwritten with the local variable , from the calling function ?

[Narue]

>num_elements is returned by each call recursively, will it be
>overwritten with the local variable , from the calling function ?
num_elements is returned, but never modified except to increment once. sample will always return 1.

[pdk123]

sorry for my bit basic question..
may be i simplify my question further...

int function (int m, int n, int *set)
{
int num_elements =0;

if (m==0)
return 0;
else
{
num_elements = function(m-1, n-1, set);
num_elements++;
}
return num_elements;
}

main(){

printf ( "%d", function(2,2) );

}

I have a basic doubt:

First function will be called with m=2, n=2,
then it again recursively calls itself with m=1, n=1,
then it again recursively calls itself with m=0, n=0,
which returns 0, which will be assigned to num_elements.

later m=1, n=1, executes rest of the code, incrementing, num_elements and returning 1.

when it returns '1' to calling function local varible whose name is also "num-elements", will it be replaced by 1 ? or will it be masked by '0'

[Narue]

If you don't understand recursion, trace through the execution and see exactly what happens:

#include <stdio.h>

int function ( int m, int n )
{
  int num_elements = 0;

  printf ( "Entering function with m == %d, n == %d\n", m, n );

  if ( m == 0 ) {
    printf ( "m == 0, returning 0\n" );
    return 0;
  }
  else {
    num_elements = function ( m - 1, n - 1 );
    printf ( "Setting num_elements to %d\n", num_elements );
    num_elements++;
    printf ( "Incrementing num_elements to %d\n", num_elements );
  }

  printf ( "Returning num_elements as %d\n", num_elements );

  return num_elements;
}

int main ( void )
{
  printf ( "Final value: %d\n", function ( 2, 2 ) );

  return 0;
}

[pdk123]

i understand recursion, By basic doubt is , since num_elements is stored in stack,(as it is local varible), will it be updated when we call the function and return value(which is also stored on stack) needs to update the local variable in the calling function....i have compiled and run. and it works fine. But i got this basic doubt....when i tried to think in terms on storage .

[Narue]

>i understand recursion, [but my] basic doubt is <blah blah>
That doubt is precisely why I don't believe you understand recursion. So why don't you explain how recursion works to me, using a common stack-based implementation and in the process I'll help you clear up any "doubts" I see.

[pdk123]

ok,
lets say m=2, n=2 => calls m=1, n=1 => m=0,n=0 which returns num_elements =0

control comes to fn m=1, n=1, num_elements get incremented and returned.

control comes to m=2, n=2, num_elements get incremented and returned.

[Narue]

>lets say m=2, n=2 => calls m=1, n=1 => m=0,n=0 which returns num_elements =0
>control comes to fn m=1, n=1, num_elements get incremented and returned.
>control comes to m=2, n=2, num_elements get incremented and returned.
That vaguely describes what happens, but not how it happens. Do you know what a stack frame is? What about how local variables work? Your question suggests that you don't realize each recursive call gets its own completely separate copy of the local variables.

[pdk123]

yes, i know a bit abt , how local variables are stored.

lets say m=2, n=2 => calls m=1, n=1 => m=0,n=0 which returns num_elements =0 . In the instance when m=2, n=2, fn called, they are local varibales and all of them are pushed to stack along with num_elements =0; Then calls the instance m=1, n=1, again in this instance of the function, m and n and num-elements are pushed to stack and which in turn calls the m=0, n=0. Here m, n and num-elemnts are local varibales and returns '0' to the calling function. Then the calling function retrieves the stack for the local varibales ( m,n and num-elements) and updates the local varible with the return value '0'. Then increments num_elements and returns it to the calling function. This function where m=2, n=2, and num_elements are local varibales are retrieved from the stack. and return value is updated to the local variable, num_elements. i.e 1. Then it gets incremented to '2'.

control comes to fn m=1, n=1, num_elements get incremented and returned.

control comes to m=2, n=2, num_elements get incremented and returned.