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

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:

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:

Đâ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à: