Standart C Programlama Dili

4.4. Özçağrı

Şimdiye kadar başka fonksiyonlar çağıran fonksiyonlara örnekler vermiş bulunuyoruz. Peki, kendini çağıran bir fonksiyona ne dersiniz? Daha önce böyle bir şey görmeyenler için, bu oldukça garip gözükebilir. Herşeyden önce, bir fonksiyon niye kendisini çağırmak zorunda kalsın? İkinci olarak, sonsuz böyle özçağrı sonucu ortaya çıkacak bir döngüden nasıl kaçınabiliriz? Üçüncü olarak da, aynı fonksiyondan birden fazla kopyanın işlek durumda olacağı için, fonksiyonun yerel değişkenlerine ne olur?

Kendini çağıran fonksiyonlara özçağrılı adı verilir. Özçağrılı bir fonksiyonun kendini dolaylı veya dolaysız olarak çağırabileceğine dikkat edin. İkinci durumda, örneğin, f adında bir fonksiyonun g adında başka bir fonksiyonu çağırması, onun da f’yi tekrar çağırması söz konusudur. Her durumda, bir fonksiyonun bir önceki etkinleştirmesi sona ermeden aynı fonksiyonun tekrar çağrılması söz konusudur. Bundan dolayı, özçağrılı fonksiyonlar özel işlem gerektirirler. Özçağrılı fonksiyonları desteklemek için derleyicinin özel bir bellek düzeni kullanması; özçağrılı fonksiyonlar yazmak için ise programcının biraz farklı bir düşünme tarzına sahip olması gerekir.

Yine de, özçağrılı fonksiyonlar o kadar garip değildir ve bazı durumlarda, eşdeğer özçağrılı olmayan fonksiyon yerine özçağrılı olanı kodlamak daha kolaydır. İşte basit ve klasik bir örnek:

Matematikte, faktöriyelin (!) tanımı şöyledir:

n! = n × (n-1) × … × 2 × 1.

Bu tanım, faktöriyel fonksiyonunun algoritmasını açıkça gösterir:

int fakt (int n)
{
  int i = 1;
  while (n)
    i *= n--;
  return i;
}

Faktöriyelin başka bir eşdeğer tanımı da şöyledir:

0! = 1

n! = n × (n-1)!

Bu bir özçağrılı tanımdır. Özçağrılı bir fonksiyonun tanımının temel unsurları şunlardır:

1. Fonksiyonun, bazı argümanlar için, değerini veren bir temel (veya aksiyomlar veya sınır koşulları). Yukarıdaki tanımda ilk deyim buna bir örnektir.
2. Bilinen değerlerden fonksiyonun başka değerlerinin nasıl elde edileceğini gösteren özçağrılı yapı kuralı. Bu da yukarıdaki örneğin ikinci deyiminde gösterilmektedir.

Özçağrılı tanımın, özçağrılı yapı kuralının temel fonksiyon değerleri üzerinde sınırlı sayıda uygulama sonucu sona eren bir yöntem tarif ettiğine dikkat etmemiz gerekir. Her n≥0 için yukarıdaki tanımın doğru olduğu gösterilebilir. Örneğin,

3! = 3 × 2! = 3 × (2 × 1!) = 3 × (2 × (1 × 0!)) = 3 × (2 × (1 × 1)) = 6

Bu kadar matematik yeter. Şimdi de bilgisayarlı gerçek yaşama dönelim. Faktöriyel fonksiyonunun özçağrılı uyarlaması şöyledir:

int fakt (int n)
{
  return (n==0) ? 1 : n*fakt(n-1);
}

Bu da tamamen matematik dilinden bilgisayar diline bir çeviridir. Koşullu işlece dikkat edin. Argümanın, temel deyimin gereğine uyup uymadığı, yani sıfır olup olmadığı, kontrol edilir. Eğer öyle ise, temel fonksiyon değeri, yani 1, döndürülür. Aksi takdirde, özçağrılı yapı kuralı uygulanır. Bu kural (3! örneğinde olduğu gibi) sınırlı sayıda tekrarlanarak doğru değer hesaplanır. Böylece bu kısmın başında sorulan ikinci soruyu yanıtlamış bulunuyoruz: Temel deyim sonsuz sayıda özçağrıya engel olur.

İlk soruya gelince: Bu bir zevk ve verimlilik sorunudur. Bazı programcılar fakt’ın ilk tanımını, bazıları ise ikinci tanımını beğenebilir. Ancak, verimlilik programcılar için önemli (ve nesnel) bir parametredir. Göreceğimiz gibi, özçağrılı tanımlar özçağrılı olmayan (yani yinelemeli olan) tanımlardan daha az verimlidir. Buna rağmen, gerçek programlarda (örneğin bir derleyicinin kendisinde) özçağrılı fonksiyonlar kullanılır, çünkü özçağrılı bir tanım bazen daha zariftir ve anlaşılıp izlenmesi daha kolay olur.

Son sorumuz özçağrılı fonksiyonların nasıl çalıştığı ile ilgili idi. Aşağıdaki atama deyiminin neyle sonuçlanacağını izleyelim.

f2 = fakt(2);

(fakt’ın ikinci uyarlamasını kullanmaktayız.) Aşağıda adım adım ne olduğu verilmektedir:

Sağda yazılan sayılar fakt fonksiyonunun kaç tane işlek kopyasının bulunduğunu gösterir. Üçüncü seferki işleme esnasında n yerel değişkeninin (parametrenin) değeri 0’dır, daha sonra ikinci işlemeye döndüğümüzde, n’nin değeri fonksiyonun o işleme başladığı zamanki değer olur. Bu örnekten, üç n’nin aslında farklı değişken olduğu ortaya çıkar.

Bunu sağlamak için, derleyici programa bir yığıt kullandırır. Bütün auto ve register değişkenleri yığıtta yer alır. Yığıt, bir bayt dizisi şeklinde bitişik bir bellek bölümü ve bununla birlikte bir yığıt göstergesi şeklinde düşünülebilir. Yığıt göstergesi başlangıçta yığıtın başına işaret eder; yığıtın geri kalanı serbest (yani boş) kabul edilir. Özçağrılı olsun olmasın, herhangi bir fonksiyona giriş yapıldığında, o fonksiyonun (static ve dışsal olanlar hariç) yerel değişkenlerinin tamamını tutacak miktarda bayt için yığıtta yer ayrılır; yığıt göstergesi yığıtın geri kalan boşluğunun başını göstereceği şekilde ileriye götürülür. Fonksiyonun bütün (dinamik) yerel değişkenlerine yapılan referanslar yığıtın ayrılmış bu kesimine yapılır. Fonksiyon bitip geri döndüğünde, yerel değişkenler yok olur, çünkü yığıt göstergesi fonksiyon çağrılmadan önce gösterdiği yeri tekrar gösterecek şekilde geriye kaydırılır. Eğer aynı fonksiyondan iki çağrı yapılırsa, yerel değişkenler için iki defa yer ayrılır; üç defa çağrılırsa, yığıtta yerel değişkenlerin üç kopyası yaratılır vs. Aynı fonksiyona birden fazla çağrı yapılmışsa, yerel değişkenlerin sadece son kopyası erişilir olmaktadır. Fonksiyon geri döndüğünde eski değişkenler etkili olmaya başlarlar vs. Bir fonksiyon çağrısı olduğu esnada yürütmenin sürdüğü yer olan dönüş adresi de yığıta itilir. Özçağrılı fonksiyonları desteklemek için bütün bunlar gereklidir. FORTRAN gibi, bazı diller bunu yapmazlar, bundan dolayı bu dillerde özçağrılı fonksiyonlara izin verilmez. Diğer taraftan, C ve Pascal gibi bazı diller özçağrıyı destekler.

Özçağrılı fonksiyonlar yığıttan çok yer harcarlar. Bir int değişkenin 4 bayt, dönüş adresinin de 8 bayt kapladığını varsayalım. Bu durumda, fakt(i) şeklinde bir çağrı yığıtta 12×(i+1) bayt kullanacaktır. Örneğin, fakt(6) için 84 bayta gereksinimimiz olacaktır. Diğer taraftan, fakt’ın yinelemeli (yani ilk verilen) uyarlaması yığıttan 8 (dönüş adresi için) + 4 (n için) + 4 (i için) = 16 bayt kullanacaktır. Özçağrılı fonksiyonun bellek üzerinde daha fazla talepte bulunduğu açıktır. Ayrıca, yerel değişkenlerin ve dönüş adresinin yığıta itilip geri alınması işlemci zamanı da harcar.

Yinelemenin özçağrıdan daha verimli olduğu sonucunu elde edebiliriz. Verimlilikteki bu farkın o kadar fazla olmadığı gerçek örnekler de verebiliriz, bundan dolayı eşdeğer bir yinelemeli algoritma bulamadığınız zaman özçağrı kullanmaya tereddüt etmeyin.