CodeGym /Khóa học Java /Mô-đun 2: Lõi Java /Điều kiện thoát. StackOverflowLỗi

Điều kiện thoát. StackOverflowLỗi

Mô-đun 2: Lõi Java
Mức độ , Bài học
Có sẵn

Ví dụ về mã đệ quy không có điều kiện thoát

Hãy xem xét một vấn đề đệ quy khác. Ví dụ, xem xét việc tính toán các số Fibonacci. Mọi người sẽ nhớ rằng dãy Fibonacci là một dãy số trong đó hai số đầu tiên là 0 và 1, và mỗi số tiếp theo bằng tổng của hai số trước đó.

Hãy viết mã để tính toán và hiển thị các số này:


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

Trước lần gọi đầu tiên của phương thức printFibonacci đệ quy , hãy in hai số đầu tiên của dãy: số không và số một. Chúng ta cần làm điều này vì phương thức đệ quy chỉ hiển thị tổng của các tham số đầu vào chứ không hiển thị chính các tham số đó.

Mã có vẻ ổn: chúng tôi nhận được hai số, tính tổng của chúng, in nó trên bàn điều khiển và gọi lại phương thức printFibonacci một cách đệ quy. Chúng tôi chuyển số trước đó (trước) và số hiện tại (hiện tại) làm đối số.

Trên thực tế, mã có hai lỗi. Bạn có thể nhìn thấy chúng nếu bạn chạy mã.

Lỗi đầu tiên là tràn loại dài . Số thứ 104 trong chuỗi của chúng tôi là số âm, cho biết rằng loại dài đã bị tràn.

Lỗi thứ hai là khác nhau. Sau khi tính toán khoảng 12.000 số, chúng tôi nhận được:

Ngoại lệ trong luồng "chính" java.lang.StackOverflowError

Bây giờ là thời điểm thích hợp để nhớ lại ngăn xếp lệnh gọi phương thức trong Java là gì. Máy Java giữ một bản ghi tất cả các lời gọi hàm. Để làm điều này, nó sử dụng một loại bộ sưu tập đặc biệt được gọi là ngăn xếp. Khi một chức năng gọi một chức năng khác, máy Java sẽ đẩy một StackTraceElement mới vào ngăn xếp. Khi chức năng kết thúc, phần tử này được lấy ra khỏi ngăn xếp. Theo đó, ngăn xếp luôn lưu trữ thông tin cập nhật về trạng thái hiện tại của ngăn xếp lời gọi hàm. Tài liệu về StackTraceElement nói rằng đó là "Bị ném khi xảy ra tràn ngăn xếp do ứng dụng lặp lại quá sâu." Một JVM đang chạy có một vùng bộ nhớ đặc biệt để lưu trữ ngăn xếp lệnh gọi phương thức. Kích thước của vùng bộ nhớ này phụ thuộc vào cài đặt hệ điều hành và JVM. Ngoài bản thân ngăn xếp cuộc gọi phương thức, các biến nguyên thủy (các giá trị cụ thể của các tham số phương thức) và địa chỉ của các biến tham chiếu (trong vùng bộ nhớ được gọi là "đống") được lưu trữ trong vùng bộ nhớ đặc biệt này. Truy cập ngăn xếp cuộc gọi tuân theo nguyên tắc LIFO.

Ví dụ đã sửa với điều kiện thoát

Hãy bắt đầu bằng cách khắc phục sự cố thứ hai trong mã.

Hãy cố gắng giải quyết vấn đề trực tiếp: nếu ngăn xếp quá nhỏ, thì hãy làm cho nó lớn hơn. Để thực hiện việc này, hãy khởi động JVM bằng cờ "-Xss" và chỉ định dung lượng bộ nhớ cần phân bổ cho ngăn xếp. Hãy thử phân bổ 5 megabyte. Đây là giao diện trong IDEA:

Chúng tôi quản lý để tăng độ dài của đầu ra. Bây giờ có thể tính toán hơn 49.000 số của dãy số thay vì bị giới hạn trong khoảng 12.000 số. Nhưng tại một số điểm, chúng tôi vẫn nhận được StackOverflowError .

Bạn có thể thử tăng kích thước của ngăn xếp, nhưng điều đó không khắc phục được vấn đề cơ bản. Vì vậy, hãy tìm kiếm một vấn đề trong logic. Phải có một điểm khi đệ quy dừng lại. Nói cách khác, phải có một số điều kiện xác định khi nào phương thức đệ quy sẽ không còn được gọi nữa, cho phép ngăn xếp cuộc gọi được giải phóng. Để xác định một điều kiện như vậy, hãy làm rõ mục tiêu của chúng ta: hiển thị chuỗi Fibonacci miễn là các số của nó nhỏ hơn Integer.MAX_VALUE .

Hãy viết một phương thức printFibonacciWithCondition mới sẽ tính đến điều kiện này. Và chúng ta sẽ gọi phương thức đã sửa mới trong phương thức chính.


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

Sau khi chạy mã, chúng tôi thấy rằng đầu ra kết thúc bằng số 1836311903. Số trước số này là 1134903170. Tổng của các số này là 2_971_215_073, thực sự lớn hơn Integer.MAX_VALUE (2_147_483_647 ) .

Thay đổi này đã tự động sửa lỗi tràn dài . Nếu bạn cần tính toán nhiều chuỗi hơn, bạn sẽ cần sử dụng các loại dữ liệu khác, chẳng hạn như BigInteger .

Đệ quy gốc và thư giãn

Hãy phân tích từng bước mã của chúng tôi được thực thi như thế nào. Để làm điều này, chúng ta sẽ thêm một phương thức echo và gọi nó trước và sau lệnh gọi đệ quy của phương thức 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);
        }
    }
}
    

Chương trình cung cấp cho chúng tôi đầu ra này:

0
1
Trước khi gọi phương thức với args: 0, 1. Số hiện tại = 1
Trước khi gọi phương thức với args: 1, 1. Số hiện tại = 2
Trước khi gọi phương thức với args: 1, 2. Số hiện tại = 3
Trước khi gọi phương thức với args: 2, 3. Số hiện tại = 5
Trước khi gọi phương thức với các đối số: 3, 5. Số hiện tại = 8
Trước khi gọi phương thức với các đối số: 5, 8. Số hiện tại = 13
Trước khi gọi phương thức với các đối số: 8, 13. Số hiện tại = 21
Trước khi gọi phương thức với args: 13, 21. Số hiện tại = 34
Trước khi gọi phương thức với args: 21, 34. Số hiện tại = 55
Trước khi gọi phương thức với args: 34, 55. Số hiện tại = 89
Trước khi gọi phương thức với args: 55, 89. Số hiện tại = 144
Trước khi gọi phương thức với args: 89, 144. Số hiện tại = 233
Trước khi gọi phương thức với args: 144, 233. Số hiện tại = 377
Trước khi gọi phương thức với args: 233, 377. Số hiện tại = 610
Trước khi gọi phương thức với args: 377, 610. Số hiện tại = 987
Trước khi gọi phương thức với các đối số: 610, 987. Số hiện tại = 1597
Trước khi gọi phương thức với các đối số: 987, 1597. Số hiện tại = 2584
Trước khi gọi phương thức với các đối số: 1597, 2584. Số hiện tại = 4181
Trước khi gọi phương thức gọi với args: 2584, 4181. Số hiện tại = 6765
Trước khi gọi phương thức với args: 4181, 6765. Số hiện tại = 10946
Trước khi gọi phương thức với args: 6765, 10946. Số hiện tại = 17711
Trước khi gọi phương thức với args: 10946, 17711. Số hiện tại = 28657
Trước khi gọi phương thức với args: 17711, 28657. Số hiện tại = 46368
Trước khi gọi phương thức với args: 28657, 46368. Số hiện tại = 75025
Trước khi gọi phương thức với args: 46368, 75025. Số hiện tại = 121393
Trước khi gọi phương thức với args: 75025, 121393. Số hiện tại = 196418
Trước khi gọi phương thức với ARGS: 121393, 196418. Số hiện tại = 317811
trước khi gọi phương thức với ARGS: 196418, 317811. Số hiện tại = 514229
trước khi gọi phương thức với ARGS: 317811, 514229. Số hiện tại =
832040 gọi với đối số: 514229, 832040. Số hiện tại = 1346269
Trước khi gọi phương thức với đối số: 832040, 1346269. Số hiện tại = 2178309
Trước khi gọi phương thức với đối số: 1346269, 2178309. Số hiện tại = 3524578
Trước khi gọi phương thức với đối số: 2178309, 3524578. Số hiện tại = 5702887
Trước khi gọi phương thức với đối số: 3524578, 5702887. Số hiện tại = 9227465 Trước khi
gọi phương thức với đối số: 5702887, 9227465. Số hiện tại = 14930352
Trước khi gọi phương thức với đối số: 9 227465, 14930352. Số hiện tại = 24157817
Trước khi gọi phương thức với các đối số: 14930352, 24157817. Số hiện tại = 39088169
Trước khi gọi phương thức với các đối số: 24157817, 39088169. Số hiện tại = 63245986
Trước khi gọi phương thức với các đối số: 39088169, 6 3245986. Số hiện tại = 102334155
Trước phương thức gọi với đối số: 63245986, 102334155. Số hiện tại = 165580141
Trước khi gọi phương thức với đối số: 102334155, 165580141. Số hiện tại = 267914296
Trước khi gọi phương thức với args: 165580141, 267914296. Số hiện tại = 433494437
Trước khi gọi phương thức với args: 267914296, 433494437. Số hiện tại = 701408733 Trước khi gọi phương thức với args: 433494437, 701408733. Số hiện tại = 11 34903170
Trước
cuộc gọi phương thức với args: 701408733, 1134903170. Số hiện tại = 1836311903
Sau khi gọi phương thức với args: 701408733, 113490317
Sau khi gọi phương thức với args: 433494437, 701408733 Sau khi gọi phương thức với args: 267914296, 433494437
Sau khi gọi phương thức
với args: 165580141, 267914296
Sau khi gọi phương thức với các đối số: 102334155, 165580141
Sau cuộc gọi phương thức với các đối số: 63245986, 102334155
Sau cuộc gọi phương thức với các đối số: 39088169, 63245986
Sau cuộc gọi phương thức có args: 24157817, 39088169
Sau cuộc gọi phương thức có args: 14930352, 24157817
Sau cuộc gọi phương thức có args: 9227465, 14930352 Sau cuộc gọi phương thức có args: 5702887, 9227465 Sau cuộc gọi phương thức có args:
3524578
, 5702887
Sau cuộc gọi phương thức với args : 2178309, 3524578
Sau cuộc gọi phương thức có args: 1346269, 2178309
Sau cuộc gọi phương thức có args: 832040, 1346269 Sau cuộc
gọi phương thức có args: 514229, 832040 Sau cuộc gọi phương thức có args: 317811
, 514229
Sau cuộc gọi phương thức có args: 196418, 317811
Sau cuộc gọi phương thức với args: 121393, 196418
Sau cuộc gọi phương thức với args: 75025, 121393
Sau cuộc gọi phương thức với args: 46368, 75025
Sau khi gọi phương thức với args: 28657, 46368
Sau khi gọi phương thức với args: 17711, 28657
Sau khi gọi phương thức với args: 10946,
17711 Sau khi gọi phương thức với args: 6765, 10946
Sau khi gọi phương thức với args: 4181, 6765
Sau khi gọi phương thức với args : 2584, 4181
Sau cuộc gọi phương thức có args: 1597, 2584
Sau cuộc gọi phương thức có args: 987, 1597
Sau cuộc gọi phương thức có args: 610, 987
Sau cuộc gọi phương thức có args: 377, 610
Sau cuộc gọi phương thức có args: 233, 377
Sau Cuộc gọi phương thức với args: 144, 233
Sau cuộc gọi phương thức với args: 89, 144
Sau cuộc gọi phương thức với args: 55, 89
Sau cuộc gọi phương thức với args: 34, 55
Sau cuộc gọi phương thức với args: 21, 34
Sau cuộc gọi phương thức với args: 13, 21
Sau cuộc gọi phương thức với args: 8, 13
Sau cuộc gọi phương thức với args: 5, 8
Sau cuộc gọi phương thức với args: 3, 5
Sau cuộc gọi phương thức với args: 2, 3
Sau cuộc gọi phương thức với args : 1, 2
Sau lời gọi phương thức với args: 1, 1
Sau lời gọi phương thức với args: 0, 1

Đây là một hình dung về những gì đang xảy ra.

Hãy nói lại lần nữa: phương thức printFibonacciWithCondition được gọi. Nó tính toán số hiện tại. Nếu nó phù hợp với chúng tôi, thì chúng tôi sẽ hiển thị nó và gọi lại phương thức printFibonacciWithCondition với các đối số mới.

Miễn là phương thức đệ quy đang được gọi, thì đây được gọi là "hậu duệ đệ quy". Khi đệ quy kết thúc và các lệnh gọi phương thức quay trở lại, chúng tôi nói rằng ngăn xếp cuộc gọi đang "tháo gỡ".

Đệ quy là một chủ đề thú vị trong lập trình. Để xử lý tài liệu tốt hơn, hãy thay đổi nhiệm vụ của chúng ta một chút. Nhiệm vụ mới là xuất ra, theo thứ tự giảm dần, tất cả các số trong chuỗi Fibonacci không vượt quá Integer.MAX_VALUE . Chúng tôi đã viết tất cả mã cần thiết cho nhiệm vụ này. Tất cả những gì còn lại là hoán đổi thứ tự hiển thị số hiện tại và gọi phương thức đệ quy. Đó là, trong ví dụ đầu tiên, số được tính toán được hiển thị trong quá trình "giảm dần", nhưng bây giờ chúng ta cần "giảm xuống tận cùng" và sau đó hiển thị các số "trên đường sao lưu". Và tất nhiên, trong phương thức chính , chúng ta hoán đổi hai số đầu tiên của dãy (không và một) sau khi hiển thị chúng sau khi chúng ta gọi phương thức đệ quy. Để dễ đọc,phương pháp.


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

Đầu ra sẽ là:

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
Bình luận
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION