เงื่อนไขการออก StackOverflowError

ตัวอย่างของ recursive code ที่ไม่มีเงื่อนไขการออก

ลองมาดูปัญหาที่เกิดซ้ำอีกครั้ง ตัวอย่างเช่น ลองพิจารณาการคำนวณตัวเลขฟีโบนัชชี ทุกคนจะจำได้ว่าลำดับฟีโบนัชชีเป็นลำดับตัวเลขที่ตัวเลขสองตัวแรกคือ 0 และ 1 และแต่ละหมายเลขที่ตามมาจะเท่ากับผลบวกของตัวเลขสองตัวก่อนหน้า

มาเขียนโค้ดเพื่อคำนวณและแสดงตัวเลขเหล่านี้:

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

ก่อนการเรียกครั้งแรกของเมธอดprintFibonacciแบบเรียกซ้ำ ให้พิมพ์ตัวเลขสองตัวแรกของลำดับ: ศูนย์และหนึ่ง เราจำเป็นต้องทำเช่นนี้เนื่องจากวิธีการเรียกซ้ำจะแสดงเฉพาะผลรวมของพารามิเตอร์อินพุต ไม่ใช่พารามิเตอร์เอง

โค้ดดูโอเค: เราได้ตัวเลขสองตัว คำนวณผลรวม พิมพ์บนคอนโซล และเรียกใช้เมธอดprintFibonacciซ้ำอีกครั้ง เราส่งหมายเลขก่อนหน้า (ก่อนหน้า) และหมายเลขปัจจุบัน (ปัจจุบัน) เป็นอาร์กิวเมนต์

จริงๆแล้วรหัสมีข้อผิดพลาดสองข้อ คุณสามารถดูได้หากคุณเรียกใช้รหัส

ข้อผิดพลาดแรกล้นประเภทยาว หมายเลข 104 ในลำดับของเราเป็นค่าลบ แสดงว่า ประเภท ยาวล้น

ข้อผิดพลาดที่สองแตกต่างกัน หลังจากคำนวณตัวเลขประมาณ 12,000 ตัวแล้ว เราจะได้:

ตอนนี้เป็นเวลาที่เหมาะสมในการเรียกคืนเมธอด call stack ใน Java เครื่อง Java เก็บบันทึกการเรียกใช้ฟังก์ชันทั้งหมด ในการทำเช่นนี้ จะใช้คอลเลกชันชนิดพิเศษที่เรียกว่าสแต็ค เมื่อฟังก์ชันหนึ่งเรียกใช้ฟังก์ชันอื่น เครื่อง Java จะพุช StackTraceElement ใหม่ไปยังสแต็ก เมื่อฟังก์ชันสิ้นสุดลง อิลิเมนต์นี้จะถูกลบออกจากสแต็ก ดังนั้น สแตกจะเก็บข้อมูลที่เป็นปัจจุบันเกี่ยวกับสถานะปัจจุบันของสแตกการเรียกใช้ฟังก์ชันเสมอ เอกสารประกอบสำหรับ StackTraceElement กล่าวว่า "โยนทิ้งเมื่อเกิดสแต็กล้นเนื่องจากแอปพลิเคชันเรียกซ้ำลึกเกินไป" JVM ที่รันอยู่มีพื้นที่หน่วยความจำพิเศษสำหรับจัดเก็บเมธอด call stack ขนาดของพื้นที่หน่วยความจำนี้ขึ้นอยู่กับการตั้งค่า OS และ JVM นอกจากเมธอด call stack แล้ว ตัวแปรดั้งเดิม (ค่าเฉพาะของพารามิเตอร์เมธอด) และแอดเดรสของตัวแปรอ้างอิง (ในพื้นที่หน่วยความจำที่เรียกว่า "ฮีป") จะถูกเก็บไว้ในพื้นที่หน่วยความจำพิเศษนี้ การเข้าถึง call stack เป็นไปตามหลักการ LIFO

ตัวอย่างที่แก้ไขด้วยเงื่อนไขการออก

เริ่มต้นด้วยการแก้ไขปัญหาที่สองในรหัส

มาลองแก้ปัญหากันแบบตัวต่อตัว: ถ้าสแต็กเล็กเกินไป มาทำให้มันใหญ่ขึ้นกันเถอะ ในการทำเช่นนี้ ให้เริ่มต้น JVM ด้วยแฟล็ก "-Xss" และระบุจำนวนหน่วยความจำที่จะจัดสรรสำหรับสแต็ก ลองจัดสรร 5 เมกะไบต์ นี่คือสิ่งที่จะมีลักษณะเหมือนใน IDEA:

เราจัดการเพื่อเพิ่มความยาวของเอาต์พุต ตอนนี้สามารถคำนวณลำดับได้มากกว่า 49,000 หมายเลขแทนที่จะถูกจำกัดไว้ที่ประมาณ 12,000 หมายเลข แต่ในบางจุด เรายังคงได้รับStackOverflowError

คุณสามารถลองเพิ่มขนาดของสแต็กได้ แต่นั่นไม่สามารถแก้ไขปัญหาพื้นฐานได้ ลองหาปัญหาในตรรกะกัน จะต้องมีจุดที่การวนซ้ำหยุดลง กล่าวอีกนัยหนึ่ง ต้องมีเงื่อนไขบางอย่างที่กำหนดว่าเมธอด recursive จะไม่ถูกเรียกใช้อีกต่อไปเมื่อใด ทำให้ call stack คลายตัวได้ ในการ กำหนดเงื่อนไขดังกล่าว เรามาทำให้วัตถุประสงค์ของเราชัดเจน: แสดงชุด Fibonacci ตราบเท่าที่ตัวเลขน้อยกว่าInteger.MAX_VALUE

ลองเขียน เมธอด printFibonacciWithCondition ใหม่ ที่จะพิจารณาเงื่อนไขนี้ และเราจะเรียกวิธีการแก้ไขใหม่ในวิธีการหลัก

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

หลังจากรันโค้ดแล้ว เราจะเห็นว่าเอาต์พุตลงท้ายด้วยหมายเลข 1836311903 ตัวเลขก่อนหน้าตัวเลขนี้คือ 1134903170 ผลรวมของตัวเลขเหล่านี้คือ 2_971_215_073 ซึ่งมากกว่า Integer.MAX_VALUE (2_147_483_647 )จริงๆ

การเปลี่ยนแปลงนี้แก้ไขบั๊กโอเวอร์โฟลว์แบบยาว โดยอัตโนมัติ หากคุณต้องการ คำนวณอนุกรมเพิ่มเติม คุณจะต้องใช้ข้อมูลประเภทอื่น เช่นBigInteger

การสืบเชื้อสายแบบเรียกซ้ำและการคลี่คลาย

มาวิเคราะห์ทีละขั้นตอนว่าโค้ดของเราทำงานอย่างไร ในการทำเช่นนี้ เราจะเพิ่ม เมธอด echoและเรียกเมธอดก่อนและหลังการเรียกซ้ำของเมธอด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);
        }
    }
}
    

โปรแกรมให้ผลลัพธ์นี้แก่เรา:

นี่คือการแสดงภาพของสิ่งที่เกิดขึ้น

พูดกันอีกครั้ง: เมธอด printFibonacciWithConditionถูกเรียก มันคำนวณจำนวนปัจจุบัน ถ้ามันเหมาะกับเรา เราจะแสดงมันและเรียกเมธอดprintFibonacciWithConditionอีกครั้งพร้อมกับอาร์กิวเมนต์ใหม่

ตราบใดที่มีการเรียกใช้ recursive method สิ่งนี้เรียกว่า "recursive destination" เมื่อการเรียกซ้ำสิ้นสุดลงและการเรียกเมธอดกลับมา เราบอกว่า call stack กำลัง "คลาย"

การเรียกซ้ำเป็นหัวข้อที่น่าสนใจในการเขียนโปรแกรม เพื่อให้จัดการกับเนื้อหาได้ดีขึ้น มาเปลี่ยนภารกิจกันเล็กน้อย งานใหม่คือการส่งออก ตาม ลำดับจากมากไปน้อย ตัวเลขทั้งหมดในอนุกรม Fibonacci ที่ไม่เกินInteger.MAX_VALUE เราได้เขียนโค้ดทั้งหมดที่จำเป็นสำหรับงานนี้แล้ว สิ่งที่เหลืออยู่คือการสลับลำดับการแสดงหมายเลขปัจจุบันและการเรียกใช้วิธีการเรียกซ้ำ นั่นคือในตัวอย่างแรก ตัวเลขที่คำนวณได้แสดงระหว่าง "การลง" แต่ตอนนี้เราต้อง "ลงไปที่ด้านล่างสุด" จากนั้นจึงแสดงตัวเลข "ระหว่างทางกลับขึ้น" และแน่นอน ใน เมธอด หลักเราจะสลับเลขเริ่มต้นสองตัวของลำดับ (ศูนย์และหนึ่ง) หลังจากแสดงเลขเหล่านั้นหลังจากที่เราเรียกเมธอดแบบเรียกซ้ำ เพื่อความสะดวกในการอ่านวิธี.

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

ผลลัพธ์จะเป็น: