Kondisi keluar. StackOverflowError

Contoh kode rekursif tanpa kondisi keluar

Mari kita lihat lagi masalah rekursif. Sebagai contoh, pertimbangkan untuk menghitung angka Fibonacci. Semua orang akan ingat bahwa deret Fibonacci adalah deret numerik di mana dua angka pertama adalah 0 dan 1, dan setiap angka berikutnya sama dengan jumlah dari dua angka sebelumnya.

Mari tulis kode untuk menghitung dan menampilkan angka-angka 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 dari metode printFibonacci rekursif , cetak dua angka pertama dari urutan: nol dan satu. Kita perlu melakukan ini karena metode rekursif hanya menampilkan jumlah dari parameter masukan, bukan parameter itu sendiri.

Kode terlihat oke: kita mendapatkan dua angka, menghitung jumlahnya, mencetaknya di konsol, dan memanggil metode printFibonacci secara rekursif lagi. Kami meneruskan nomor sebelumnya (sebelumnya) dan nomor saat ini (saat ini) sebagai argumen.

Sebenarnya, kode tersebut memiliki dua kesalahan. Anda dapat melihatnya jika Anda menjalankan kode.

Kesalahan pertama meluap tipe panjang . Angka ke-104 dalam deret kita adalah negatif, menunjukkan bahwa tipe long overflow.

Kesalahan kedua berbeda. Setelah menghitung kira-kira 12.000 angka, kami mendapatkan:

Sekarang adalah waktu yang tepat untuk mengingat apa itu tumpukan pemanggilan metode di Jawa. Mesin Java mencatat semua panggilan fungsi. Untuk melakukan ini, ia menggunakan koleksi khusus yang disebut tumpukan. Saat satu fungsi memanggil yang lain, mesin Java mendorong StackTraceElement baru ke tumpukan. Saat fungsi berakhir, elemen ini dihapus dari tumpukan. Oleh karena itu, stack selalu menyimpan informasi terkini tentang keadaan saat ini dari stack pemanggilan fungsi. Dokumentasi untuk StackTraceElement mengatakan bahwa itu adalah "Dilempar ketika stack overflow terjadi karena aplikasi berulang terlalu dalam." JVM yang sedang berjalan memiliki area memori khusus untuk menyimpan tumpukan pemanggilan metode. Ukuran area memori ini bergantung pada pengaturan OS dan JVM. Selain tumpukan pemanggilan metode itu sendiri, variabel primitif (nilai spesifik dari parameter metode) dan alamat variabel referensi (di area memori yang disebut "heap") disimpan di area memori khusus ini. Akses ke tumpukan panggilan mengikuti prinsip LIFO.

Contoh yang diperbaiki dengan kondisi keluar

Mari kita mulai dengan memperbaiki masalah kedua pada kode.

Mari kita coba selesaikan masalah secara langsung: jika tumpukan terlalu kecil, mari kita buat lebih besar. Untuk melakukannya, mulai JVM dengan flag "-Xss" dan tentukan berapa banyak memori yang akan dialokasikan untuk stack. Mari kita coba alokasikan 5 megabyte. Ini akan terlihat seperti di IDEA:

Kami berhasil menambah panjang output. Sekarang dapat menghitung lebih dari 49.000 angka urutan daripada dibatasi sekitar 12.000 angka. Namun pada titik tertentu, kami masih mendapatkan StackOverflowError .

Anda dapat mencoba menambah ukuran tumpukan, tetapi itu tidak menyelesaikan masalah mendasar. Jadi, mari kita cari masalah dalam logika. Harus ada titik ketika rekursi berhenti. Dengan kata lain, harus ada beberapa kondisi yang menentukan kapan metode rekursif tidak lagi dipanggil, memungkinkan tumpukan panggilan untuk bersantai. Untuk menentukan kondisi seperti itu, mari buat tujuan kita eksplisit: tampilkan deret Fibonacci selama angkanya kurang dari Integer.MAX_VALUE .

Mari tulis metode printFibonacciWithCondition baru yang akan mempertimbangkan kondisi ini. Dan kami akan memanggil metode baru yang dikoreksi dalam metode 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);
    }
}

Setelah menjalankan kode, kita melihat bahwa output diakhiri dengan angka 1836311903. Angka sebelum ini adalah 1134903170. Jumlah dari angka-angka ini adalah 2_971_215_073, yang memang lebih besar dari Integer.MAX_VALUE (2_147_483_647 ) .

Perubahan ini secara otomatis memperbaiki bug long overflow. Jika Anda perlu menghitung lebih banyak seri, Anda perlu menggunakan tipe data lain, seperti BigInteger .

Keturunan rekursif dan pelepasan

Mari menganalisis langkah demi langkah bagaimana kode kita dieksekusi. Untuk melakukannya, kita akan menambahkan metode gema dan memanggilnya sebelum dan sesudah pemanggilan rekursif dari metode 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 memberi kita output ini:

Inilah visualisasi dari apa yang terjadi.

Katakan lagi: metode printFibonacciWithCondition dipanggil. Ini menghitung jumlah saat ini. Jika cocok untuk kita, maka kita tampilkan dan panggil kembali metode printFibonacciWithCondition dengan argumen baru.

Selama metode rekursif dipanggil, ini disebut "keturunan rekursif". Ketika rekursif berakhir dan pemanggilan metode kembali, kita mengatakan bahwa tumpukan panggilan "melepas".

Rekursi adalah topik yang menarik dalam pemrograman. Untuk memahami materi dengan lebih baik, mari ubah sedikit tugas kita. Tugas baru adalah menampilkan, dalam urutan menurun, semua angka dalam deret Fibonacci yang tidak melebihi Integer.MAX_VALUE . Kami telah menulis semua kode yang diperlukan untuk tugas ini. Yang tersisa hanyalah menukar urutan menampilkan nomor saat ini dan memanggil metode rekursif. Artinya, pada contoh pertama, angka yang dihitung ditampilkan selama "turun", tetapi sekarang kita perlu "turun ke paling bawah" dan kemudian menampilkan angka "dalam perjalanan kembali". Dan tentu saja, dalam metode utama , kami menukar dua angka awal dari urutan (nol dan satu) setelah menampilkannya setelah kami memanggil metode rekursif. Untuk keterbacaan,metode.

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 adalah: