Bài báo
Bắt đầu
Bắt đầu học
JavaRush /Blog Java /Random-VI /Đệ quy trong Java
Алексей Дмитревский
Mức độ
Москва

Đệ quy trong Java

Xuất bản trong nhóm
Để hiểu đệ quy là gì, bạn cần hiểu đệ quy là gì. Trên thực tế, không có gì khó khăn khi hiểu những chức năng này, bạn chỉ cần hiểu rõ nó một lần. Và thực hành khi nói đến lập trình. Đệ quy trong Java - 1Đệ quy không chỉ xảy ra trong lập trình mà còn xảy ra trong đời sống thực. Cầm một chiếc gương trong tay và đứng trước một tấm gương khác. Sự phản chiếu của sự phản ánh sẽ được phản ánh trong sự phản ánh và vân vân. Bạn sẽ thấy vô số phản xạ đi vào vô tận. Bạn có thể tìm hiểu thêm về đệ quy “thực” trong bài viết “ Dành riêng cho Ngày con rắn… ” Hãy cùng quay trở lại từ thế giới thực với cuộc sống hàng ngày của một lập trình viên. Định nghĩa đơn giản: Hàm đệ quy trong java là các hàm tự gọi chính nó. Hãy để tôi cho bạn một ví dụ rất đơn giản và rất có hại: 
public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}
Tại sao nó có hại? Tôi đề nghị bạn tự kiểm tra nó! Nếu bạn quyết định thực hiện cuộc phiêu lưu này (và rất có thể bạn sẽ làm như vậy, bạn là lập trình viên!), hãy viết vào phần nhận xét xem JVM sẽ đưa ra lỗi gì =) Ví dụ này và nhiều ví dụ khác chứng minh rằng việc sử dụng đệ quy trong Java phải được tiếp cận với thận trọng. Bạn cần hiểu cách tiếp cận giải quyết vấn đề như vậy là hợp lý ở đâu, khi nào và đảm bảo rằng chức năng của bạn không biến việc thực thi chương trình thành “Ngày con rắn”. Có hai định nghĩa quan trọng hơn để hiểu đệ quy:
  • Cơ sở đệ quy - điều kiện để thoát khỏi khối lệnh gọi đệ quy - giải pháp cơ bản cho bài toán, trong điều kiện không cần gọi đệ quy.
  • Bước đệ quy là khi một hàm gọi chính nó khi thay đổi tham số.
Java-университет
Một ví dụ kinh điển về việc sử dụng hàm đệ quy là tính giai thừa của một số. Trong trường hợp bạn quên, hãy để tôi nhắc bạn: giai thừa của một số nguyên dương N(ký hiệu là N!) là tích của các số từ 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Nhân tiện, giai thừa của số 0 theo định nghĩa bằng 1. Vì vậy, giai thừa có thể được tìm thấy cho bất kỳ số nguyên dương và số 0 nào (theo ngôn ngữ toán học - cho tập hợp các số nguyên không âm hoặc cho tập hợp số tự nhiên và số không). Tôi nghĩ bạn hiểu rằng bạn có thể lập trình giai thừa bằng cách sử dụng vòng lặp. Trên thực tế, đây là một phương pháp không đệ quy để giải quyết vấn đề này: 
private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}
Hãy thêm một kiểm tra để đảm bảo số đó là số dương và số nguyên, đồng thời kiểm tra riêng cho số 0. 
private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}
Bây giờ tôi sẽ đưa ra mã phương thức để giải quyết vấn đề này một cách đệ quy: 
private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}
Hãy xem kết quả đầu ra cho các cuộc gọi: 
System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));
Chúng tôi nhận được các giá trị mong đợi: 
1
1
2
6
24
120
720
Hãy thêm một kết quả đầu ra đẹp và tính giai thừa cho số lớn hơn: 
private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");
Chúng tôi nhận được: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Trong trường hợp này, việc sử dụng hàm đệ quy là hợp lý và an toàn. Chúng tôi đã xác định rõ ràng điều kiện để thoát khỏi khối đệ quy và chúng tôi tin tưởng rằng điều đó có thể đạt được: chúng tôi nhập một số nguyên không âm, nếu số đó bằng 0 hoặc một, chúng tôi trả về kết quả, nếu số đó lớn hơn , chúng ta nhân kết quả với một hàm của số n-1. Sử dụng giai thừa của ba làm ví dụ: 
factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1
Về sự thận trọng khi sử dụng: lỗ hổng của chức năng này là gì? Nếu bạn cung cấp cho một phương thức một số âm làm tham số thì kiểm tra 
if (n == 1 || n == 0) {
    return result;
}
vô nghĩa và chúng ta sẽ kết thúc trong một vòng lặp vô tận gọi tên chính mình. Cần thêm một kiểm tra về tính không tiêu cực: 
if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}
Và tất cả sẽ tốt đẹp. Ưu điểm của phương pháp này so với phương pháp khác là gì? Có vẻ như không có sự khác biệt lớn, nhưng trên thực tế, rất nhiều lệnh gọi đệ quy sẽ có tác động tiêu cực đến hiệu suất và mức tiêu thụ bộ nhớ: ngăn xếp cuộc gọi là một tài nguyên gần như không thể kiểm soát được và trong các điều kiện khác nhau để gọi cùng một hàm đệ quy, chúng tôi có thể gặp hoặc không gặp vấn đề liên quan đến tài nguyên này. Hầu như tất cả các vấn đề được giải quyết bằng cách sử dụng phép lặp (như chu trình for-each) cũng có thể được giải quyết bằng đệ quy. Ưu điểm của đệ quy là dễ đọc và dễ viết, chúng ta đã nói về nhược điểm ở trên: cơ hội “tự bắn vào chân mình” không phải là viển vông. Bạn cần phải cẩn thận hơn nữa khi sử dụng cái gọi là “đệ quy phức tạp”: Một hàm A()sẽ gọi một hàm B()gọi hàm đó A(). Việc giải quyết những vấn đề như vậy đòi hỏi sự hiểu biết đầy đủ về cách thức hoạt động của đệ quy. Một ví dụ về nhiệm vụ như vậy: tính giá trị của x^n/(n!). Giai thừa, như chúng ta đã thảo luận ở trên, được xác định trên tập hợp các số nguyên không âm. Cuối cùng, tôi sẽ đưa ra mã giải pháp. Đệ quy phức tạp sẽ bao gồm hai phương pháp: 
private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}
Để nhập đệ quy, một phương thức được sử dụng calculate, phương thức này gọi một phương thức power, phương thức này lần lượt gọi một phương thức calculate. Chúng tôi đã xác định cơ sở đệ quy trong phương pháp lũy thừa: 
if (n == 1) return x;
Bước đệ quy cũng được xác định ở đó: 
return x * calculate(x, n - 1);
Tất cả những gì còn lại là thêm kiểm tra tính hợp lệ của dữ liệu đầu vào:
  • Bất kỳ số nào khác 0 đều bằng lũy ​​thừa của 0 1. Nếu n = 0, thì n! = 1. Cần phải trả lại nó 1.
  • Số không với mọi lũy thừa đều bằng không.
  • Chúng tôi sẽ không xem xét tính không chắc chắn về loại 0^0và sẽ chấp nhận dữ liệu đầu vào đó là không hợp lệ.
Với tất cả các bước kiểm tra, các phương thức sẽ trông như thế này: 
private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}
À, khi gọi hàm bạn cần nhớ bắt lỗi: 
try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}
Bình luận
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION