Çıkış koşulları. StackOverflowError

Çıkış koşulu olmayan özyinelemeli kod örneği

Özyinelemeli bir probleme bir kez daha göz atalım. Örnek olarak, Fibonacci sayılarını hesaplamayı düşünün. Fibonacci dizisinin ilk iki sayının 0 ve 1 olduğu ve sonraki her sayının önceki iki sayının toplamına eşit olduğu bir sayısal dizi olduğunu herkes hatırlayacaktır.

Bu sayıları hesaplamak ve göstermek için kod yazalım:

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacci(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }
}
    

Özyinelemeli printFibonacci yönteminin ilk çağrısından önce , dizinin ilk iki sayısını yazdırın: sıfır ve bir. Bunu yapmamız gerekiyor çünkü özyinelemeli yöntem parametrelerin kendisini değil yalnızca girdi parametrelerinin toplamını gösteriyor.

Kod iyi görünüyor: iki sayı alıyoruz, toplamlarını hesaplıyoruz, konsolda yazdırıyoruz ve tekrar tekrar printFibonacci yöntemini çağırıyoruz. Önceki numarayı (önceki) ve mevcut numarayı (mevcut) argüman olarak iletiyoruz.

Aslında, kodun iki hatası var. Kodu çalıştırırsanız bunları görebilirsiniz.

İlk hata, uzun türün taşmasıdır . Dizimizdeki 104. sayı negatiftir, bu da uzun tipin taştığını gösterir.

İkinci hata farklı. Yaklaşık 12.000 sayı hesapladıktan sonra şunu elde ederiz:

Şimdi, Java'da bir yöntem çağrı yığınının ne olduğunu hatırlamak için uygun bir zaman. Java makinesi tüm işlev çağrılarının kaydını tutar. Bunu yapmak için yığın adı verilen özel bir koleksiyon türü kullanır. Bir işlev diğerini çağırdığında, Java makinesi yığına yeni bir StackTraceElement gönderir. Fonksiyon sona erdiğinde, bu eleman yığından kaldırılır. Buna göre yığın, işlev çağrı yığınının mevcut durumu hakkında her zaman güncel bilgileri depolar. StackTraceElement belgeleri, "Bir uygulama çok derin bir şekilde yinelendiğinden bir yığın taşması meydana geldiğinde atılır" olduğunu söylüyor. Çalışan bir JVM, yöntem çağrı yığınını depolamak için özel bir bellek alanına sahiptir. Bu bellek alanının boyutu işletim sistemi ve JVM ayarlarına bağlıdır. Yöntem çağrı yığınına ek olarak, ilkel değişkenler (yöntem parametrelerinin belirli değerleri) ve referans değişkenlerin adresleri ("yığın" adı verilen bir bellek alanında) bu özel bellek alanında saklanır. Çağrı yığınına erişim, LIFO ilkesini izler.

Çıkış koşuluyla düzeltilmiş örnek

Koddaki ikinci sorunu çözerek başlayalım.

Sorunu kafa kafaya çözmeye çalışalım: Yığın çok küçükse, onu büyütelim. Bunu yapmak için JVM'yi "-Xss" bayrağıyla başlatın ve yığın için ne kadar bellek ayrılacağını belirtin. 5 megabayt ayırmayı deneyelim. IDEA'da şöyle görünecek:

Çıktının uzunluğunu artırmayı başardık. Artık, yaklaşık 12.000 sayıyla sınırlı olmak yerine, dizinin 49.000'den fazla sayısını hesaplayabilir. Ancak bir noktada, hala bir StackOverflowError alıyoruz .

Yığının boyutunu artırmayı deneyebilirsiniz, ancak bu temel sorunu çözmez. Öyleyse mantıkta bir problem arayalım. Özyinelemenin durduğu bir nokta olmalıdır. Başka bir deyişle, özyinelemeli yöntemin ne zaman artık çağrılmayacağına karar veren ve çağrı yığınının gevşemesine izin veren bir koşul olmalıdır. Böyle bir koşulu tanımlamak için, amacımızı açıklığa kavuşturalım: sayıları Integer.MAX_VALUE değerinden küçük olduğu sürece Fibonacci serisini görüntüleyin .

Bu durumu dikkate alacak yeni bir printFibonacciWithCondition metodu yazalım . Ve yeni düzeltilmiş yöntemi ana yöntemde arayacağız.

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
//        printFibonacci(0, 1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
    }
}
    

Kodu çalıştırdıktan sonra çıktının 1836311903 sayısı ile bittiğini görüyoruz. Bundan önceki sayı 1134903170. Bu sayıların toplamı 2_971_215_073 ki bu da Integer.MAX_VALUE'den (2_147_483_647) gerçekten büyük .

Bu değişiklik, uzun taşma hatasını otomatik olarak düzeltti. Serinin daha fazlasını hesaplamanız gerekirse, BigInteger gibi diğer veri türlerini kullanmanız gerekecektir .

Yinelemeli iniş ve gevşeme

Kodumuzun nasıl yürütüldüğünü adım adım inceleyelim. Bunu yapmak için bir yankı yöntemi ekleyeceğiz ve onu printFibonacciWithCondition yönteminin özyinelemeli çağrısından önce ve sonra çağıracağız .

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        echo(true, penultimate, previous);
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
        echo(false, penultimate, previous);
    }

    private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
        if (isBeforeRecursiveCall) {
            System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
        } else {
            System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
        }
    }
}
    

Program bize şu çıktıyı veriyor:

İşte neler olduğuna dair bir görselleştirme.

Tekrar söyleyelim: printFibonacciWithCondition yöntemi çağrılır. Mevcut sayıyı hesaplar. Bize uygunsa, onu görüntüler ve printFibonacciWithCondition yöntemini yeni argümanlarla tekrar çağırırız.

Özyinelemeli yöntem çağrıldığı sürece buna "özyinelemeli iniş" denir. Özyinelemeli sona erdiğinde ve yöntem çağrıları geri döndüğünde, çağrı yığınının "gevşediğini" söyleriz.

Özyineleme, programlamada ilginç bir konudur. Malzemeyi daha iyi kavramak için görevimizi biraz değiştirelim. Yeni görev, Fibonacci serisindeki Integer.MAX_VALUE değerini aşmayan tüm sayıları azalan düzende çıkarmaktır . Bu görev için gereken tüm kodu zaten yazdık. Geriye kalan tek şey, geçerli sayıyı görüntüleme sırasını değiştirmek ve özyinelemeli yöntemi çağırmak. Yani, ilk örnekte, hesaplanan sayı "iniş" sırasında görüntüleniyordu, ancak şimdi "en alta inmemiz" ve ardından "geri dönerken" sayıları görüntülememiz gerekiyor. Ve tabi ki main metodunda recursive metodu çağırdıktan sonra dizinin ilk iki numarasını (sıfır ve bir) ekrana getirdikten sonra yer değiştiriyoruz. Okunabilirlik için,yöntem.

public class Fibonacci {
    public static void main(String[] args) {
        printFibonacciWithCondition(0, 1);
        System.out.println(1);
        System.out.println(0);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        printFibonacciWithCondition(previous, current);
        System.out.println(current);
    }
}
    

Çıktı şöyle olacaktır: