Mga kondisyon sa paglabas. StackOverflowError

Halimbawa ng recursive code na walang kondisyon sa paglabas

Tingnan natin muli ang isang recursive na problema. Bilang halimbawa, isaalang-alang ang pagkalkula ng mga numero ng Fibonacci. Matatandaan ng lahat na ang Fibonacci sequence ay isang numerical sequence kung saan ang unang dalawang numero ay 0 at 1, at ang bawat kasunod na numero ay katumbas ng kabuuan ng dalawang naunang numero.

Sumulat tayo ng code upang kalkulahin at ipakita ang mga numerong ito:

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

Bago ang unang tawag ng recursive printFibonacci method, i-print ang unang dalawang numero ng sequence: zero at isa. Kailangan nating gawin ito dahil ipinapakita lamang ng recursive na paraan ang kabuuan ng mga parameter ng input, hindi ang mga parameter mismo.

Mukhang okay ang code: nakakakuha kami ng dalawang numero, kalkulahin ang kanilang kabuuan, i-print ito sa console, at muling tawagan ang paraan ng printFibonacci . Ipinapasa namin ang nakaraang numero (nakaraan) at ang kasalukuyang numero (kasalukuyang) bilang mga argumento.

Sa totoo lang, may dalawang error ang code. Maaari mong makita ang mga ito kung patakbuhin mo ang code.

Ang unang error ay umaapaw sa mahabang uri. Ang ika-104 na numero sa aming sequence ay negatibo, na nagpapahiwatig na ang mahabang uri ay umapaw.

Iba ang pangalawang error. Pagkatapos kalkulahin ang humigit-kumulang 12,000 mga numero, nakukuha namin ang:

Ngayon ay isang angkop na oras upang alalahanin kung ano ang isang method na call stack sa Java. Ang Java machine ay nagpapanatili ng isang talaan ng lahat ng mga function na tawag. Upang gawin ito, gumagamit ito ng isang espesyal na uri ng koleksyon na tinatawag na stack. Kapag ang isang function ay tumawag sa isa pa, ang Java machine ay nagtutulak ng bagong StackTraceElement papunta sa stack. Kapag natapos ang function, ang elementong ito ay aalisin sa stack. Alinsunod dito, ang stack ay palaging nag-iimbak ng up-to-date na impormasyon tungkol sa kasalukuyang estado ng function call stack. Sinasabi ng dokumentasyon para sa StackTraceElement na ito ay "Itinapon kapag naganap ang isang stack overflow dahil ang isang application ay umuulit nang masyadong malalim." Ang isang tumatakbong JVM ay may espesyal na lugar ng memorya para sa pag-iimbak ng method call stack. Ang laki ng lugar ng memorya na ito ay nakasalalay sa mga setting ng OS at JVM. Bilang karagdagan sa mismong method call stack, primitive variable (mga partikular na halaga ng mga parameter ng pamamaraan) at ang mga address ng reference variable (sa isang memory area na tinatawag na "heap") ay naka-imbak sa espesyal na memory area na ito. Ang access sa call stack ay sumusunod sa prinsipyo ng LIFO.

Nawastong halimbawa na may kondisyon sa paglabas

Magsimula tayo sa pamamagitan ng pag-aayos ng pangalawang problema sa code.

Subukan nating lutasin ang problema nang direkta: kung masyadong maliit ang stack, gawin natin itong mas malaki. Upang gawin ito, simulan ang JVM gamit ang flag na "-Xss" at tukuyin kung gaano karaming memory ang ilalaan para sa stack. Subukan nating maglaan ng 5 megabytes. Ito ang magiging hitsura nito sa IDEA:

Nagawa naming taasan ang haba ng output. Ngayon ay maaaring kalkulahin ang higit sa 49,000 mga numero ng pagkakasunud-sunod sa halip na limitado sa humigit-kumulang 12,000 mga numero. Ngunit sa ilang mga punto, nakakakuha pa rin kami ng isang StackOverflowError .

Maaari mong subukang palakihin ang laki ng stack, ngunit hindi nito naaayos ang pangunahing problema. Kaya, maghanap tayo ng problema sa lohika. Dapat may punto kung kailan huminto ang recursion. Sa madaling salita, dapat mayroong ilang kundisyon na tumutukoy kung kailan hindi na tatawagin ang recursive method, na nagpapahintulot sa call stack na mag-unwind. Upang tukuyin ang ganoong kundisyon, gawin nating tahasan ang ating layunin: ipakita ang serye ng Fibonacci hangga't ang mga numero nito ay mas mababa sa Integer.MAX_VALUE .

Sumulat tayo ng bagong paraan ng printFibonacciWithCondition na isasaalang-alang ang kundisyong ito. At tatawagin natin ang bagong corrected method sa pangunahing paraan.

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

Pagkatapos patakbuhin ang code, nakita namin na ang output ay nagtatapos sa numerong 1836311903. Ang numero bago ang isang ito ay 1134903170. Ang kabuuan ng mga numerong ito ay 2_971_215_073, na talagang mas malaki kaysa sa Integer.MAX_VALUE (2_147_483_647 ) .

Awtomatikong naayos ng pagbabagong ito ang mahabang overflow na bug. Kung kailangan mong kalkulahin ang higit pa sa serye, kakailanganin mong gumamit ng iba pang mga uri ng data, gaya ng BigInteger .

Paulit-ulit na pagbaba at pag-unwinding

Suriin natin ang hakbang-hakbang kung paano isinasagawa ang ating code. Upang gawin ito, magdaragdag kami ng paraan ng echo at tatawagin ito bago at pagkatapos ng recursive na tawag ng paraan ng 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);
        }
    }
}
    

Ang programa ay nagbibigay sa amin ng output na ito:

Narito ang isang visualization ng kung ano ang nangyayari.

Sabihin nating muli: ang printFibonacciWithCondition na paraan ay tinatawag. Kinakalkula nito ang kasalukuyang numero. Kung ito ay nababagay sa amin, pagkatapos ay ipapakita namin ito at tawagan muli ang paraan ng printFibonacciWithCondition na may mga bagong argumento.

Hangga't ang recursive method ay tinatawag, ito ay tinatawag na "recursive descent". Kapag natapos ang recursive at bumalik ang mga method call, sinasabi namin na ang call stack ay "unwinding".

Ang recursion ay isang kawili-wiling paksa sa programming. Upang makakuha ng isang mas mahusay na hawakan sa materyal, baguhin natin ang ating gawain nang bahagya. Ang bagong gawain ay i-output, sa pababang pagkakasunud-sunod, ang lahat ng numero sa Fibonacci series na hindi lalampas sa Integer.MAX_VALUE . Naisulat na namin ang lahat ng code na kailangan para sa gawaing ito. Ang natitira na lang ay ang palitan ang pagkakasunud-sunod ng pagpapakita ng kasalukuyang numero at pagtawag sa recursive na paraan. Iyon ay, sa unang halimbawa, ang kinakalkula na numero ay ipinakita sa panahon ng "pagbaba", ngunit ngayon ay kailangan nating "bumaba sa pinakailalim" at pagkatapos ay magpakita ng mga numero "sa daan pabalik". At siyempre, sa pangunahing pamamaraan, pinapalitan namin ang dalawang paunang numero ng pagkakasunud-sunod (zero at isa) pagkatapos ipakita ang mga ito pagkatapos naming tawagan ang recursive na paraan. Para madaling mabasa,paraan.

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

Ang magiging output ay: