Çalıştırılabilir C Dokümanları: özyineleme

Q: C'de özyineleme nedir?

Aynı problemin daha küçük bir sürümünü çözmek için kendisini çağıran bir fonksiyondur. Her özyinelemeli fonksiyonun iki şeye ihtiyacı vardır: özyinelemeden dönen bir temel durum ve ona ölçülebilir biçimde yaklaşan bir özyinelemeli durum. Temel durum olmadan çağrılar hiç bitmez ve program bir yığın taşmasıyla çöker.

Q: C'de faktöriyel fonksiyonu nasıl yazılır?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Temel durum 0 ve 1'i halleder ve her özyinelemeli çağrı ona ulaşana dek n'i bir azaltır. int'in 13!'de taştığını not edin - daha büyük değerler için unsigned long long kullanın.

Q: C'de özyinelemeli Fibonacci neden bu kadar yavaş?

Çünkü fib(n), fib(n-1) ve fib(n-2)'yi çağırır; bunlar da aynı alt problemleri tekrar tekrar yeniden hesaplar - çağrı sayısı üstel büyür, dolayısıyla fib(50) yıllar sürerdi. Onu son iki değeri saklayan bir döngü olarak yeniden yazmak doğrusal ve anlık kılar.

Q: C özyinelemesinde yığın taşmasına ne yol açar?

Her çağrı parametreleri ve yerelleri için bir yığın çerçevesi alır ve yığın yalnızca birkaç megabayttır. Eksik ya da erişilemez bir temel durum, sonsuz özyineleme ve anlık bir çökme demektir; yüz binlerce seviye derine inen doğru özyineleme bile yığını tüketebilir.

Kendisini Çağıran Bir Fonksiyon

Hiçbir şey bir C fonksiyonunun kendisini çağırmasını engellemez. Kendi adı gövdesinin içinde kapsamdadır, dolayısıyla bu geçerlidir:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* kendisini çağırır - ama asla durmaz! */
}

Aynı zamanda bozuktur. Program çökene dek sonsuza, negatif sayılara doğru yazdırır. Eksik olan şey bir temel durumdur: fonksiyonun kendisini çağırmadan döndüğü bir koşul.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* temel durum: dur */
        printf("Kalkis!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* ozyinelemeli durum: daha kucuk bir problem */
}

int main(void) {
    countdown(5);
    return 0;
}

Her özyinelemeli fonksiyonun tam olarak şu iki parçası vardır:

Bir temel durum - doğrudan yanıtlanan, başka çağrı yapmayan en küçük girdi.
Bir özyinelemeli durum - problemi kendisinin kesinlikle daha küçük bir sürümü cinsinden çözer.

"Kesinlikle daha küçük", insanların yanlış yaptığı kısımdır. countdown(n - 1) her çağrıda 0'a doğru ilerler. countdown(n) ilerlemezdi ve n sonsuza dek 1 olabiliyorsa countdown(n / 2) de ilerlemezdi. Her yol problemi küçültmelidir, yoksa temel duruma hiç ulaşılmaz.

Faktöriyel

Standart ilk örnek. n!, n × (n-1) × ... × 1'dir ve 0!, 1 olarak tanımlanır. O tanım zaten özyinelemelidir: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* temel durum: 0! ve 1! ikisi de 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* ozyinelemeli durum */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

Cevabın nasıl birleştirildiğini görmek için factorial(4)'ü izleyin. Çağrılar aşağı iner ve çarpmalar yukarı çıkarken gerçekleşir:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (temel durum)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Temel durum dönene kadar hiçbir şey çarpılmaz. Bekleyen her çağrı kendi n'ini tutarak bekler ki içselleştirmeye değen nokta budur: o bekleyen çağrılar bellek kaplar.

Dönüş tipine dikkat edin. int, 13! civarında taşar ve sessizce yanlış bir sayı üretir - C denetim yapmaz. unsigned long long sizi 20!'ye taşır ve daha ileri götürmez, çünkü 21! 64 biti aşar. Burada sınırlayıcı etmen özyineleme değildir; tiptir.

Temel durum bilerek n == 1 yerine n <= 1 kullanır: factorial(0), 1 olmalıdır ve <= bunu halleder. n == 1 ile factorial(0) çağırmak -1, -2 diye özyinelenir ve asla sonlanmazdı - "apaçık doğru" bir temel durumun bir girdiyi nasıl kaçırabileceğinin güzel bir örneği.

Fibonacci ve Saf Sürümün Neden Bir Tuzak Olduğu

Fibonacci diğer klasiktir: her sayı, 0 ve 1'den başlayarak kendisinden önceki ikisinin toplamıdır. Özyinelemeli tanım kendini yazar.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld cagri)\n", n, result, calls);
    }
    return 0;
}

Çağrı sayılarına bakın. fib(10) 177 çağrı alır; fib(35) neredeyse 30 milyon alır. 5'lik her adım işi yaklaşık on bir kat artırır.

Sebep çağrı ağacında görünürdür. fib(5), fib(4) ve fib(3)'ü çağırır; fib(4), fib(3)'ü tekrar çağırır; ve bunların her biri fib(2)'yi sıfırdan yeniden hesaplar. Hiçbir şey hatırlanmaz, dolayısıyla aynı alt problemler tekrar tekrar çözülür ve çağrı sayısı kabaca 1,6ⁿ gibi büyür. Bu şekilde fib(50) günlerce çalışırdı; fib(100) evrenden uzun yaşardı.

Döngü sürümü son iki değeri saklar ve doğrusaldır:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) anında döner. Ders "özyineleme yavaştır" değildir - örtüşen alt problemler içeren özyinelemenin, cevapları hatırlamadıkça yavaş olduğudur. Sonuçları hesaplarken bir diziye saklayın (belleklendirme) ve özyinelemeli sürüm de doğrusallaşsın.

Çağrı Yığını ve Yığın Taşması

Her fonksiyon çağrısının parametrelerini, yerellerini ve dönülecek adresi tutacak bir yere ihtiyacı vardır. O depolama bir yığın çerçevesidir; çağrı başladığında itilir ve döndüğünde çıkarılır. Özyineleme çerçeveleri üst üste yığar - factorial(1000)'in her biri kendi n'i olan bin çerçevesi aynı anda canlıdır.

Yığın büyük değildir. Tipik bir varsayılan 1-8 MB'dır, dolayısıyla birkaç on bin çerçeve gerçekçi sınırdır ve her çerçeve büyük bir yerel dizi tutuyorsa çok daha azdır. Onu aşın, program ölür:

Segmentation fault (core dumped)

Bu bir yığın taşmasıdır ve birine ulaşmanın iki yolu vardır:

Sonsuz özyineleme - eksik ya da erişilemez bir temel durum. Bu bir hatadır ve çökme anlıktır:

int bad(int n) {
    return bad(n - 1);      /* temel durum yok - saniyenin çok altında çöker */
}

Doğru ama çok derin - bir milyon elemanlı bir liste üzerinde eleman başına bir özyineleme. Mantık doğrudur; yaklaşım yığına sığmaz. Onu bir döngü olarak yeniden yazın ya da derinlik logaritmik olacak şekilde yeniden yapılandırın (ikili arama ve birleştirme sıralamasının yaptığı gibi yarılar üzerinde özyinelemek, bir milyon eleman için yaklaşık 20 derinlik verir).

Bazı derleyiciler kuyruk özyinelemesini - özyinelemeli çağrının fonksiyonun yaptığı en son şey olduğu, ardından bekleyen bir iş olmadığı durumu - tek bir çerçeveyi yeniden kullanan bir döngüye dönüştürebilir. Yukarıdaki countdown kuyruk özyinelemelidir; factorial değildir, çünkü çarpmanın hâlâ çağrı döndükten sonra gerçekleşmesi gerekir. Ama C bu iyileştirmeyi zorunlu kılmaz, dolayısıyla derleyiciye ve bayraklara göre olabilir de olmayabilir de. Yalnızca iyileştirici bir kuyruk çağrısını kaldırdığı için çalışan C'yi asla yazmayın.

Özyinelemenin Gerçekten Kazandığı Yerler

Her özyinelemeli fonksiyon bir döngü olarak yeniden yazılabilir ve basit sayma için döngü apaçık daha iyidir. Özyineleme, verinin kendisi özyinelemeli olduğunda - bir yapı kendisinin daha küçük kopyalarını içerdiğinde - ekmeğini hak eder.

İkili arama temiz bir örnektir: yarıyı ara, sonra onun yarısını.

#include <stdio.h>

/* hedefin indeksini ya da -1 dondurur */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* temel durum: gerisi kalmadi */
    }
    int mid = low + (high - low) / 2;       /* buyuk indekslerde tasmayi onler */

    if (a[mid] == target) {
        return mid;                         /* temel durum: bulundu */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> indeks %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Burada iki temel durum var ki bu normaldir: biri başarı, biri tükenme için. Derinlik yaklaşık log₂(n)'dir, dolayısıyla bir milyar eleman bile yalnızca otuz çerçeve ister.

Özyinelemenin doğal olduğu diğer yerler: bir ağaçta ya da bağlı listede dolaşmak, dizin gezinmesi, iç içe ifadeleri ayrıştırmak ve quicksort ile mergesort gibi böl-ve-yönet sıralamaları. Hepsinde özyinelemeli kod, yerini alan açık yığınlı döngüden hem daha kısa hem daha anlaşılırdır.

Özyineleme mi Döngü mü?

Dongu kullanin        problem dogrusalsa - saymak, toplamak, taramak
Ozyineleme kullanin   veri ic iceyse - agaclar, ic ice yapilar, bol ve yonet
Ozyinelemeyi yazin    derinlik girdi boyutuyla sinirsiz buyuyebiliyorsa yeniden
Asla kullanmayin      alt problemler ortusuyorsa, belleklendirmedikce

İki pratik not. Özyinelemeli çağrılar bir döngü yinelemesinden biraz daha pahalıdır - her seferinde itilip çıkarılacak bir çerçeve - dolayısıyla sıcak, basit döngülerde yinelemeli sürüm bellekte olduğu gibi hızda da kazanır. Ve hata ayıklama farklıdır: derin özyinelemeden gelen bir yığın izi yüzlerce özdeş görünen çerçevedir, dolayısıyla bir şey sonlanmıyorsa girişte parametreyi yazdırın (yukarıdaki calls sayacının yaptığı gibi).

Özyinelemeli Bir Fonksiyon Yazmak: Bir Kontrol Listesi

Önce temel durumu bulun. En küçük girdi nedir ve cevabı nedir? Adlandıramıyorsanız fonksiyon yazılamaz.
Özyinelemeli çağrının çalıştığını varsayın. Onu zihninizde izlemeyin - factorial(n - 1)'in (n-1)! döndüreceğine güvenin ve onu cevaba dönüştüren tek adımı yazın.
Her yolun küçüldüğünü denetleyin. Her özyinelemeli çağrı, 0 ve negatifler dahil her olası girdi için temel duruma doğru ilerlemelidir.
Derinliği denetleyin. Gerçek veride bu kabaca kaç çerçeve derine iner? Binlerce sorunsuzdur; milyonlar değildir.
Örtüşmeyi denetleyin. Aynı alt problem iki kez hesaplanıyorsa belleklendirmeye ya da bir döngüye ihtiyacınız var.

Sıkça Sorulan Sorular

C'de özyineleme nedir?

Aynı problemin daha küçük bir sürümünü çözmek için kendisini çağıran bir fonksiyondur. Her özyinelemeli fonksiyonun iki şeye ihtiyacı vardır: özyinelemeden dönen bir temel durum ve ona ölçülebilir biçimde yaklaşan bir özyinelemeli durum. Temel durum olmadan çağrılar hiç bitmez ve program bir yığın taşmasıyla çöker.

C'de faktöriyel fonksiyonu nasıl yazılır?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Temel durum 0 ve 1'i halleder ve her özyinelemeli çağrı ona ulaşana dek n'i bir azaltır. int'in 13!'de taştığını not edin - daha büyük değerler için unsigned long long kullanın.

C'de özyinelemeli Fibonacci neden bu kadar yavaş?

Çünkü fib(n), fib(n-1) ve fib(n-2)'yi çağırır; bunlar da aynı alt problemleri tekrar tekrar yeniden hesaplar - çağrı sayısı üstel büyür, dolayısıyla fib(50) yıllar sürerdi. Onu son iki değeri saklayan bir döngü olarak yeniden yazmak doğrusal ve anlık kılar.

C özyinelemesinde yığın taşmasına ne yol açar?

Her çağrı parametreleri ve yerelleri için bir yığın çerçevesi alır ve yığın yalnızca birkaç megabayttır. Eksik ya da erişilemez bir temel durum, sonsuz özyineleme ve anlık bir çökme demektir; yüz binlerce seviye derine inen doğru özyineleme bile yığını tüketebilir.

İlgili kavramlar