Algoritmaya Giriş #8 - Özyinelemeli Fonksiyonlar

 Algoritmaya Giriş serisinde fonksiyonlara giriş yaptıktan sonra sıra bu yapıların oldukça iyi bilinen bir kullanımına geldi. Bu şekilde kullanılmak için yazılan fonksiyonlara "özyinelemeli fonksiyon" veya "kendini çağıran fonksiyon" denir. Aslında adlarından ne olduklarını ve nasıl yazıldıklarını aşağı yukarı tahmin ediyorsunuzdur, ancak bu yazıda sahne tamamen onların, o yüzden onları çok iyi tanıma şansınız olacak :)

Özyinelemeli fonksiyonlar belli bir davranışı belli bir kere tekrarlayabilmek için bir değer üzerinden tekrar kendini çağıran fonksiyonlardır. Aldıkları değer üzerinden belli bir işlem gerçekleştirirler ve bu işlemin sonunda değerin aldığı değişime göre aynı işlemi ya da farklı bir işlemi gerçekleştirmek için kendini yeniden çağırarak başa sarar. Kendisine verilen problemi kendini yeniden çağırarak çözen bu fonksiyonlar, isimlerindeki "öz"yinelemeli kısmını da buradan alır.

Özyinelemeli Fonksiyonların Oluşturulması

Yazının bu başlığında sizlere özyinelemeli bir fonksiyon en basit haliyle nasıl oluşturulur onu anlatacağım. Burada kullanacağım örnek faktöriyel hesaplama olacak. Öncelikle Flowgorithm'imizi açıyoruz ve programımızın başlangıç kısmını aşağıdaki şekilde oluşturuyoruz.

Buradaki "sayi" değişkenimiz bizim faktöriyelini almak istediğimiz tamsayı, o yüzden onu bir Integer olarak tanımlıyoruz. Daha sonra faktöriyel alma fonksiyonunu yazmak için uygulamamızın ekranındaki "Main"in (veya Türkçe kullanıyorsanız "Ana") yanındaki ok tuşundan "Fonksiyon Ekle"ye basıyoruz. Daha sonra fonksiyonumuzu çıkan menüden aşağıdaki şekilde oluşturuyoruz:

Burada parametre olarak tanımladığımız sayi değişkenini girdik. Dönüş tipi olarak da, faktöriyel işleminin sonucu bir tamsayı olduğu için Integer belirledik. Dönüş değişkenine istediğiniz ismi verebilirsiniz, ben burada "faktoriyel" verdim. Karşımıza çıkan boş fonksiyon şu şekilde olacak:

Şimdi özyinelemeli fonksiyonların genel geçer kullanım şeklini uygulamalı olarak görebiliriz. Özyinelemeli fonksiyonlar bir nevi While döngüsü gibidir ve düzgün çalışmaları için bir çıkış koşulu barındırmaları gerekir. Bu koşul da fonksiyon içerisinde bir if bloğu ile sağlanır. Faktöriyel fonksiyonlarında faktöriyeli alınacak sayı 1 ve 1'den küçükse sonuç her daim 1'dir, aksi takdirde o sayıdan 1'e doğru birer birer azalacak şekilde tüm doğal sayıların çarpımıdır. Dolayısıyla bizim bu örnekteki koşul yapımız aşağıdaki şekilde oluşacaktır:

Burada sayi değişkeninin 1'den küçük eşit olması çıkış koşuludur ve programımız faktoriyel değişkenine 1 değerini atayıp direk olarak programdan çıkacaktır. Ancak sayi değişkeni en az 2 olduğunda programımız faktoriyel değişkenine sayi değişkenini ve faktoriyel fonksiyonuna bu değişkenin bir eksiğini parametre olarak verdiğimizde elde ettiğimiz sonuç ortaya çıkacaktır. Bir fonksiyonu özyinelemeli yapan yer de tam olarak budur. Bunu daha iyi görebilmek için Step (>|) tuşuna tekrarlı olarak basarak programı adım adım ilerletin ve faktoriyel(sayi) fonksiyonuna gelin. Programımız faktoriyel değişkenini tanımladıktan sonra sayi <= 1 koşulunu kontrol edecek ve koşul yanlış olduğu sürece "Yanlış" okundan ilerleyecektir. faktoriyel = sayi * faktoriyel(sayi-1) bloğuna geldikten sonra Step (>|) butonuna bastıktan sonra programımızın imleci yeniden Integer faktoriyel bloğuna gidecek, bu şekilde fonksiyon kendi üzerinden yeniden çağırılmış olacaktır.

Programınız fonksiyonu girdiğiniz sayı kadar sefer baştan başlattıktan sonra en son sayi değişkeni 1 olacağı için "True" okundan ilerleyip "Return" bloğuna gidecektir. Hemen ardından da bir o kadar kez faktoriyel = sayi * faktoriyel(sayi-1) bloğundan ilerleyip döndürme bloğuna ilerleyecektir. Bunun sebebi aslında bir fonksiyonun özyinelenmesinin o fonksiyonun içinde olmasından dolayı bir nevi o fonksiyonun kendi içinde başka bir akış oluşturmasıdır diyebiliriz. Örneğin faktoriyel(3) fonksiyonunda faktoriyel(2)'yi çağırarak özyineleme yaptıysanız faktoriyel(2)'nin akış şeması bir nevi faktoriyel(3)'ün akış şemasına dahil olur. faktoriyel(2) de faktoriyel(1)'i çağırdığında faktoriyel(1)'in akış şeması faktoriyel(2)'ye dahil olur. faktoriyel(1) döndüğünde faktoriyel(2) devam eder, o da döndüğünde faktoriyel(3) devam eder.

Bunu biraz daha hızlı şekilde görmek için programınızın çalışma hızını şuradan ayarlayabilirsiniz.

Burada işaretli olan butona tıkladıktan sonra dört farklı hız seviyesi arasından seçim yapabiliyorsunuz, bu sayede programınızın çalışmasını adım adım izleme şansınız oluyor. Zamandan kazanmanız ve anlamanız arasındaki dengeyi kurmak açısından "Orta" hızı seçmeniz sizin için çok daha iyi olacaktır.

Divide and Conquer (Böl-Parçala-Yönet) Algoritmaları

Özyinelemeli fonksiyonların kullanıldığı bir algoritma türü "Divide and Conquer" algoritmalarıdır. Bu algoritmalar belli bir problemi parçalara ayırarak çözmek için kullanılır ve bu tür bir algoritmanın kullanılmadığı ancak aynı problemi çözen algoritmalara göre performans artışı gösterebilmektedir. Buna en basit örnek bir diziyi ikiye ayırıp elemanlarını toplama işlemi verilebilir. Peki böyle bir algoritmaya neden ihtiyaç var?

Bu tür algoritmalar, kullanıldıkları probleme göre:

• Zaman karmaşıklığını azaltabilir
• Algoritmanın etkinliğini arttırır
• Multi-threading ile programın daha da hızlı çalıştırılmasını sağlayabilir

Bu açıdan Divide and Conquer algoritmaları bir performans geliştirmesi mahiyetinde düşünülebilir. Karmaşık verilerle yaptığınız işlemin kalitesini ve hızını arttırarak büyük ölçekli uygulamalarda önemli performans artışına sebep olabilirler. Bu açıdan edinilmesi iyi bir algoritma yeteneği olarak karşımıza çıkmaktadır Böl-Parçala-Yönet Algoritmaları.

Bu başlıkta yazacağım örnek ilk paragrafta örneğini verdiğim dizi elemanları toplama uygulaması. 1, 3, 7, 9, 4 ve 5 değerlerini tutan altı elemanlı bir dizimiz olsun ve biz bu dizinin elemanlar toplamını bulalım. Programımızın başlangıç kısmı şu şekilde oluşturulur:

İlgili fonksiyonumuz olan calculateRecursive ana programımızdaki Output bloğundan çağırılacaktır. Fonksiyonumuza eklediğimiz tam sayı dönen calculateRecursive fonksiyonumuz da aşağıdaki şekilde oluşturulmuştur.

Bu fonksiyonumuz argüman olarak bir tam sayı dizisi (arr), ilk index (start) ve son index (end) alır. Dönüş değişkeni olan sum da bütün işlemler bittikten sonra döndürülür. calculateRecursive fonksiyonumuzun bitmiş hali de aşağıdaki şekildedir:

Bu fonksiyonumuz özyinelemeli fonksiyon mantığıyla yazılmıştır ancak önceki örneğimizden biraz farklı bir şekilde özyineleme özelliğini kullanmaktadır. Bu fonksiyonun çıkış koşulu başlangıç indeksinin son indekse eşit olmasıdır ki burada dizinin başlangıç indeksi döndürülür. Aksi takdirde fonksiyonun çalışma gidişatı şu şekildedir:

• Dizi ortadan ikiye bölünür ve sol parçası alınır.
• Bu sol parça sürekli olarak soldan bölünür, ta ki son bölümde tek bir eleman kalıncaya dek. Aynı şekilde sağdan da yine son bölümde tek bir eleman kalıncaya dek bölünür.
• Sonra ana dizinin sağ parçası yine sol parçası gibi, önce soldan sonra sağdan tek eleman kalıncaya dek bölünür.
• Bölünen her parça sollu ve sağlı olarak toplanır ve sumLeft ile sumRight değişkenlerine atanır.
• En son ana calculateRecursive fonksiyonuna gelindiğinde bütün sol ve sağ parçaların toplamı elde edilmiş olur ve bu parçaların toplamı toplanıp toplam sonuç olarak döndürülür.

Verdiğimiz örnek dolayısıyla sonuç 29 çıkacaktır.

Fonksiyonlar konusu ikinci yazısıyla bu şekildeydi. Fonksiyonların ne olduğu, nasıl kullanıldığı, nasıl parametre aldığı ve bu parametreleri nasıl kullandığı, değer döndürmesi ve bu fonksiyonların özyinelemeli çağırılması konularını işledik. Artık tam anlamıyla dallanıp budaklanan algoritmalar yazmanızı sağlayacak bilgiye ve yeteneğe sahip olduğunuzu ümit ediyorum. Bir sonraki yazıda programlama dünyası için hayati bir öneme sahip olan dosya işlemlerine geçiyor olacağım. İyi kodlamalar :)