Syarat keluar. StackOverflowError

Contoh kod rekursif tanpa syarat keluar

Mari kita lihat satu lagi masalah rekursif. Sebagai contoh, pertimbangkan untuk mengira nombor Fibonacci. Semua orang akan ingat bahawa jujukan Fibonacci ialah jujukan berangka di mana dua nombor pertama ialah 0 dan 1, dan setiap nombor berikutnya adalah sama dengan jumlah dua nombor sebelumnya.

Mari tulis kod untuk mengira dan memaparkan nombor ini:

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);
    }
}
    

Sebelum panggilan pertama kaedah cetak rekursifFibonacci , cetak dua nombor pertama jujukan: sifar dan satu. Kita perlu melakukan ini kerana kaedah rekursif hanya memaparkan jumlah parameter input, bukan parameter itu sendiri.

Kod itu kelihatan baik: kami mendapat dua nombor, mengira jumlahnya, mencetaknya pada konsol, dan memanggil kaedah printFibonacci secara rekursif sekali lagi. Kami lulus nombor sebelumnya (sebelumnya) dan nombor semasa (semasa) sebagai argumen.

Sebenarnya, kod tersebut mempunyai dua ralat. Anda boleh melihatnya jika anda menjalankan kod tersebut.

Ralat pertama melimpahi jenis panjang . Nombor ke-104 dalam urutan kami adalah negatif, menunjukkan bahawa jenis panjang melimpah.

Ralat kedua adalah berbeza. Selepas mengira kira-kira 12,000 nombor, kami mendapat:

Sekarang ialah masa yang sesuai untuk mengingati susunan panggilan kaedah dalam Java. Mesin Java menyimpan rekod semua panggilan fungsi. Untuk melakukan ini, ia menggunakan jenis koleksi khas yang dipanggil tindanan. Apabila satu fungsi memanggil yang lain, mesin Java menolak StackTraceElement baharu ke tindanan. Apabila fungsi tamat, elemen ini dialih keluar daripada timbunan. Sehubungan itu, timbunan sentiasa menyimpan maklumat terkini tentang keadaan semasa timbunan panggilan fungsi. Dokumentasi untuk StackTraceElement mengatakan bahawa ia adalah "Dibuang apabila limpahan tindanan berlaku kerana aplikasi berulang terlalu mendalam." JVM yang sedang berjalan mempunyai kawasan memori khas untuk menyimpan timbunan panggilan kaedah. Saiz kawasan memori ini bergantung pada tetapan OS dan JVM. Sebagai tambahan kepada timbunan panggilan kaedah itu sendiri, pembolehubah primitif (nilai khusus parameter kaedah) dan alamat pembolehubah rujukan (dalam kawasan memori yang dipanggil "timbunan") disimpan dalam kawasan memori khas ini. Akses kepada timbunan panggilan mengikut prinsip LIFO.

Contoh yang diperbetulkan dengan keadaan keluar

Mari mulakan dengan menyelesaikan masalah kedua dalam kod.

Mari cuba selesaikan masalah itu secara langsung: jika timbunan terlalu kecil, maka mari kita besarkan. Untuk melakukan ini, mulakan JVM dengan bendera "-Xss" dan tentukan berapa banyak memori yang perlu diperuntukkan untuk timbunan. Mari cuba peruntukkan 5 megabait. Inilah rupanya dalam IDEA:

Kami berjaya meningkatkan panjang output. Kini boleh mengira lebih daripada 49,000 nombor jujukan dan bukannya terhad kepada kira-kira 12,000 nombor. Tetapi pada satu ketika, kami masih mendapat StackOverflowError .

Anda boleh cuba meningkatkan saiz timbunan, tetapi itu tidak menyelesaikan masalah asas. Jadi, mari kita cari masalah dalam logik. Mesti ada titik apabila rekursi berhenti. Dalam erti kata lain, mesti ada beberapa syarat yang menentukan bila kaedah rekursif tidak akan dipanggil lagi, membenarkan timbunan panggilan untuk berehat. Untuk menentukan keadaan sedemikian, mari kita jelaskan objektif kami: paparkan siri Fibonacci selagi nombornya kurang daripada Integer.MAX_VALUE .

Mari tulis kaedah printFibonacciWithCondition baharu yang akan mengambil kira syarat ini. Dan kami akan memanggil kaedah diperbetulkan baru dalam kaedah utama.

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);
    }
}
    

Selepas menjalankan kod, kita melihat bahawa output berakhir dengan nombor 1836311903. Nombor sebelum ini ialah 1134903170. Jumlah nombor ini ialah 2_971_215_073, yang sememangnya lebih besar daripada Integer.MAX_VALUE (2_147_483_647 ) .

Perubahan ini membetulkan pepijat limpahan panjang secara automatik . Jika anda perlu mengira lebih banyak siri, anda perlu menggunakan jenis data lain, seperti BigInteger .

Penurunan rekursif dan berehat

Mari analisa langkah demi langkah bagaimana kod kami dilaksanakan. Untuk melakukan ini, kami akan menambah kaedah gema dan memanggilnya sebelum dan selepas panggilan rekursif kaedah printFibonacciWithCondition .

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 ini memberi kita output ini:

Berikut ialah visualisasi tentang apa yang berlaku.

Katakan sekali lagi: kaedah printFibonacciWithCondition dipanggil. Ia mengira nombor semasa. Jika ia sesuai dengan kami, maka kami memaparkannya dan memanggil kaedah printFibonacciWithCondition sekali lagi dengan hujah baharu.

Selagi kaedah rekursif dipanggil, ini dipanggil "keturunan rekursif". Apabila rekursif ditamatkan dan panggilan kaedah kembali, kami mengatakan bahawa timbunan panggilan sedang "berhenti".

Rekursi adalah topik yang menarik dalam pengaturcaraan. Untuk mendapatkan pegangan yang lebih baik tentang bahan, mari kita ubah sedikit tugasan kita. Tugas baharu adalah untuk mengeluarkan, dalam tertib menurun, semua nombor dalam siri Fibonacci yang tidak melebihi Integer.MAX_VALUE . Kami telah menulis semua kod yang diperlukan untuk tugas ini. Yang tinggal hanyalah menukar susunan memaparkan nombor semasa dan memanggil kaedah rekursif. Iaitu, dalam contoh pertama, nombor yang dikira telah dipaparkan semasa "keturunan", tetapi sekarang kita perlu "turun ke bahagian paling bawah" dan kemudian memaparkan nombor "dalam perjalanan ke atas". Dan sudah tentu, dalam kaedah utama , kami menukar dua nombor awal jujukan (sifar dan satu) selepas memaparkannya selepas kami memanggil kaedah rekursif. Untuk kebolehbacaan,kaedah.

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);
    }
}
    

Outputnya ialah: