Özyinelemeli (Recursive) Fonksiyonlar Nedir?

Özyinelemeli fonksiyonlar, tıpkı matematikteki bileşke fonksiyonlar gibi aynı fonksiyonların iç içe geçtiği durumlardır. Ancak mantığı matematikteki haliyle aynı diyemeyiz. Mantığını 2019 Ulusal Bilgisayar Olimpiyatları’nda sorulmuş olan bir soruyu inceleyerek çözeceğiz. Soruda aşağıdaki kod blokunun çıktısı sorulmuş:

void f(int n) {
   if (n>0){
      f(--n);
      printf("%d " , n);
      f(--n);
}
}
int main() {
   f(4);
}

Kod blokunda bir ‘ f ‘ fonksiyonu tanımlanmış ve içine ‘4’ rakamını yerleştirince nasıl bir çıktı alınacağı sorulmuş. ‘ f ‘ fonksiyonumuz geri döndürülemeyen yani ‘void’ türünde bir fonksiyon. Bu fonksiyonumuzu özyinelemeli (recursive) yapan durum ise kod blokunda gördüğünüz üzere fonksiyonun içinde kendinin aynısından iki tane daha bulunması.

Gelelim sorunun çözümüne. Öncelikle f fonksiyonumuzun içine, yani n değişkeni yerine 4 rakamını yazalım.

void f(4) {
   if (4>0){
      f(--4); // başında -- bulunduğundan bu satır ve sonrasında 4'ü 3 olarak alacağız.
      printf("%d " , 3);
      f(--3);// aynı şekilde rakamın başında -- bulunduğundan dolayı sayımızı bu satır ve sonrasında 2 olarak alacağız.
}
}
int main() {
   f(4);
}

Kod blokunda da gördüğünüz gibi ‘ f(4) ‘ü bulabilmek için ‘ f(3) ‘ ve ‘ f(2) ‘ye ihtiyacımız var. Aynı şekilde ‘n’ değişkeni yerinde 3 ve 2 varmış gibi düşünerek fonksiyonumuzun ne olacağına bakalım.

f(4) = f(3); printf("%d",3); f(2);
f(3) = f(2); printf("%d",2); f(1);
f(2) = f(1); printf("%d",1); f(0);
f(1) = f(0); printf("%d",0); f(-1);
f(0) = ; // baştaki if bloğunun şartını sağlamadığı için f(0)'ın herhangi bir çıktısı bulunmuyor.

‘ f(4) ‘ü bulabilmek için ‘ f(3) ‘ ve ‘ f(2) ‘ye ihtiyacımız vardı, şimdi ise ‘ f(3) ‘ ve ‘ f(2) ‘ nin değerlerini bulabilmek için
‘ f(1) ‘,’ f(0) ‘ gibi farklı değerlere ihtiyacımız var. Bu sonsuz paradoksu sonlandıran nokta ise gördüğünüz gibi ‘if’ koşulu oluyor. ‘n’ değerinin 0’dan büyük olması şartı ortadan kalkınca iç içe geçmiş fonksiyonlarımızı artık çözebiliyor duruma geliyoruz. Fonksiyonun içindeki ‘n’ değeri için verilen 0 ve 0’dan daha küçük değerlerin hiçbir anlam ifade etmediğini anlamış olduk. Artık ‘ f(0) ‘ , ‘ f(-1) ‘ gibi fonksiyonları, ‘n’ değeri pozitif olan fonksiyonlarımızın içinden gönül rahatlığıyla silebiliriz.

f(1) = f(0); printf("%d",0); f(-1);
// artık böyle olacak:
f(1) = printf("%d",0);
// f(1) değerinin ekrana 0 değerini yazdırdığını öğrendik.

‘ f(1) ‘ fonksiyonumuzun artık nasıl bir çıktı vereceğini biliyoruz. Bu durumda ‘ f(2) ‘ fonksiyonun içindeki ‘ f(1) ‘ değerini de anlamlandırabiliriz.

f(2) = f(1); printf("%d",1); f(0);

f(1) fonksiyonunun printf(“%d”,0); çıktısını verdiğini biliyoruz. O zaman yerine yazabiliriz. Ayrıca f(0) yine herhangi bir anlam ifade etmediğinden siliyoruz.

f(2) = printf("%d",0); printf("%d",1);

Artık f(2) fonksiyonunun da ne olduğunu tamamen biliyoruz. Bu durumda f(2)’yi kullanarak f(3)’ü, f(3)’ü -f(2)’yi biliyoruz zaten- kullanarak da f(4)’ün ne olduğunu bulabileceğiz.

Yukarıdaki kod blokunda gördüğünüz üzere fonksiyonların çıktılarını yerlerine yazarak sonuca ulaşabiliyoruz. Bu durumu ‘ f(3) ‘ ve ‘ f(4) ‘ için de yaparak sonuca ulaşalım.

f(1) = printf("%d",0);
f(2) = printf("%d",0); printf("%d",1);

f(1) ve f(2)’nin değerini biliyorduk. Artık f(3) ve f(4)’ün içindeki fonksiyonların yerine çıktılarını yazarak sonuca ulaşabiliyoruz.

f(3) = f(2); printf("%d",2); f(1);

f(3) fonksiyonunun yeni hali ↓

f(3) = printf("%d",0); printf("%d",1); printf("%d",2); printf("%d",0);

f(2) ve f(1) fonksiyonlarının çıktılarını yerlerine yazarak f(3)’ün nasıl bir çıktı vereceğini öğrendik. Artık f(4)’ün ne olduğunu bilmememiz için herhangi bir engel yok.

f(4) = f(3); printf("%d",3); f(2);

// f(4) fonksiyonunun yeni hali ↓

f(4) = printf("%d",0); printf("%d",1); printf("%d",2); printf("%d",0); printf("%d",3); printf("%d",0); printf("%d",1);

‘ f(4) ‘ fonksiyonunun aslında ne olduğunu bulduk. Yani çıktımız ve sorunun cevabı ” 0 1 2 0 3 0 1 “. Başta çok zor bir paradoksa benzese de aslında çok basit bir mantığı var özyinelemeli fonksiyonların. Bu yazıdaki gibi C, algoritma tarzı, özellikle de bilgisayar olimpiyatlarındaki sorularla alakalı derslerin devamı ilgi gösterdiğiniz takdirde gelecektir. Beklemede kalın ?