Cevap.

Sorunun Tarihi:

Rekürsiyon, C'nin ortaya çıkmasından beri desteklenmektedir - bu dilin paradigmasına doğal bir şekilde uygundur ve özellikle ağaçlarla, listelerle, karmaşık ayrıştırma algoritmalarında kompakt çözümler üretmeyi sağlar.

Sorun:

Rekürsiyonun başlıca riskleri, yığının aşırı kullanılma oranı, yığın taşması (stack overflow) olasılığı ve ayrıca performansa (döngüsel uygulama ile karşılaştırıldığında) belirsiz etkidir. C'de çağrıların iç içe geçme derinliğini otomatik olarak kontrol edecek standart bir yöntem yoktur.

Çözüm:

Rekürsiyonu uygulamadan önce, maksimum mümkün iç içe geçme seviyesini değerlendirmek, mümkünse kuyruk rekürsiyonunu kullanmak (derleyici tarafından optimize edilmesi için) ve yığın taşmasına karşı koruma eklemek, örneğin, açık bir rekürsiyon derinliği sayacıyla. Alternatif bir yöntem ise, basit görevler için rekürrent çağrıları döngüsel olanlarla değiştirmektir.

Kod Örneği:

#include <stdio.h>
#define MAX_DEPTH 1000

int factorial(int n, int depth) {
    if (depth > MAX_DEPTH) {
        printf("Hata: maksimum rekürsiyon derinliği aşıldı!\n");
        return -1;
    }
    if (n == 0) return 1;
    return n * factorial(n - 1, depth + 1);
}

int main() {
    printf("%d\n", factorial(5, 0)); // 120
    return 0;
}

Anahtar Özellikler:

Rekürsiyon derinliğini otomatik olarak sınırlandırma garantisi yoktur
Rekürsiyon, yığının tükenebileceği şekilde yığın tüketir
Kuyruk rekürsiyonu, derleyici tarafından optimize edilebilir, ancak her zaman değil

Kandırmaca Soruları.

Eğer iç içe geçen rekürsif bir işlev içinde return işlemi gerçekleştirilirse, yığın temizlenir mi?

Evet, mevcut işlevden çıkıldığında yığın serbest bırakılır. Yığın taşması gerçekleşmediyse, yığında hiçbir "asılı" veri kalmaz.

Rekürsif işlevin gövdesinde statik yerel değişkenler tanımlanabilir mi ve bunlar nasıl davranır?

Tanımlanabilir. Bu tür değişkenler, tüm rekürsif çağrılar için ortak olacak ve çağrılar arasında değerlerini koruyacak, bu da bu davranışı dikkate almazsanız sık sık hatalara yol açacaktır.

C derleyicisi rekürsiyon derinliğini etkiler mi ve bunu sınırlayabilir mi?

Derleyici doğrudan rekürsiyonu sınırlamaz. Rekürsiyon derinliği, işletim sisteminin yığın boyutu veya dış faktörlerle sınırlıdır.

Tipik Hatalar ve Anti-Desenler

Derinlik kontrolü olmadan sınırsız rekürsiyon
Rekürsif işlevin gövdesinde başlatılmamış veya statik yerel değişkenler
Rekürsiyonu, bir döngünün daha kolay ve verimli olduğu yerlerde kullanmak

Hayattan Bir Örnek

Derinlik sınırı olmadan bir arama ağacının rekürsif dolaşımı gerçekleştirilmiştir:

Artıları:

Kod özlü, okunması kolaydır.

Eksileri:

Ağacın büyük derinliğinde, program yığın taşması hatasıyla sonlanıyordu.

Geliştirilmiş sürümde, bir derinlik sayacı eklenmiş ve büyük ağaç boyutlarında yığın tabanlı dolaşıma geçiş yapılmıştır: