Yineleme (Recursion)
Prolog’un en ilgi çekici özelliklerinden birisi yineleme kapasitesidir. Yineleme bir şey kendisi ve sonlandırma koşulu kullanarak tanımlanırsa olur. Faktöriyel tanımı klasik bir örnektir:
- N’in faktöriyeli N kere N-1’in faktöriyeline eşittir.
- Sıfırın faktöriyeli 1’dir.
Faktöriyelin bu tanımı prologda kolayca ifade edilebilir:
faktoriyel(0,1). à gerçek
faktoriyel(N,X) :- M is N-1, à kural
faktoriyel(M,Y),
X is N * Y.
Bu örnekte gerçek kuraldan önce yazılmalıdır. Prolog’da gerçek ve kurallar programdaki yazılış sırasına göre işlem görmektedir. Prolog kuralın içinde faktoriyel(M,Y)’yi bulurken programda yüklemin ilk geçtiği yerden başlayarak çözümü arar. M sıfıra kadar azaltılmaktadır. M sıfır olduğunda “gerçeğe” erişildiği zaman geri dönüş işlemi başlar. Eğer gerçek kuraldan sonra yazılırsa sonsuz döngüye girilir.
Yineleme, programlarıın basit ve kısa olmasını sağladığı için çok kullanışlıdır ama program yazılırken çok dikkatli olmak gerekir. Yineleme yalnız rakam ile değil veri yapıları ile de yaplabilir. Prolog’da veri atom (tek değer) veya liste (çok değer) olabilir. Liste elemanlar kümesidir. Elemanlar; sayı, harf, karakter dizisi hatta liste olabilir.
Liste [ ] içinde ve elemanları virgül ile ayrılmış şekilde yazılır. Aşağııda basit listeler görülmektedir:
- [printer, monitor, mouse, cpu ]
- [123, 45, 667]
- [a, b, c, d, e, f, g]
Liste, elemanlar kümesi olduğu için kesişim, bileşim, fark gibi temel işlemler prologda yapılabilir. Örneğin; X, L litesinin üyesi ise doğru olan üye(X,L) yüklemi prologda aşağıdaki gibi tanımlanabilir:
- uye(X,[X|_]).
- uye(X,[_|L]) :- uye(X,L).
| operatörü listeyi ilk eleman(baş) ve geri kalanı (kuyruk) şeklinde ikiye ayırır. Eğer X listenin ilk elemanı ise 1.satırdaki uye(X,[X|_]) yüklemi doğrudur. Altçizgisi “_” değişkenin değerini dikkate alma anlamındadır. Burada kuyrukta ne olduğuna bakılmamaktadır. Eğer birinci satır yanlış ise ikinci satıra bakılır. Bu satırda listenin ilk elemanı uzaklaştırılarak tekrar ilk elemanın X’e eşit olup olmadığına bakılır.
Not: üye yüklemi prologda “member(X,L)” şeklinde tanımlanmıştır.
Üye yüklemini bir dosyaya yazarak aşağıdaki sorgulamaları yapın:
- uye(a,[b,c,a,d]).
- uye(a,[b,c,d,e]).
- uye(2,[1,2,3,34]).
- uye(2,[1,5,3,34]).
Altküme işlemi de yararlı bir işlemdir. X listesinin tüm elemanları Y listesininde elemanı ise altkume(X,Y) yüklemi doğrudur. Bu problemi çözmemiz için X’in tüm elemanlarının Y’nin de elemanıı olup olmadığına bakmamız gerekir. X listesinde kontrol edilecek eleman yoksa durur aksi takdirde başarısızlıkla (fail) karşılaşılır. Program aşağıdaki şekilde yazılabilir:
- altkume([],_).
- altkume([X|L],Y) :- uye(X,Y), altkume(L,Y).
Burada [] boş kümedir. X’deki tüm elemanlar kontrol edilince 1.satır doğru olur.
Uye yüklemini ve altküme yüklemini aynı dosyaya yazarak aşğıdaki sorgulamaları yapınız:
- altkume([a,b,c],[x,a,g,b,f,c,k]).
- altküme([1,5,10],[10,5,1,4]).
- altküme([1,5,10],[10,5]).