C fonksiyonları, çalışma yığını (runtime stack) ve özyineleme

Şimdiye kadar her şey main içindeydi. Gerçek programlar fonksiyonlara bölünür: her biri tek bir işi yapar, adı vardır, parametre alır, bir değer döndürür. Bu sayfa fonksiyonların C’deki kurallarını, LC-3’te nasıl çalıştıklarını (çalışma yığını, runtime stack) ve kendini çağıran fonksiyonları (özyineleme, recursion) anlatıyor. Sınavda iki tür soru gelir: “What is printed?” ve “yığını çiz: R5 nerede, parametre hangi offset’te?”.

Fonksiyon tanımı

int square(int x) {      /* dönüş tipi, ad, parametre listesi */
    return x * x;
}

int main(void) {
    int r = square(4);   /* argüman 4 */
    printf("%d\n", r);
    return 0;
}

• Parametre (parameter): fonksiyon tanımındaki değişken (x).
• Argüman (argument): çağrıda verilen değer (4).
• Prototip (prototype): fonksiyon main’den sonra tanımlanacaksa önceden bildirilir: int square(int x);.
• void dönüş tipi: değer döndürmez.

Değerle çağırma (call by value)

C’de argümanın değeri kopyalanır. Fonksiyon parametresini değiştirirse sadece kendi kopyasını değiştirir.

void swap(int a, int b) { int t = a; a = b; b = t; }

int main(void) {
    int x = 1, y = 2;
    swap(x, y);
    printf("%d %d\n", x, y);
    return 0;
}

1 2

LC-3 düzeyinde açıklaması basit: argümanlar yığına kopyalanır, swap o kopyaları değiştirir, fonksiyon dönünce o bölge yığından atılır. Takas için x ve y’nin adreslerini geçmek gerekir (pointer, 13. hafta).

Kapsam ve ömür

int counter(void) { static int c = 0; c++; return c; }

İlk çağrı 1, ikinci 2, üçüncü 3 döndürür. static olmasa her seferinde 1.

Çalışma yığını (runtime stack)

Her fonksiyon çağrısı için bellekte bir aktivasyon kaydı (activation record ya da stack frame) açılır. Kayıtlar yığın (stack) düzeninde tutulur: son giren ilk çıkar (LIFO). main bir fonksiyon çağırınca onun kaydı main’inkinin üstüne konur; fonksiyon dönünce kaldırılır. Özyinelemenin çalışmasının sebebi budur: her çağrının kendi kaydı, yani kendi n’i vardır.

LC-3 C derleyicisinde:

Yığın düşük adreslere doğru büyür: push = R6’yı bir azalt, sonra yaz.

Aktivasyon kaydının yapısı

düşük adres
            +--------------------+
  R5 - 1 →  | 2. yerel değişken  |
  R5     →  | 1. yerel değişken  |
  R5 + 1    | dynamic link       |  çağıranın R5'i
  R5 + 2    | return address     |  çağıranın R7'si
  R5 + 3    | return value       |
  R5 + 4    | 1. argüman         |  çağıran itti
  R5 + 5    | 2. argüman         |
            +--------------------+
yüksek adres

Çağırma adımları

Çağıran (caller):

1. Argümanları sağdan sola yığına it (böylece 1. argüman tepeye en yakın olur).
2. JSR fonksiyon.
3. Dönüşte tepedeki dönüş değerini oku, dönüş değerini ve argümanları yığından at.

Çağrılan (callee):

1. Dönüş değeri için yer aç (R6 - 1).
2. R7’yi it (dönüş adresi).
3. R5’i it (dynamic link).
4. R5 ← R6 - 1 (yeni çerçeve), yerel değişkenler için yer aç.
5. Gövdeyi çalıştır; yerellere LDR/STR Rx, R5, #-k, argümanlara LDR Rx, R5, #4+k ile eriş.
6. Dönüş değerini R5 + 3’e yaz, yerelleri at, R5 ve R7’yi geri yükle, RET.

Çözümlü örnek: add2(3, 9)

int add2(int a, int b) { int s; s = a + b; return s; }
/* main: r = add2(3, 9); */

Simülatörde, başlangıçta R6 = R5 = x4000. add2’nin içinde s = a + b satırından hemen sonra yığın:

adres   içerik   R5'e göre   anlamı
x3FFA   x000C    R5 + 0      s = 12
x3FFB   x4000    R5 + 1      dynamic link (main'in R5'i)
x3FFC   x300B    R5 + 2      return address (JSR'dan sonraki komut)
x3FFD   x0000    R5 + 3      return value (henüz yazılmadı)
x3FFE   x0003    R5 + 4      a = 3
x3FFF   x0009    R5 + 5      b = 9

R5 = x3FFA, R6 = x3FFA

Gövdenin LC-3 karşılığı:

        LDR  R0, R5, #4     ; a
        LDR  R1, R5, #5     ; b
        ADD  R0, R0, R1
        STR  R0, R5, #0     ; s = a + b

Dönüşten sonra main R0 = 12’yi tepeden okur, R6 tekrar x4000 olur.

Özyineleme (recursion)

Özyinelemeli bir fonksiyonun iki parçası var:

1. Temel durum (base case): özyineleme olmadan cevaplanan küçük durum.
2. Özyinelemeli adım: problemi küçültüp kendini çağırma.

Temel durum yoksa ya da problem küçülmüyorsa yığın taşar (stack overflow).

int fact(int n) {
    if (n <= 1) return 1;        /* temel durum */
    return n * fact(n - 1);      /* küçültülmüş problem */
}

fact(4)
= 4 * fact(3)
= 4 * (3 * fact(2))
= 4 * (3 * (2 * fact(1)))
= 4 * (3 * (2 * 1))
= 24

En derin anda yığında dört fact kaydı ve main’in kaydı vardır.

Basma sırası: önce mi sonra mı?

void p(int n) {
    if (n == 0) return;
    printf("%d ", n);   /* inerken */
    p(n - 1);
    printf("%d ", n);   /* çıkarken */
}

p(3):

3 2 1 1 2 3

Kural: özyinelemeli çağrıdan önceki iş inerken sırayla, sonraki iş yığın açılırken ters sırayla yapılır.

Çağrı ağacı

İki kez kendini çağıran fonksiyonlarda bir ağaç çiz:

                 fib(4)
              /         \
         fib(3)          fib(2)
        /      \         /     \
    fib(2)   fib(1)  fib(1)  fib(0)
    /    \
fib(1) fib(0)

düğüm sayısı = 9 çağrı, fib(4) = 3

fib(5) için 15 çağrı. Aynı alt problemler (fib(2) gibi) tekrar tekrar hesaplanır.

Sık yapılan hatalar

void swap(int a, int b) { int t = a; a = b; b = t; }

int main(void) {
    int x = 1, y = 2;
    swap(x, y);
    printf("%d %d\n", x, y);
    return 0;
}

int f(int x) { x = x * 2; return x + 1; }

int main(void) {
    int a = 5;
    int b = f(a);
    printf("%d %d\n", a, b);
    return 0;
}

int counter(void) { static int c = 0; c++; return c; }
int plain(void) { int c = 0; c++; return c; }

int main(void) {
    counter();
    counter();
    printf("%d %d\n", counter(), plain() + plain());
    return 0;
}

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}
/* in main: */ printf("%d\n", fact(5));

void p(int n) {
    if (n == 0) return;
    printf("%d ", n);
    p(n - 1);
    printf("%d ", n);
}

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

int add2(int a, int b) { int s; s = a + b; return s; }

int dsum(int n) { if (n < 10) return n; return n % 10 + dsum(n / 10); }
int power(int b, int e) { if (e == 0) return 1; return b * power(b, e - 1); }
/* in main: */ printf("%d %d\n", dsum(4705), power(3, 4));

void rev(int n) { if (n == 0) return; printf("%d", n % 10); rev(n / 10); }
void up(int n)  { if (n == 0) return; up(n / 10); printf("%d", n % 10); }
/* in main: */ rev(123); printf(" "); up(123);