Все как несколько экземпляров функции

Question

я собирался через код в C для сортировки слияния, которая выглядит следующим образом:

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` 

Здесь функция деление является рекурсивным, то называющим себя снова, пока условие выполняется. Но я смущен тем, существует ли какое-либо понятие типа «экземпляров функций» или «копий функций», вследствие чего значение переменных внутри вызываемой функции не зависит от его значения во время другого вызова этой функции. Таким образом, когда в этом коде деление вызывается снова, будет передан массив «a» в качестве аргумента функции, который был передан при первоначальном вызове функции или будет измененной версией, полученной в предыдущем вызове ? Я полагаю, что это не должно быть той же самой причиной, которая, по-видимому, вызовет функцию внутри той же функции бессмысленно. Может ли кто-то проливать на него какой-то свет, могут ли такие вещи, как копии или экземпляры функции?

Answer 1

C использует вызов по значению. Это означает, что каждый вызов функции получает аргументы как собственный набор значений. В вашем случае 3 значения будут переданы в divide, то есть указатель на массив и 2 целых числа. Любое изменение, внесенное в эти значения, является локальным для конкретного вызова функции.

В стандарте C не указывается, как это должно быть реализовано. Стандарт описывает только то, как он должен себя вести.

Наиболее распространенные реализации используют стек для хранения значений, локальных для функции. Стек - это область памяти, зарезервированная для программы (процесс/поток) при запуске. Указатель стека используется, чтобы указать, где находится текущий конец стека. Когда вызывается функция, она увеличивает указатель стека на количество байтов, необходимых функции для хранения локальных переменных (и, возможно, некоторых других вещей, таких как обратный адрес и т. Д.). Когда функция возвращается, указатель стека уменьшается на одну и ту же величину (что означает, что вся локальная переменная теряется, то есть выходит за рамки).

Поэтому, когда функция вызывается рекурсивно, каждый вызов увеличивает указатель стека на некоторую величину. Когда «условие» выполняется и вызовы функции начинают возвращаться, указатель стека снова уменьшается.

Так положить его коротким:

Функциональный код присутствует только один раз, а локальные переменные присутствуют в стеке столько раз, сколько есть вложенные вызовы функций.

Примечание: в тексте выше я написал приращение, когда вызов функции выполнен и уменьшается при возврате функции. Тем не менее, реализация определена в том направлении, в котором растет стек. Таким образом, это может также быть декремент на звонки и увеличение при возврате.

Пример кода для иллюстрации:

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

Выход на одной конкретной системы:

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 

Так что этот пример показывает, как локальная переменная n заканчивается в стеке. Вы можете видеть, что в этой системе n размещается в разных ячейках памяти для каждого вызова функции. Вы также можете видеть, что расстояние равно 0x20 (32 десятичных числа), которые предполагают, что указатель стека изменяется на 32 для каждого вызова. Он также показывает, что стек растет вниз по этой системе.

Answer 2

Несмотря на синтаксис массива (int a[]), фактически передается только указатель на первый элемент массива. Таким образом, во время вызовов нет копий исходного массива. Указатель обычно передается в рекурсивных вызовах, поэтому будут копии указателя.

Однако компилятор может (не гарантируется) заменить тело divide() в тех местах, где сам звонит divide(). И он может сделать это снова в замененном коде. Очевидно, что, не зная глубины рекурсии заранее, это невозможно сделать бесконечно много раз (невозможно) или слишком много раз (слишком много кода генерируется). Но это может быть сделано как 3 уровня в глубину, а затем будет рекурсивный вызов для 4-го уровня (и еще 3 без вызовов, а затем снова вызов и т. Д.). Когда компилятор заменяет код и устраняет вызовы, возможны некоторые другие оптимизации. В нашем примере не нужно копировать указатель в 3 уровня замещения.