Sayfa 23

“çözüm bulundu”'dan başkası değil-

PROBLEMİN ÇöZül

GEÇEN ZAMAN

BAŞLANGIÇ ŞEKLİ

O kkk Ek * * tk 4 * * 4 4k ** *k 4 *

* * * * * * * * kak

KALA #CCCCCCC

4k * ** * * ** * 4 * * ** 4 *

* * * * * * * KK akk ler. Bunları “sıfır” ve “bir” durumları olarak sembolize edelim. Bir altprogram “bir” durumuyla geri döndüğü zaman o seviyede veya daha alt seviyelerde çözüm bulunmuş demektir. Daha fazla uğraşmasına gerek kalmadan aynı mesajla o da geri döner. Ta ki tümüyle geri çıkılana kadar.

Peki altprogram tümüyle geri döndüğünde (dışarıdan rekursif altprogramı çağıran diğer programa geri dönüldüğünde) bildirilen değer sıfır durumuysa ne olacak? Basitçe görülmektedir ki, böyle bir durumda yapılacak bir şey yoktur. Programımız tüm ihtimalleri denemiş, çözüm bulamamıştır. Bu, programı-

PROBLEMİN ÇöZÜüMÜü

GEÇEN ZAMAN

BAŞLANGIÇ ŞEKLİ

*5 Ek * * ** * bt * * ** * ** &* kt 4 4 4k Ok ak

SANİYE) 1

KKK Ok kk CCCCCCCE* * * * * *ttk * * * *k .* * * tk kkk

* ss. ee RR mızın yetersizliğinden çok labirentin gerçekten de çözümsüz bir iabirent olduğunu gösterir. Kullanıcıya hatası bildirilir ve program bitirilir. Görüldüğü gibi arapsaçına dönecek, çorba gibi karışacak gibi görünen ihtimaller bile dikkatle değerlendirildiğinde çözümleri bulunabiliyor. Artık bu noktada programımızın kesinlikle kusursuz çalışacağına eminiz. Bir adım daha atarak programımızın ilk satırlarını oluşturalım. i) Program X ve Y parametreleriyle çağırılması gerekiyor. ii) Geri dönerken O veya 1 durumu bildiriyor. Programımız ilk satırlarında X, Y noktasında çevresine bakıyor. Gidebileceği nokta tek bir tane ise oraya gidiyor ve çevresine bakma işleminden yeniden başlıyor. Böylece yol tek yönlüyse o yolun sonuna kadar gitmesi sağlanmış oluyor. Burada bazılarımızın dikkatini çekmiş olabilir; programın bir evvelki noktaya geri dönmemesi nasıl sağlanacak? Tek bir çözüm var: Programın geçtiği noktalara iz bırakması ve böylece aynı noktalara bir daha girmemesi. Bu konuyu daha detaylı olarak birazdan bir kere daha döneceğiz. İlk satırlara geri dönelim. Programımızın düz yolda ilerlemesi sağlanmıştı. Diyelim ki bu yol üzerinde hedefe ya da çözüme rastladı; ne yapacak? Gayet basit: Bir durumuna geçerek RETURN emriyle geri dönecek ve müjdeyi üst seviyedeki programlara verecek. Diyelim ki düz yolda giderken yolu tıkandı bu sefer ne yapacak? Bu sefer de sıfır durumuna geçerek üzüntülerini üst seviyedeki programlara bildirecek. Şimdi dördüncü ve en karışık ihtimale geliyoruz; yol çatallaşırsa ne olacak? Zaten RECURSION'i gerektiren durum da bu. Programımız N, Y koordinatlarını yığına atacak ve ihtimallerden birini seçip o yönde bir nokta ilerleyecek ve o ihtimali değerlendirmesi için kendi kendini çağıracak. Geri dönüşte X, Y koordinatlarını yığından geri alacak ve çağırdığı programın gönderdiği durum kodunu kontrol edecek. Şayet durum kodu *bir'se altprogram işi çözmüş demektir. Programımız aynı durum koduyla geri dönecektir. Durum kodu “sıfır” ise alt seviyedeki programın yolu tıkanmış demektir. Bu durumda yapılacak iş girilmiş olan çıkmaz yolun belirlenmesine gelir. Arkasından diğer ihtimallerin değerlendirilmesi programın başındaki “çevresine bakma' işlemine gider. Şimdi geçtiği yola iz bırakma olayına geri dönelim. Başta basit görürakılan iz şu işlere yarayacak. Öncelikle üzerinden geçilen noktaların hazırlanması için gerekli. Hedefi bulma işi bittiğinde ise bırakılmış olan izler çözüm yolunu içerir. Fakat çözüm için gerekli olandan fazlası yani çıkmaz yolları da içerir. Bu çıkmaz yolların esas çözüm yolundan ayırdedilebilir özellikte olması gerekir. O yüzdendir ki sıfır koduyla geri dönen altprogramın bıraktığı izler değiştirilmekte (bir bakıma silinmekte). Bu safha da dikkati çeken bir nokta da her seviyede yürüyen programın bıraktığı iz farklı olursa bir kolaylık sağlanacağı. Böylece değişik seviyelerin izleri daha kolay bulunup drüzeltilebilir. Basit bir mantıksal çıkarım gösterecektir ki çözüm bulunduğu zaman her seviyeye ait bir tek iz olacaktır; bu da çözüme giden izdir. Bunca tartışmadan sonra akla gelen en basit çözüm iz bırakma kodunun seviye (veya yığın göstergeci) ile doğru orantılı veya aynı değerde olmasıdır. Herkesin olayı rahatça takip edebil-