Yazan : Şadi Evren ŞEKER
Fonksiyonel programlamada kullanılan bir fonksiyon tipidir. Buna göre bir özyinelemeli (recursive) fonksiyon kendisini her çağırmada mevcut işlenmiş değeri geçirir. Bu sayede derleyici (compiler) özyineleme yığınını (recursion stack) hafızada tutmak yerine basit bir parametre değiştirme işlemi ile sonucu hesaplayabilir.
Örneğin aşağıda iki farklı faktöriyel hesabı yapan fonksiyon verilmiştir:
Klasik özyineleme fonksiyonu tarzında faktöriyel:
int faktoriyel(int n){
if(n<=0)
return 1;
return n * faktoriyel(n-1);
}
Yukarıda verilen bu fonksiyon örneğin 3! hesaplamak için çalıştırıldığı zaman aşağıdakine benzer bir çağırma yığını (call stack) oluşur:
call faktoriyel (3)
call 3 * faktoriyel (2)
call 2 * faktoriyel (1)
call 1 * faktoriyel (0)
return 1
return 1
return 2
return 6
Görüldüğü üzere öncelikle fonksiyon özyinelemedeki başlangıç durumuna (initial state) kadar indirilmiş ve sonuç buradan çağrıldığı yere kadar geri hesaplanmıştır. Bu işlem sırasında kaç fonksiyon çağırma işlemi yapıldıysa bütün bu fonksiyonlar hafızayı işgal etmiştir. Aynı hesaplama işlemi basit bir değişiklikle daha verimli tutulabilir.
Kuyruk özyinelemeli (birikimsel tarzda) faktöriyel hesabı:
int faktoriyel(int n, int birikim){
if(n<= 0)
return birikim;
return faktoriyel(n-1,birikim*n);
}
Yukarıdaki fonksiyon faktoriyel(3,1) olarak çalıştırıldığında hafızadaki durum aşağıdaki şekildedir:
replace arguments with (3 1), jump to "faktoriyel" replace arguments with (2 3), jump to "faktoriyel" replace arguments with (1 6), jump to "faktoriyel" replace arguments with (0 6), jump to "faktoriyel" return 6
Görüldüğü üzere fonksiyon (3 1) parametreleri ile çalıştırıldığında yeni çağrılacak olan fonksiyonda ilk parametre 1 azalıp 2 olurken ikinci parametre 3 * 1 ile 3 olmaktadır. Bu şekilde ilk parametre her çağrımda 1 azalırken ikinci parametre kendisi ile ilk parametrenin çarpımı olmakta ve en nihayetinde ilk parametre 0 olduğunda ikinci parametrede sonuç birikmiş olmaktadır. Bu durumda sonuç ikinci parametrenin döndürülmesiyle kolayca hesaplanır.
Bu yeni yöntemde dikkat edilirse ilk yönteme göre daha az hafıza kullanılmıştır çünkü fonksiyonların birbirini beklemesi söz konusu değildir. Ayrıca zaman olarak da verimlidir çünkü başlangıç durumu (initial state) ulaşıldıktan sonra hesaplamalar için fonksiyonların geri yüklenmesi gerekmemektedir.