Java'da Özyineleme Üzerine Bu Derinlemesine Eğitim, Örnekler, Türler ve İlgili Kavramlarla Özyinelemenin ne olduğunu açıklar. Ayrıca Yinelemeye Karşı Özyinelemeyi de kapsar:
Java'daki önceki derslerimizde, bir döngü bildirdiğimiz ve ardından her seferinde bir öğe alarak bir veri yapısı boyunca yinelemeli bir şekilde ilerlediğimiz yinelemeli yaklaşımı gördük.
Ayrıca, yine bir döngü değişkenini tuttuğumuz ve döngü değişkeni koşulu karşılayana kadar bir kod parçasını tekrarladığımız koşullu akışı da gördük. İşlev çağrıları söz konusu olduğunda, işlev çağrıları için yinelemeli yaklaşımı da keşfettik.
Bu eğitimde, programlamaya farklı bir yaklaşım olan Özyinelemeli yaklaşımı ele alacağız.
Java'da Özyineleme Nedir?
Özyineleme, bir işlevin veya yöntemin kendisini tekrar tekrar çağırması işlemidir. Doğrudan veya dolaylı olarak tekrar tekrar çağrılan bu işleve "özyinelemeli işlev" denir.
Özyinelemeyi anlamak için çeşitli örnekler göreceğiz. Şimdi özyinelemenin sözdizimini görelim.
Özyineleme Sözdizimi
Özyinelemeyi uygulayan herhangi bir yöntemin iki temel parçası vardır:
- Kendini çağırabilen, yani özyinelemeli yöntem çağrısı
- Özyinelemeyi durduracak bir ön koşul.
Herhangi bir özyinelemeli yöntem için bir ön koşulun gerekli olduğunu unutmayın, çünkü özyinelemeyi kesmezsek, sonsuza kadar çalışmaya devam edecek ve yığın taşmasına neden olacaktır.
Özyinelemenin genel sözdizimi aşağıdaki gibidir:
methodName (T parameters...) { if (precondition == true) //önkoşul veya temel koşul { return result; } return methodName (T parameters...); //recursive call } Ön koşulun temel koşul olarak da adlandırıldığını unutmayın. Bir sonraki bölümde temel koşul hakkında daha fazla tartışacağız.
Java'da Özyinelemeyi Anlamak
Bu bölümde, özyineleme sürecini anlamaya ve nasıl gerçekleştiğini görmeye çalışacağız. Temel koşul, yığın taşması hakkında bilgi edineceğiz ve belirli bir sorunun özyineleme ile nasıl çözülebileceğini ve bunun gibi diğer ayrıntıları göreceğiz.
Özyineleme Temel Koşulu
Özyinelemeli programı yazarken öncelikle temel durum için çözüm sağlamalıyız. Daha sonra büyük problemi daha küçük problemler cinsinden ifade ederiz.
Olarak Örnek, Bir sayının faktöriyelini hesaplamak için klasik bir problemi ele alabiliriz. n sayısı verildiğinde, n! ile gösterilen n'nin faktöriyelini bulmamız gerekir.
Şimdi özyineleme kullanarak n faktöriyelini (n!) hesaplamak için programı uygulayalım.
public class Main{ static int fact(int n) { if (n == 1) // temel koşul return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Çıktı
Bu programda, (n<=1) koşulunun temel koşul olduğunu ve bu koşula ulaşıldığında fonksiyonun 1 döndürdüğünü görebiliriz. Fonksiyonun else kısmı özyinelemeli çağrıdır. Ancak özyinelemeli yöntem her çağrıldığında, n 1 azaltılır.
Böylece, sonuçta n değerinin 1 veya 1'den küçük olacağı ve bu noktada metodun 1 değerini döndüreceği sonucuna varabiliriz. Bu temel koşula ulaşılacak ve fonksiyon duracaktır. n değerinin, temel koşulu karşıladığı sürece herhangi bir şey olabileceğine dikkat edin.
Özyineleme Kullanarak Problem Çözme
Özyinelemeyi kullanmanın arkasındaki temel fikir, daha büyük problemi daha küçük problemler cinsinden ifade etmektir. Ayrıca, özyinelemeden çıkabilmemiz için bir veya daha fazla temel koşul eklememiz gerekir.
Bu, yukarıdaki faktöriyel örneğinde zaten gösterilmişti. Bu programda, n faktöriyelini (n!) daha küçük değerler cinsinden ifade ettik ve bir temel koşulumuz (n <=1) vardı, böylece n 1'e ulaştığında özyinelemeli yöntemden çıkabilirdik.
Özyinelemede Yığın Taşması Hatası
Herhangi bir yöntem ya da fonksiyon çağrıldığında, fonksiyonun durumunun yığında saklandığını ve fonksiyon geri döndüğünde geri alındığını biliyoruz. Yığın, özyinelemeli yöntem için de kullanılır.
Ancak özyineleme durumunda, temel koşulu tanımlamadığımızda veya temel koşula bir şekilde ulaşılmadığında veya yürütülmediğinde bir sorun ortaya çıkabilir. Bu durum meydana gelirse, yığın taşması ortaya çıkabilir.
Aşağıdaki faktöriyel gösterim örneğini ele alalım.
Burada yanlış bir temel koşul verdik, n==100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Yani n> 100 olduğunda yöntem 1 döndürür ancak özyineleme durmaz. n değeri, onu durduracak başka bir koşul olmadığı için süresiz olarak azalmaya devam edecektir. Bu, yığın taşana kadar devam edecektir.
Başka bir durum da n <100 değerinin olması halinde ortaya çıkacaktır. Bu durumda da yöntem temel koşulu asla çalıştırmayacak ve yığın taşmasına neden olacaktır.
Java'da Özyineleme Örnekleri
Bu bölümde, özyineleme kullanarak aşağıdaki örnekleri uygulayacağız.
#1) Özyineleme Kullanarak Fibonacci Serisi
Fibonacci serisi şu şekilde verilir,
1,1,2,3,5,8,13,21,34,55,…
Yukarıdaki dizi, mevcut elemanın önceki iki elemanın toplamı olduğunu göstermektedir. Ayrıca, Fibonacci serisindeki ilk eleman 1'dir.
Yani genel olarak n mevcut sayı ise, (n-1) ve (n-2)'nin toplamı ile verilir. Mevcut eleman önceki elemanlar cinsinden ifade edildiğinden, bu problemi özyineleme kullanarak ifade edebiliriz.
Fibonacci serisini uygulamak için program aşağıda verilmiştir:
public class Main { //fibonacci serisini hesaplama yöntemi static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int sayı = 10; //fibonacci serisinin ilk 10 sayısını yazdır System.out.println ("Fibonacci Serisi: İlk 10 sayı:"); for (int i = 1; i <= sayı; i++) { System.out.print(fibonacci(i) + " ");} } } Çıktı
#2) Özyineleme Kullanarak Bir Sayının Palindrom Olup Olmadığını Kontrol Edin
Palindrom, soldan sağa veya sağdan sola okuduğumuzda eşit olan bir dizidir.
121 sayısı verildiğinde, soldan sağa ve sağdan sola okuduğumuzda eşit olduğunu görürüz. Dolayısıyla 121 sayısı bir palindromdur.
Başka bir sayıyı ele alalım, 1242. Soldan sağa okuduğumuzda 1242, sağdan sola okuduğumuzda ise 2421. Dolayısıyla bu bir palindrom değildir.
Palindrom programını, sayıların rakamlarını ters çevirerek ve verilen sayıyı ters çevrilmiş gösterimiyle özyinelemeli olarak karşılaştırarak uyguluyoruz.
Aşağıdaki program palindromu kontrol etmek için programı uygular.
import java.io.*; import java.util.*; public class Main { // num'un yalnızca bir rakam içerip içermediğini kontrol et public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //palindrome yardımcı işlevi public static int isPalindrome_util (int num, int revNum) throws Exception { // temel koşul; num=0 ise return if (num == 0) { return revNum; } else { //callyardımcı fonksiyonu özyinelemeli olarak revNum = isPalindrome_util(num / 10, revNum); } // num ve revNum'un ilk basamağının eşit olup olmadığını kontrol et if (num % 10 == revNum % 10) { // evetse, revNum num ile hareket eder return revNum / 10; } else { // exit throw new Exception(); } } // palindrome yardımcı fonksiyonunu kullanarak verilen bir sayının palindrom olup olmadığını kontrol etme metodu public static int isPalindrome(int num) throwsException { if (num <0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } n = 1221; try { isPalindrome(n);System.out.println("Evet, verilen sayı " + n + " bir palindromdur."); } catch (Exception e) { System.out.println("Hayır, verilen sayı " + n + " bir palindrom değildir."); } } } Çıktı
#3) Ters Dize Özyineleme Java
Bir "Hello" dizesi verildiğinde, sonuç dizesi "olleH" olacak şekilde bunu tersine çevirmemiz gerekir.
Bu işlem özyineleme kullanılarak yapılır. Dizedeki son karakterden başlayarak, dizedeki tüm karakterler tükenene kadar her karakteri özyinelemeli olarak yazdırırız.
Aşağıdaki program, verilen bir dizeyi tersine çevirmek için özyineleme kullanır.
class String_Reverse { //verilen bir dizeyi tersine çevirmek için özyinelemeli yöntem void reverseString(String str) { /temel koşul; dize null ise veya 1 veya daha az karakter içeriyorsa geri döner if ((str==null)} } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("The given string: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("The reversed string: "); obj.reverseString(inputstr); } } Çıktı
#4) İkili Arama Java Özyineleme
İkili arama algoritması, arama için kullanılan ünlü bir algoritmadır. Bu algoritmada, n elemanlı sıralanmış bir dizi verildiğinde, bu diziyi verilen anahtar eleman için ararız. Başlangıçta, dizinin orta elemanını bularak diziyi ikiye böleriz.
Daha sonra anahtarın ortada olmasına bağlı olarak aramamızı dizinin ilk veya ikinci yarısında sınırlandırırız. Bu şekilde anahtar elemanların yeri bulunana kadar aynı işlem tekrarlanır.
Bu algoritmayı burada özyineleme kullanarak uygulayacağız.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //calculate mid of array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray[mid] == key) return mid; // if key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search insağ alt dizi return binarySearch(numArray, mid + 1, right, key); } //dizide eleman yok, -1 döndür return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //diziyi bildir ve yazdır int numArray[] = { 4,6,12,16,22}; System.out.println("Verilen dizi : " + Arrays.toString(numArray)); int len = numArray.length; //dizinin uzunluğuint anahtar = 16; //aranacak anahtar int sonuç = ob.binarySearch(numArray, 0, len - 1, anahtar); if (sonuç == -1) System.out.println("Eleman " + anahtar + " mevcut değil"); else System.out.println("Eleman " + anahtar + " dizinde bulundu " + sonuç); } } Çıktı
#5) Özyineleme Kullanarak Dizideki Minimum Değeri Bulma
Özyineleme kullanarak dizideki minimum değeri de bulabiliriz.
Dizideki minimum değeri bulmak için kullanılan Java programı aşağıda verilmiştir.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //eğer sadece bir eleman varsa ilk elemanı döndür veya dizi elemanlarının minimumunu döndür (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Verilen Dizi : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Dizinin minimum elemanı: " + getMin(numArray, 0, n) + "\n"); } } Çıktı
Bunlar özyineleme örneklerinden bazılarıdır. Bu örneklerin dışında, yazılımdaki diğer pek çok problem özyineleme teknikleri kullanılarak uygulanabilir.
Özyineleme Türleri
Özyineleme, özyinelemeli yöntemin ne zaman çağrıldığına bağlı olarak iki türdür.
Onlar:
#1) Kuyruk Özyineleme
Özyinelemeli yönteme yapılan çağrı, özyinelemeli yöntem içinde yürütülen son deyim olduğunda, buna "Kuyruk Özyinelemesi" denir.
Kuyruk özyinelemesinde, özyinelemeli çağrı ifadesi genellikle yöntemin dönüş ifadesiyle birlikte yürütülür.
Kuyruk özyinelemesi için genel sözdizimi aşağıda verilmiştir:
methodName (T parameters...){ { if (base_condition == true) { return result; } return methodName (T parameters...) //tail recursion } #2) Kafa Özyinelemesi
Baş özyineleme, kuyruk özyinelemesi olmayan herhangi bir özyinelemeli yaklaşımdır. Yani genel özyineleme bile baş özyinelemedir.
Baş özyinelemenin sözdizimi aşağıdaki gibidir:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Java'da Yinelemeye Karşı Yineleme
| Özyineleme | Yineleme |
|---|---|
| Özyineleme, bir yöntemin temel bir koşul karşılanana kadar kendisini tekrar tekrar çağırdığı bir süreçtir. | Yineleme, bir kod parçasının sonlu sayıda veya bir koşul karşılanana kadar tekrar tekrar yürütüldüğü bir süreçtir. |
| Fonksiyonlar için uygulama. | Döngüler için geçerlidir. |
| Daha küçük kod boyutu için iyi çalışır. | Daha büyük kod boyutu için iyi çalışır. |
| Her özyinelemeli çağrı yığına itildiği için daha fazla bellek kullanır | Nispeten daha az bellek kullanılır. |
| Hata ayıklaması ve bakımı zor | Hata ayıklaması ve bakımı daha kolay |
| Temel koşul belirtilmezse veya bu koşula ulaşılmazsa yığın taşmasıyla sonuçlanır. | Sonsuza kadar çalışabilir, ancak herhangi bir bellek hatasında yürütmeyi durduracaktır |
| Zaman karmaşıklığı çok yüksektir. | Zaman karmaşıklığı nispeten daha düşüktür. |
Sıkça Sorulan Sorular
S #1) Java'da Özyineleme nasıl çalışır?
Cevap ver: Özyinelemede, özyinelemeli işlev bir temel koşul sağlanana kadar kendini tekrar tekrar çağırır. Çağrılan işlevin belleği, çağıran işlevin belleğinin en üstündeki yığına itilir. Her işlev çağrısı için yerel değişkenlerin ayrı bir kopyası oluşturulur.
Q #2) Özyineleme neden kullanılır?
Cevap ver: Özyineleme, daha küçük problemlere bölünebilen ve tüm problemin daha küçük bir problem cinsinden ifade edilebildiği problemleri çözmek için kullanılır.
Özyineleme, yinelemeli bir yaklaşım kullanılarak çözülemeyecek kadar karmaşık olan problemler için de kullanılır. Zaman karmaşıklığının sorun olmadığı problemlerin yanı sıra özyineleme kullanın.
Q #3) Özyinelemenin faydaları nelerdir?
Cevap ver:
Özyinelemenin faydaları şunlardır:
- Özyineleme, gereksiz fonksiyon çağrılarını azaltır.
- Özyineleme, yinelemeli yaklaşıma kıyasla problemleri daha kolay çözmemizi sağlar.
S #4) Hangisi daha iyi - Özyineleme mi Yineleme mi?
Cevap ver: Özyineleme, temel işleve ulaşılana kadar tekrarlanan çağrılar yapar. Bu nedenle, her işlev çağrısı için bir bellek yığına itildiği için bir bellek ek yükü vardır.
Öte yandan yinelemenin fazla bellek yükü yoktur. Yinelemeli yürütme yinelemeli yaklaşımdan daha yavaştır. Yinelemeli yaklaşım kodu büyütürken yineleme kodun boyutunu küçültür.
Q #5) Yinelemenin Yinelemeye Göre Avantajları Nelerdir?
Cevap ver:
- Özyineleme kodu daha anlaşılır ve kısa hale getirir.
- Hanoi Kulesi, ağaç geçişleri gibi problemler için özyineleme, yinelemeli yaklaşımdan daha iyidir.
- Her işlev çağrısında bellek yığına itildiğinden, Özyineleme daha fazla bellek kullanır.
- Yineleme performansı, yinelemeli yaklaşıma göre daha yavaştır.
Sonuç
Özyineleme, programlama dilinden bağımsız olarak yazılımda çok önemli bir kavramdır. Özyineleme çoğunlukla Hanoi kuleleri, ağaç geçişleri, bağlı listeler gibi veri yapısı problemlerinin çözümünde kullanılır. Daha fazla bellek gerektirmesine rağmen, özyineleme kodu daha basit ve anlaşılır hale getirir.
Bu eğitimde Özyineleme hakkında her şeyi keşfettik. Ayrıca kavramı daha iyi anlamak için çok sayıda programlama örneği uyguladık.