Yineleme

YİNELEME

Şimdiye kadar tartıştığımız programlar, fonksiyonların birbirlerini hiyerarşik bir düzende çağırdıkları yapısal programlardı. Bazı problem tipleri için fonksiyonların kendi kendilerini çağırması kullanışlı olabilir. Bir yineleme fonksiyonu ( recursive function ), kendi kendini doğrudan ya da bir başka fonksiyon içinden çağıran fonksiyondur. Yineleme, yüksek seviyeli bilgisayar derslerinde uzunca tartışılan karışık bir konudur. Bu ve sonraki kısımda yinelemenin basit örnekleri gösterilecektir. Bu kitap yineleme konusuna, 5. Üniteden 12. üniteye kadar özel bir önem göstermiştir. Kısım 5.15'te bu kitap boyunca yinelemeyle ilgili verilmiş 31 örnek ve alıştırmanın bir özetini bulacaksınız.

Öncelikle yineleme kavramı üstünde duracak daha sonra da yineleme fonksiyonları içeren örnekler inceleyeceğiz. Yinelemeli problem çözme yaklaşımlarının genelde, birden çok elemanı vardır. Yineleme fonksiyonu, bir problemi çözmek için çağrılır. Bu fonksiyon, yalnızca en basit durumu ya da temel durum olarak adlandırılan durumu nasıl çözeceğini bilmektedir. Eğer fonksiyon temel bir durumla çağrılırsa, fonksiyon bir sonuç geri döndürür. Eğer fonksiyon daha karmaşık bir problemle çağrılırsa, fonksiyon problemi iki kavramsal parçaya ayırır : Fonksiyonun nasıl yapacağını bildiği parça ve fonksiyonun nasıl yapacağını bilmediği parça. Yinelemeyi mümkün kılmak için sonraki parça orijinal probleme benzemelidir, fakat orijinal problemin daha basit ya da daha küçük bir versiyonu olmalıdır. Bu yeni problem orijinal probleme benzediğinden, fonksiyon bu küçük problem üzerinde çalışmak için yeni bir kopyasını çağırır. Buna yineleme çağrısı ve de yineleme adımı denir. Yineleme adımı, return anahtar kelimesini içerir çünkü bu adımın sonucu, fonksiyonun problemin nasıl çözeceğini bildiği kısmıyla birleştirilerek, orijinal çağırıcıya döndürülecek
sonucu oluşturur.(orijinal çağırırcı muhtemelen main'dir)

Yineleme adımı fonksiyona yapılan çağrı açıkken, yani henüz çalışması sonlanmadan çalışır. Yineleme adımı daha fazla yineleme çağrısına sebep olabilir. Fonksiyon her problemi bölmeye devam ederken iki kavramsal kısım ile çağrılır. Yinelemeden çıkılabilmesi için , her seferinde fonksiyon kendini problemin biraz daha basit versiyonuyla çağırır. Bu basit ve daha basit problemlerin dizisi en sonunda temel duruma ulaşmalıdır. Bu noktada fonksiyon temel durumu tanır, fonksiyonun bir önceki kopyasına bir sonuç aktarır ve sonuçların döndürüldüğü bir dizi, fonksiyonun orijinal çağrısının en son sonucu main'e döndürmesine kadar yukarıya doğru devam eder. Bütün bunlar, şu ana kadar kullanmaya alıştığımız problem çözme teknikleriyle karşılaştırıldığında oldukça ilginç gelebilir. Aslında, bu sürecin doğal gelmesi için bir çok yineleme programı yazma alıştırması yapmak gerekmektedir. Bu kavramların bir örneği olarak, popüler bir matematik hesaplamasını gerçekleştiren bir yineleme programı yazalım.

Negatif olmayan bir n tamsayısının faktoriyeli, n! biçiminde yazılır (" n faktoriyel" şeklinde okunur) ve

n * (n-1) * (n-2) *......* 1

çarpımı olarak tanımlanır. 1! ve 0! faktoriyel 1 olarak tanımlanmıştır. Örneğin , 5! 120'ye eşit olan 5 * 4 * 3 * 2 * 1 çarpımıdır.

Sıfırdan büyük yada sıfıra eşit bir tamsayının (sayi) faktoriyeli, yineleme olmadan for kullanarak aşağıdaki biçimde hesaplanabilir:

1
2
3

faktoriyel = 1;
for ( sayici = sayi; sayici >= 1; sayici-- )
faktoriyel *= sayici;

Faktoriyel fonksiyonu için bir yineleme tanımına

1

n! = n * ( n –1 )!

bağıntısı gözlemlenerek ulaşılabilir.

Örneğin, 5! aşağıda açıkça gösterildiği gibi 5 * 4! 'e eşittir:

5!=5*4*3*2*1
5!=5*(4*3*2*1)
5!=5*(4!)

5!'in hesaplanışı, şekil 5.13'te gösterildiği biçimde ilerler. Şekil 5.13-a , yineleme çağrılarının başarısının, yinelemeyi sonlandıran 1!'in bir olarak hesaplanmasını sağlayana kadar nasıl sürdüğünü göstermektedir. Şekil 5.13-b , en son sonuca ulaşılıp bu sonuç döndürülene kadar her yineleme çağrısından döndürülen sonucu göstermektedir.

---
Şekil 5.13 5!'in yineleme ile hesaplanması

Şekil 5.14, 0'dan 10'a kadar olan tamsayıların faktoriyellerini hesaplamak ve yazdırmakta yinelemeyi kullanmaktadır. (long veri tipinin kullanılışı az sonra açıklanacaktır) faktoriyel yineleme fonksiyonu, ilk önce bir sonlandırma koşulunun ( sayi 1'den küçük ya da 1'e eşitse) doğru olup olmadığını kontrol etmektedir. sayi 1'den küçük ya da 1'e eşitse, faktoriyel fonksiyonu 1 sonucunu döndürmektedir ve daha fazla yinelemeye gerek kalmadığından program sonlanmaktadır. Eğer sayi 1'den büyükse

1

return sayi * faktoriyel ( sayi - 1);

ifadesi problemi, sayi ile sayi-1'in faktoriyelini hesaplayan faktoriyel fonksiyonuna bir yineleme çağrısının çarpımı biçiminde ifade etmektedir. faktoriyel (sayi-1)'in orijinal hesaplama olan faktoriyel (sayi)'dan biraz daha basit bir problem olduğuna dikkat ediniz.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/* Fig. 5.14: fig05_14.c
Yineleme faktoriyel fonksiyonu */
#include <stdio.h>
 
long faktoriyel ( long );
 
int main( )
 {
 int i;
 
 for ( i = 1; i <= 10; i++ )
    printf( "%2d! = %ld\n", i, faktoriyel(i ) );
 return 0;
 }
 
 long faktoriyel( long sayi)
 {
     if ( sayi <= 1 )
         return 1;
     else
         return ( sayi * faktoriyel(sayi - 1 ) );
 }

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

Şekil 5.14 Faktoriyel hesaplamalarını yineleme fonksiyonuyla yapmak

faktoriyel fonksiyonu, long tipte bir parametre alacak ve long tipte bir sonuç üretecek biçimde bildirilmiştir. Bu, long int gösteriminin kısaltmasıdır. ANSI standardı long int tipinde bir değişkenin en az 4 byte içinde depolanacağını ve bu sebepten +2147483647 kadar büyük bir değer tutabileceğini belirlemiştir. Şekil 5.14'te görülebileceği gibi faktoriyel değerleri hızlı bir biçimde büyümektedir. long veri tipini, küçük tamsayılar (2 byte gibi) kullanan bilgisayarlarda 7!'den daha büyük faktoriyel değerlerini hesaplayabilmek için seçtik. long değerleri yazdırmak için %ld belirteci kullanılır. Maalesef, faktoriyel fonksiyonu büyük değerleri o kadar hızlı üretir ki, long int bir değişkenin büyüklüğüne ulaşılana kadar, bir çok faktoriyel değerini long int kullansak bile yazdırmak mümkün olmaz.

Alıştırmalarda araştıracağımız gibi, daha büyük sayıların faktoriyellerini hesaplamak için kullanıcı tarafından double kullanmaya ihtiyaç duyulabilir. Bu, C'nin (ve diğer bir çok programlama dilinin) bir zayıflığını gösterir. Dil, çeşitli uygulamaların ihtiyaçlarını karşılamak için kolaylıkla genişletilememektedir. İleride göreceğimiz gibi, C++ istediğimizde büyük sayılar elde edebilmemiz için kolaylıkla genişletilebilir.

Genel Programlama Hataları 5.15
İhtiyaç duyulmasına rağmen, bir yinelemeli fonksiyondan değer geri döndürmeyi unutmak.

Genel Programlama Hataları 5.16
Temel durumu dahil etmemek ya da yineleme adımını temel duruma ulaşmayacak yanlış bir biçimde yazmak, neticede hafızayı yoran sonsuz yineleme yaratır. Bu, yinelemeli olmayan bir çözümde sonsuz döngü problemiyle eşdeğerdir. Sonsuz yineleme beklenmeyen bir giriş yapıldığında da oluşabilir.

5.14 YİNELEMELERİ KULLANAN ÖRNEK: FIBONACCI SERİLERİ

Fibonacci serileri

0,1,1,2,3,5,8,13,21,......

0 ve 1 ile başlar ve sonradan gelen her Fibonacci sayısının, kendinden önceki iki Fibonacci sayısının toplanması özelliğine sahiptir.

Seriler doğada bulunmaktadır ve özel olarak spiral biçimini tanımlar. Fibonacci sayılarının oranı, sabit bir değer olan 1.618....'e yaklaşır. Bu sayı da doğada sık sık tekrarlanır ve altın oran ya da altın orta olarak adlandırılır. İnsanlar altın ortayı estetik olarak hoş bulma eğilimindedir. Mimarlar genellikle pencereleri, odaları ve binaları, uzunluk ve genişlikleri altın orta oranında olacak biçimde tasarlarlar. Kartpostallar genellikle altın orta oranına sahip bir biçimde yapılırlar.

Fibonacci serileri yinelemeli olarak aşağıdaki biçimde tanımlanabilir:

1
2
3

fibonacci(0)=0
fibonacci(1)=1
fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)

Şekil 5.15, fibonacci fonksiyonunu kullanarak i. Fibonacci sayısını yinelemeli olarak hesaplamaktadır. Fibonacci sayılarının hızlı bir biçimde büyüme eğiliminde olduklarına dikkat ediniz. Bu sebepten, fibonacci fonksiyonunda geri dönüş tipi ve parametre tipi için long tipini seçtiğimize dikkat ediniz. Şekil 5.15'te çıktıların her iki satırı programın ayrı bir çalışmasından elde edilen sonucu göstermektedir.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

1 /* Fig. 5.15: fig05_15.c
2 Yinelemeli fibonacci fonksiyonu */
3 #include <stdio.h>
4
5 long fibonacci( long );
6
int main( )
{
 long sonuc, sayi;
 
 printf( "Bir tamsayı giriniz: " );
 scanf( "%ld", & sayi);
 sonuc = fibonacci(sayi);
 printf( "Fibonacci( %ld ) = %ld\n", sayi, sonuc);
 return 0;
 }
 
 /* Yinelemeli tanımlanmış fibonacci fonksiyonu */
 long fibonacci( long n )
 {
     if ( n == 0 || n == 1 )
         return n;
     else
         return fibonacci( n - 1 ) + fibonacci( n - 2 );
 }

Bir tamsayı giriniz: 0
Fibonacci(0) = 0
Bir tamsayı giriniz: 1
Fibonacci(1) = 1
Bir tamsayı giriniz: 2
Fibonacci(2) = 1
Bir tamsayı giriniz: 3
Fibonacci(3) = 2
Bir tamsayı giriniz: 4
Fibonacci(4) = 3
Bir tamsayı giriniz: 5
Fibonacci(5) = 5
Bir tamsayı giriniz: 6
Fibonacci(6) = 8
Bir tamsayı giriniz: 10
Fibonacci(10) = 55
Bir tamsayı giriniz: 20
Fibonacci(20) = 6765
Bir tamsayı giriniz: 30
Fibonacci(30) = 832040
Bir tamsayı giriniz: 35
Fibonacci(35) = 9227465
Şekil 5.15 Yinelemeli olarak Fibonacci sayıları oluşturmak.

main içinden fibonacci fonksiyonuna yapılan çağrı yinelemeli çağrı değildir, ancak bundan sonra fibonacci fonksiyonuna yapılan çağrıların hepsi yinelemelidir. fibonacci her çağrıldığında temel durumu, yani n'in 0 ya da 1'e eşit oluşunu kontrol eder. Eğer bu doğruysa, n döndürülür. İlginç bir şekilde eğer n 1'den büyükse, yineleme her biri fibonacci'ye yapılan orijinal çağrıdan daha basit bir problem olan iki yinelemeli çağrı yapar. Şekil 5.16, fibonacci fonksiyonunun fibonacci ( 3 ) değerini nasıl hesapladığını gösterir. Şekil 5.16'da fibonacci yerine f yazarak şeklin daha kolay anlaşılmasını sağladık.

Bu şekil (Şekil 5.16), C derleyicilerinin, operatörlerin operandlarını hangi sırada değerlendirecekleriyle ilgili ilginç konuları ortaya çıkartmaktadır. Bu, operatörlerin operandlara hangi sırada uygulandıklarından, yani operatör önceliklerinden daha farklıdır. Şekil 5.16, f ( 3 ) hesaplanırken iki yinelemeli çağrının ; f ( 2 ) ve f ( 1 )'in yapıldığını göstermektedir. Fakat bu çağrılar hangi sırada yapılacaktır? Çoğu programcı operandların soldan sağa doğru hesaplanacağını düşünecektir. Ancak ANSI standardı, çoğu operatörün (+ operatörü de dahil olmak üzere) operandlarının değerlendirilme sıralarını belirtmemiştir. Bu sebepten, programcı bu çağrıların çalıştırılma sıraları hakkında yorum yapamaz. Bu çağrılar önce f ( 2 ) daha sonra f ( 1 ) çalıştırılarak ya da tam ters bir biçimde önce f ( 1 ) sonra f ( 2 ) çalıştırılarak yapılabilir. Bu programda ve diğer bir çok programda en son sonuç aynı olacaktır. Ancak bazı programlarda, bir operandın değerlendirilmesi ifadenin en son değerini etkileyebilecek yan etkilere sebep olabilir. C'nin bir çok operatörü arasından, ANSI standardı yalnızca 4 operatörün operandlarını değerlendirme sıralarını belirlemiştir. Bunlar &&, || , virgül operatörü ( , ) ve ?: operatörleridir. Bunlardan ilk üçü, ikili operatörlerdir ve operandlarının soldan sağa doğru değerlendirilmesi garanti altına alınmıştır. Son operatör ise C'nin üçlü tek operatörüdür. Bu operatörün en soldaki operandı her zaman ilk olarak ele alınır; eğer en soldaki operand sıfır harici bir değer olarak hesaplanırsa, ortadaki operand hesaplanır ve en son operand ihmal edilir , eğer en soldaki ifade 0 olarak hesaplanırsa en sağdaki operand ele alınır ve ortadaki operand ihmal edilir.

Genel Programlama Hataları 5.17
&& , || , ?: ve virgül ( , ) operatörleri dışındaki operatörlerin operandlarını değerlendirme sıralarına bağımlı olarak yazılan programlar hatalara sebep olabilir.Çünkü derleyiciler operandları programcının beklediği gibi ele almayabilir.

Taşınırlık İpuçları 5.2
&& ,|| ,?: ve virgül(,) operatörleri dışındaki operatörlerin operandlarını değerlendirme sıralarına bağımlı olarak yazılan programlar farklı sistemlerde ve farklı derleyicilerle farklı bir şekilde çalışabilirler.

Burada yineleme programlarıyla ilgili dikkat edilecek bir noktadan bahsetmek istiyoruz. fibonacci fonksiyonundaki her yineleme, çağrı sayılarını iki katına çıkartmaktadır yani n. fibonacci sayısını bulmak için çalıştırılacak yineleme çağrısı sayısı 2n dir. Bu çok hızlı bir şekilde kontrolden çıkabilir. 20.fibonacci sayısını hesaplamak için 220 ya da milyonlarca çağrı yapmak, 30.fibonacci sayısını hesaplamak için 230 çağrı ya da milyarlarca çağrı yapmak gerekir. Bilgisayarla uğraşan bilim adamları bu üssel karışıklığa dikkati çekerler. Bu tarzdaki problemler dünyanın en güçlü bilgisayarlarını bile zorlar! Genel karmaşa konuları ve üssel karmaşa konuları genellikle yüksek seviyeli bilgisayar bilimlerinde "Algoritmalar" adlı kurslarda tartışılır.

Performans İpuçları 5.4
Çağrıların üssel bir biçimde arttığı Fibonnacci tarzında yinelemeli programlardan kaçınınız.

Şekil 5.16 fibonacci fonksiyonu için yineleme çağrıları

YİNELEME ve TEKRAR

Önceki kısımlarda kolaylıkla yinelemeli ya da tekrarlı bir biçimde gösterilebilecek iki fonksiyon inceledik. Bu kısımda iki yaklaşımı karşılaştırarak, programcının özel durumlarda hangisini diğerine tercih edebileceğini tartışacağız.

Yineleme ve tekrar bir kontrol yapısına dayanır : tekrar bir döngü yapısı, yineleme bir seçim yapısı kullanır. Tekrar ve yinelemenin ikisi de döngü içerir. Tekrar özellikle döngü yapısını kullanırken, yineleme döngüyü fonksiyon çağrılarının tekrarında kullanır. Tekrar ve yinelemenin ikisi de bir sonlandırma testi içerirler. Yineleme temel bir durumla karşılaşıldığında, tekrar ise döngü devam koşulu yanlış hale geldiğinde sona erer. Sayıcı kontrollü döngü içeren tekrar ve yineleme yavaş yavaş sonlanmaya yaklaşır : tekrarlama sayıcıyı, sayıcı döngü devam şartını yanlış hale getirecek bir değer alana kadar değiştirmeye devam eder; yineleme ise temel duruma ulaşılıncaya kadar orijinal problemin daha basit versiyonlarını yaratmaya devam eder. Tekrar ve yinelemenin ikisi de sonsuz olabilir: Sonsuz bir döngü eğer döngü devam şartı asla yanlış hale gelmiyorsa ; sonsuz yineleme, yineleme adımı problemi temel duruma yaklaştıracak biçimde indirgemiyorsa oluşur.

Yineleme bir çok negatif özelliğe sahiptir.Yineleme, mekanizmayı sürekli çağırarak fonksiyon çağrılarının artmasına sebep olur. Bu, işlemci zamanı ve hafızada fazladan yük demektir. Her yineleme çağrısı ,fonksiyonun başka bir kopyasının oluşmasına(aslında yalnızca fonksiyonun değişkenlerinin) sebep olur, bu da hafızayı fazladan işgal etmek demektir. Tekrar, genellikle bir fonksiyon içinde yer aldığından, fonksiyonların sürekli olarak çağrılması ve fazladan hafıza kullanılması engellenir. O halde neden yineleme seçilsin?

Yazılım Mühendisliği Gözlemleri 5.12
Yinelemeli olarak çözülen her problem tekrarlı bir biçimde çözülebilir. Yineleme yaklaşımı genelde problemi daha iyi yansıttığı ve daha kolay anlaşılan ve hataları kolay ayıklanan programlar yazılmasını sağlattığı için, tekrar yaklaşımına göre tercih edilebilir. Yinelemeli çözümleri seçmenin başka bir sebebi de tekrarlı çözümün kolaylıkla bulunamayışıdır.

Performans İpuçları 5.5
Performansın önemli olduğu durumlarda yinelemeden kaçının.Yineleme çağrıları fazladan vakit ve hafıza gerektirir.

Genel Programlama Hataları 5.18
Yanlışlıkla, kendi kendini doğrudan ya da başka bir fonksiyon içinden çağıran, yinelemeli olmayan bir fonksiyona sahip olmak.

Çoğu programlama kitabı, yinelemeyi bizim burada yaptığımızdan daha geç tanıtır. Yinelemenin oldukça zengin ve karmaşık bir konu olduğunu düşündüğümüzden, bu konuyu şimdi anlatmayı ve örnekleri kitabın geri kalanına yaymayı uygun gördük. Şekil 5.17, kitap boyunca verilen 31 yineleme örneğinin hangi ünitelerde bulunduğunu özetlemektedir.

Bu üniteyi, kitap boyunca tekrar tekrar yaptığımız birkaç gözlemle kapatalım. İyi yazılım mühendisliği önemlidir. Yüksek performans önemlidir. Ancak maalesef bu hedefler genelde birbirlerini engellerler. İyi yazılım mühendisliği, ihtiyaç duyduğumuz daha büyük ve karmaşık yazılım sistemlerinin geliştirilmesinde temel noktadır. Yüksek performans ise gelecekteki donanım üzerinde daha fazla işlem gerektiren sistemlerin gerçekleştirilebilmesindeki temel noktadır. Öyleyse fonksiyonlar nereye uymaktadır?

Yazılım Mühendisliği Gözlemleri 5.13
Programları düzgün,hiyerarşik bir düzende fonksiyonlardan oluşturmak iyi yazılım mühendisliğini destekler. Ancak bunun da bir bedeli vardır.

Performans İpuçları 5.6
Fonksiyonların yoğun bir biçimde kullanıldığı programlar, fonksiyonların yer almadığı tek parça programlarla karşılaştırıldığında, çok fazla sayıda fonksiyon çağrısı yapacaktır ve bu da bilgisayarın işlemcisinin zamanını çok fazla alır. Ancak tek parça programları yazmak, test etmek, hatalarını ayıklamak ve geliştirmek oldukça zordur.