Anything like multiple instances of a function

Question

I was going through a code in C for merge sort which is as follow :

void merge(int a[], int low, int mid, int high);

void divide(int a[], int low, int high)
{
 if(low<high) // The array has atleast 2 elements
 {
  int mid = (low+high)/2;
  divide(a, low, mid);     // Recursion chain to sort first half of the array
  divide(a, mid+1, high);  // Recursion chain to sort second half of the array
  merge(a, low, mid, high);
 }
}

void merge(int a[], int low, int mid, int high)
{
 int i, j, k, m = mid-low+1, n = high-mid;
 int first_half[m], second_half[n];
 for(i=0; i<m; i++)  // Extract first half (already sorted)
   first_half[i] = a[low+i];
 for(i=0; i<n; i++)  // Extract second half (already sorted)
   second_half[i] = a[mid+i+1];
 i = j = 0;
 k = low;
 while(i<m || j<n)  // Merge the two halves 
 {
   if(i >= m)
   {
    a[k++] = second_half[j++];
    continue;
   }
   if(j >= n)
   {
    a[k++] = first_half[i++];
    continue;
   }
   if(first_half[i] < second_half[j])
     a[k++] = first_half[i++];
   else
     a[k++] = second_half[j++];
 }
} 

main()
{
 int i, n, a[10];
 printf("How many elements in the array? ");
 scanf("%d", &n);
 printf("Enter array: ");
 for(i=0; i<n; i++)
   scanf("%d", &a[i]);

 divide(a, 0, n-1);

 printf("\nSorted array:  ");
 for(i=0;i<n;i++)
   printf("%d  ",a[i]);
 printf("\n");
}  `enter code here`

Here the function divide is a recursive one , it is calling itself again till a condition is satisfied. But I am confused whether there is any concept like "instances of functions" or "copies of functions " owing to which the value of a variables inside a function being called are independent of its value during a different call made to that function . So , when in this code divide is called again ,will the array "a" being passed as the argument to the function remain the same as it was passed in the initial call to the function or will be the changed version obtained in the previous call ? I guess it shouldn't be the same cause apparently that will make the calls to the function inside the same function pointless . Can someone throw some light on it , whether things like copies or instances of function come into play here ?

Answer 1

C uses call by value. That means that every function call gets the arguments as its own set of values. In your case 3 values will be passed to divide, i.e. a pointer to the array and 2 integers. Any change made to those values are local to the specific function call.

The C standard does not specify how that shall be implemented. The standard only describes how it has to behave.

The most common implementations use a stack to store values local to a function. A stack is a memory area reserved for the program (process/thread) at start up. A stack pointer is used to tell where the current end of the stack is. When a function is called, it increments the stack pointer by the amount of bytes the function needs for holding local variables (and possibly some other stuff like return address, etc). When the function returns, the stack pointer is decremented by the same amount (meaning that all local variable are lost, i.e. out of scope).

So when a function is called recursively, then each call will increment the stack pointer by some amount. When the "condition" is met and the function calls start to return, the stack pointer is again decrement.

So to put it short:

The function code is only present once but the local variables is present on the stack as many times as there are nested function calls.

Note: In the text above I have written increment when the function call is made and decrement when the function returns. It is however implementation defined which direction the stack grows. So it may as well be decrement on calls and increment on returns.

Example code to illustrate:

#include <stdio.h>
 
void foo(int n)
{
    printf("n=%d at address %p\n", n, (void*)&n);
    if (n == 0) return;
    foo(n-1);
}
 
int main(void) {
    foo(5);
    return 0;
}

Output on one specific system:

n=5 at address 0xfff6c220
n=4 at address 0xfff6c200
n=3 at address 0xfff6c1e0
n=2 at address 0xfff6c1c0
n=1 at address 0xfff6c1a0
n=0 at address 0xfff6c180

So this example shows how the local variable n ends on the stack. You can see that on this system n is placed in different memory locations for each function call. You can also see that the distance is 0x20 (32 decimal) which suggest that the stack pointer is changed by 32 for each call. It also shows that the stack grows downwards on this system.

Answer 2

Despite the array syntax (int a[]), only the pointer to the first element of the array is actually passed. So, there are no copies of the original array made during the calls. The pointer will normally be passed in recursive calls and so there will be copies of the pointer.

However, the compiler may (not guaranteed to) substitute the body of divide() in the places where divide() calls itself. And it can do it again in the substituted code. Obviously, without knowing the depth of recursion beforehand, this can't be done infinitely many times (impossible) or too many times (too much code generated). But in may be done like 3 levels deep and then there will be a recursive call for the 4th level (and another 3 without calls, and then a call again and so on). When the compiler substitutes code and eliminates calls, some other optimizations become possible. In our example no copies of the pointer need to be made within the 3 levels of substitution.