CodeGym /Kursus Java /Modul 2: Teras Java /Syarat keluar. StackOverflowError

Syarat keluar. StackOverflowError

Modul 2: Teras Java
Tahap , pelajaran
Tersedia

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:

Pengecualian dalam benang "utama" java.lang.StackOverflowError

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:

0
1
Sebelum kaedah panggilan dengan args: 0, 1. Nombor semasa = 1
Sebelum kaedah panggilan dengan args: 1, 1. Nombor semasa = 2
Sebelum kaedah panggilan dengan args: 1, 2. Nombor semasa = 3
Sebelum kaedah panggilan dengan args: 2, 3. Nombor semasa = 5
Sebelum kaedah panggilan dengan args: 3, 5. Nombor semasa = 8
Sebelum kaedah panggilan dengan args: 5, 8. Nombor semasa = 13
Sebelum kaedah panggilan dengan args: 8, 13. Nombor semasa = 21
Sebelum kaedah panggilan dengan args: 13, 21. Nombor semasa = 34
Sebelum kaedah panggilan dengan args: 21, 34. Nombor semasa = 55
Sebelum kaedah panggilan dengan args: 34, 55. Nombor semasa = 89
Sebelum kaedah panggilan dengan args: 55, 89. Nombor semasa = 144
Sebelum kaedah panggilan dengan args: 89, 144. Nombor semasa = 233
Sebelum kaedah panggilan dengan args: 144, 233. Nombor semasa = 377
Sebelum kaedah panggilan dengan args: 233, 377. Nombor semasa = 610
Sebelum kaedah panggilan dengan args: 377, 610. Nombor semasa = 987
Sebelum kaedah panggil dengan args: 610, 987. Nombor semasa = 1597
Sebelum kaedah panggil dengan args: 987, 1597. Nombor semasa = 2584
Sebelum kaedah panggil dengan args: 1597, 2584. Nombor semasa = 4181
Sebelum kaedah panggilan dengan args: 2584, 4181. Nombor semasa = 6765
Sebelum kaedah panggilan dengan args: 4181, 6765. Nombor semasa = 10946
Sebelum kaedah panggil dengan args: 6765, 10946. Nombor semasa = 17711
Sebelum kaedah panggilan dengan args: 109716 Nombor semasa = 28657
Sebelum kaedah panggilan dengan args: 17711, 28657. Nombor semasa = 46368
Sebelum kaedah panggilan dengan args: 28657, 46368. Nombor semasa = 75025
Sebelum kaedah panggilan dengan args: 46368, 75025. Nombor semasa = 121393
Sebelum kaedah panggilan = 121393 121393. Nombor semasa = 196418
Sebelum kaedah panggilan dengan args: 121393, 196418. Nombor semasa = 317811
Sebelum kaedah panggilan dengan args: 196418, 317811. Nombor semasa = 514229
Sebelum kaedah panggilan dengan args: 317.
kaedah panggilan dengan args: 514229, 832040. Nombor semasa = 1346269
Sebelum kaedah panggil dengan args: 832040, 1346269. Nombor semasa = 2178309
Sebelum kaedah panggilan dengan args: 1346269, 2178309.
Sebelum kaedah panggilan dengan args: 2178309, 3524578. Nombor semasa = 5702887
Sebelum kaedah panggil dengan args: 3524578, 5702887. Nombor semasa = 9227465
Sebelum kaedah panggil dengan args: 5702887, 922746 5702887, 922746
kaedah semasa: 9 27465, 14930352. Nombor semasa = 24157817
Sebelum kaedah panggil dengan args: 14930352, 24157817. Nombor semasa = 39088169
Sebelum kaedah panggil dengan args: 24157817, 39088169. Nombor semasa = 690845 args: 6928 3245986.
Nombor semasa = 102334155
Kaedah sebelum hubungi dengan args: 63245986, 102334155. Nombor semasa = 165580141
Sebelum kaedah panggil dengan args: 102334155, 165580141. Nombor semasa = 267914296
Sebelum kaedah panggil dengan args: 165580141, 267914296. Nombor semasa = 433494437
Sebelum kaedah panggil dengan args: 267914296, 433494437. Nombor semasa = 701408733 Sebelum kaedah panggilan dengan args: 434,149. 34903170
Sebelum
kaedah panggilan dengan args: 701408733, 1134903170. Nombor semasa = 1836311903
Selepas kaedah panggilan dengan args: 701408733, 113490317
Selepas kaedah panggilan dengan args: 433494437, 701408733 Selepas
kaedah panggilan dengan args: 267 463
panggilan dengan kaedah: 2679432 580141, 267914296
Selepas kaedah panggilan dengan args: 102334155, 165580141
Selepas kaedah panggilan dengan args: 63245986, 102334155
Selepas kaedah panggilan dengan args: 39088169, 63245986
Selepas kaedah panggilan dengan args: 24157817, 39088169
Selepas kaedah panggilan dengan args: 14930352, 24157817 Selepas kaedah panggil dengan args: 9227465
, 14930352 Selepas kaedah panggil dengan args: 5702887, 9228 887 Selepas kaedah panggil dengan args : 2178309, 3524578 Selepas kaedah panggilan dengan args: 1346269, 2178309 Selepas kaedah panggilan dengan args: 832040, 1346269 Selepas kaedah panggilan dengan args: 514229, 832040 Selepas kaedah panggilan dengan args: 34917 selepas kaedah panggilan dengan args: 34918 8, 317811 Selepas panggilan kaedah dengan args: 121393, 196418 Selepas panggilan kaedah dengan args: 75025, 121393 Selepas panggilan kaedah dengan args: 46368, 75025











Selepas panggilan kaedah dengan args: 28657, 46368
Selepas panggilan kaedah dengan args: 17711, 28657
Selepas panggilan kaedah dengan args: 10946,
17711 Selepas panggilan kaedah dengan args: 6765, 10946 Selepas panggilan kaedah dengan
args: 4181, 6765
: 2584, 4181
Selepas panggilan kaedah dengan args: 1597, 2584
Selepas panggilan kaedah dengan args: 987, 1597
Selepas panggilan kaedah dengan args: 610, 987
Selepas panggilan kaedah dengan args: 377, 610
Selepas panggilan kaedah dengan args: 233, 377
Selepas panggilan kaedah dengan args: 144, 233
Selepas panggilan kaedah dengan args: 89, 144
Selepas panggilan kaedah dengan args: 55, 89
Selepas panggilan kaedah dengan args: 34, 55
Selepas panggilan kaedah dengan args: 21, 34
Selepas panggilan kaedah dengan args: 13, 21
Selepas panggilan kaedah dengan args: 8, 13
Selepas panggilan kaedah dengan args: 5, 8
Selepas panggilan kaedah dengan args: 3, 5
Selepas panggilan kaedah dengan args: 2, 3
Selepas panggilan kaedah dengan args : 1, 2
Selepas kaedah panggilan dengan args: 1, 1
Selepas kaedah panggilan dengan args: 0, 1

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:

1836311903
1134903170
701408733
433494437
267914296
165580141
102334155
63245986
39088169
24157817
14930352
9227465
5702887
3524578
2178309
1346269
832040
514229
317811
196418
121393
75025
46368
28657
17711
10946
6765
4181
2584
1597
987
610
377
233
144
89
55
34
21
13
8
5
3
2
1
1
0
Komen
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION