Syarat metu. StackOverflowError

Tuladha kode rekursif tanpa syarat metu

Ayo goleki maneh masalah rekursif. Contone, nimbang ngetung angka Fibonacci. Saben uwong bakal ngelingi yen urutan Fibonacci minangka urutan numerik sing rong nomer pisanan yaiku 0 lan 1, lan saben nomer sabanjure padha karo jumlah rong nomer sadurunge.

Ayo nulis kode kanggo ngetung lan nampilake nomer kasebut:

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

Sadurunge telpon pisanan saka cara printFibonacci rekursif , print rong nomer pisanan saka urutan: nul lan siji. Kita kudu nindakake iki amarga cara rekursif mung nampilake jumlah paramèter input, dudu paramèter kasebut.

Kode katon oke: kita njaluk rong nomer, ngetung jumlah sing, print ing console, lan nelpon cara printFibonacci recursively maneh. Kita ngliwati nomer sadurunge (sadurunge) lan nomer saiki (saiki) minangka argumen.

Bener, kode kasebut duwe rong kesalahan. Sampeyan bisa ndeleng yen sampeyan mbukak kode.

Kesalahan pisanan yaiku overflowing jinis dawa . Nomer 104 ing urutan kita negatif, nuduhake yen jinis dawa overflowed.

Kesalahan kapindho beda. Sawise ngitung kira-kira 12.000 nomer, kita entuk:

Saiki iki wektu sing tepat kanggo ngelingi apa stack panggilan metode ing Jawa. Mesin Java nyimpen rekaman kabeh panggilan fungsi. Kanggo nindakake iki, nggunakake koleksi khusus sing diarani tumpukan. Nalika siji fungsi nelpon liyane, mesin Java nyurung StackTraceElement anyar menyang tumpukan. Nalika fungsi rampung, unsur iki dibusak saka tumpukan. Patut, tumpukan tansah nyimpen informasi anyar babagan kahanan saiki tumpukan telpon fungsi. Dokumentasi kanggo StackTraceElement ujar manawa "Dibuwang nalika tumpukan tumpukan kedadeyan amarga aplikasi recurses banget." JVM sing mlaku nduweni area memori khusus kanggo nyimpen tumpukan panggilan metode. Ukuran area memori iki gumantung ing setelan OS lan JVM. Saliyane tumpukan panggilan metode dhewe, variabel primitif (nilai spesifik paramèter metode) lan alamat variabel referensi (ing area memori sing disebut "tumpukan") disimpen ing area memori khusus iki. Akses menyang tumpukan telpon ngetutake prinsip LIFO.

Conto sing didandani kanthi kondisi metu

Ayo dadi miwiti kanthi ndandani masalah kapindho ing kode.

Ayo nyoba ngatasi masalah kasebut kanthi cepet: yen tumpukan kasebut cilik banget, mula dadi luwih gedhe. Kanggo nindakake iki, miwiti JVM karo "-Xss" flag lan nemtokake jumlah memori kanggo nyedhiakke kanggo tumpukan. Coba alokasi 5 megabyte. Iki bakal katon kaya ing IDEA:

Kita bisa nambah dawa output. Saiki bisa ngetung luwih saka 49.000 nomer saka urutan tinimbang diwatesi nganti udakara 12.000 nomer. Nanging ing sawetara titik, kita isih entuk StackOverflowError .

Sampeyan bisa nyoba kanggo nambah ukuran tumpukan, nanging ora ndandani masalah dhasar. Dadi, ayo goleki masalah ing logika. Mesthi ana titik nalika rekursi mandheg. Ing tembung liyane, kudu ana sawetara kondisi sing nemtokake nalika cara rekursif ora bakal disebut maneh, saéngga tumpukan telpon kanggo unwind. Kanggo nemtokake kondisi kasebut, ayo nggawe obyektif kanthi jelas: nampilake seri Fibonacci anggere angka kasebut kurang saka Integer.MAX_VALUE .

Ayo nulis metode printFibonacciWithCondition anyar sing bakal nimbang kondisi kasebut. Lan kita bakal nelpon cara didandani anyar ing cara 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);
    }
}

Sawise mbukak kode, kita weruh yen output rampung karo nomer 1836311903. Nomer sadurunge iki 1134903170. Jumlah nomer kasebut yaiku 2_971_215_073, sing luwih gedhe tinimbang Integer.MAX_VALUE (2_147_483_647 ) .

Owah-owahan iki kanthi otomatis ndandani bug kebanjiran dawa . Yen sampeyan kudu ngetung luwih akeh seri, sampeyan kudu nggunakake jinis data liyane, kayata BigInteger .

Turunan rekursif lan unwinding

Ayo analisa langkah demi langkah carane kode dieksekusi. Kanggo nindakake iki, kita bakal nambah cara gema lan nelpon sadurunge lan sawise telpon rekursif saka 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 menehi output iki:

Mangkene visualisasi apa sing kedadeyan.

Ayo ngomong maneh: cara printFibonacciWithCondition diarani. Iku ngetung nomer saiki. Yen cocog karo kita, banjur kita nampilake lan nelpon metode printFibonacciWithCondition maneh kanthi argumen anyar.

Anggere cara rekursif diarani, iki diarani "turun rekursif". Nalika rekursif mungkasi lan cara telpon bali, kita ngomong yen tumpukan telpon "unwinding".

Rekursi minangka topik sing menarik ing pemrograman. Kanggo entuk pegangan sing luwih apik babagan materi, ayo ngganti tugas kita rada. Tugas anyar kanggo output, ing urutan mudhun, kabeh nomer ing seri Fibonacci sing ora ngluwihi Integer.MAX_VALUE . Kita wis nulis kabeh kode sing dibutuhake kanggo tugas iki. Kabeh sing isih ana yaiku ngganti urutan nampilake nomer saiki lan nelpon metode rekursif. Yaiku, ing conto pisanan, nomer sing diwilang ditampilake nalika "turun", nanging saiki kita kudu "mudhun menyang ngisor" lan banjur nampilake nomer "ing dalan bali". Lan mesthi, ing cara utama , kita ngganti rong nomer awal saka urutan (nol lan siji) sawise nampilake sawise kita nelpon cara rekursif. Kanggo maca,cara.

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

Output bakal: