การเรียกซ้ำใน Java

เพื่อทำความเข้าใจว่าการเรียกซ้ำคืออะไร คุณต้องเข้าใจว่าการเรียกซ้ำคืออะไร ในความเป็นจริง ไม่มีอะไรยากในการทำความเข้าใจฟังก์ชันดังกล่าว คุณต้องเข้าใจให้ดีเพียงครั้งเดียวเท่านั้น และฝึกฝนเมื่อพูดถึงการเขียนโปรแกรม การเรียกซ้ำเกิดขึ้นไม่เพียงแต่ในการเขียนโปรแกรมเท่านั้น แต่ยังเกิดขึ้นในชีวิตจริงด้วย ถือกระจกในมือแล้วยืนหน้ากระจกอีกบาน การสะท้อนของการสะท้อนก็จะสะท้อนในการสะท้อนเป็นต้น คุณจะเห็นการสะท้อนกลับไปสู่อนันต์จำนวนอนันต์ คุณสามารถหาข้อมูลเพิ่มเติมเกี่ยวกับการเรียกซ้ำ "ของจริง" ได้ในบทความ " อุทิศให้กับวันกราวด์ฮอก... ” กลับมาจากโลกแห่งความเป็นจริงสู่ชีวิตประจำวันของโปรแกรมเมอร์กันดีกว่า คำจำกัดความง่ายๆ: ฟังก์ชันแบบเรียกซ้ำใน Javaเป็นฟังก์ชันที่เรียกตัวเองว่า ฉันขอยกตัวอย่างที่ง่ายและเป็นอันตรายมากให้กับคุณ:

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

ทำไมมันถึงเป็นอันตราย? ฉันขอแนะนำให้คุณตรวจสอบด้วยตัวเอง! หากคุณตัดสินใจที่จะผจญภัยครั้งนี้ (และคุณน่าจะเป็นโปรแกรมเมอร์!) เขียนในความคิดเห็นว่า JVM จะเกิดข้อผิดพลาดอะไร =) ตัวอย่างนี้และอื่นๆ อีกมากมาย แสดงให้เห็นว่าต้องใช้การเรียกซ้ำใน Java ด้วย คำเตือน. คุณต้องเข้าใจว่าเหตุใด เมื่อไหร่ และเพราะเหตุใดแนวทางในการแก้ปัญหาดังกล่าวจึงมีความสมเหตุสมผล และตรวจสอบให้แน่ใจว่าฟังก์ชันของคุณไม่เปลี่ยนการทำงานของโปรแกรมให้เป็น "วันกราวด์ฮอก" มีคำจำกัดความที่สำคัญอีกสองคำสำหรับการทำความเข้าใจการเรียกซ้ำ:

• พื้นฐานการเรียกซ้ำ - เงื่อนไขสำหรับการออกจากบล็อกการโทรซ้ำ - วิธีแก้ปัญหาพื้นฐานสำหรับปัญหาภายใต้เงื่อนไขเมื่อไม่จำเป็นต้องเรียกการเรียกซ้ำ
• ขั้นตอนการเรียกซ้ำคือเมื่อฟังก์ชันเรียกตัวเองเมื่อเปลี่ยนพารามิเตอร์

ตัวอย่างคลาสสิกของการใช้ฟังก์ชันเรียกซ้ำคือการคำนวณแฟกทอเรียลของตัวเลข ในกรณีที่คุณลืม ฉันขอเตือนคุณว่า แฟกทอเรียลของจำนวนเต็มบวกN(เขียนแทนด้วย N!) คือผลคูณของตัวเลข1 до N: N! = 1 * 2 * 3 * … (N - 1) * Nจาก อย่างไรก็ตาม แฟกทอเรียลของศูนย์ตามคำจำกัดความจะเท่ากับ 1 ดังนั้นแฟกทอเรียลสามารถพบได้สำหรับจำนวนเต็มบวกและศูนย์ (ในภาษาคณิตศาสตร์ - สำหรับเซตของจำนวนเต็มที่ไม่เป็นลบหรือสำหรับเซตของจำนวนธรรมชาติและ ศูนย์). ฉันคิดว่าคุณเข้าใจว่าคุณสามารถโปรแกรมแฟคทอเรียลโดยใช้ลูปได้ จริงๆ แล้ว นี่เป็นวิธีการแบบไม่เรียกซ้ำสำหรับการแก้ปัญหานี้:

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

เรามาเพิ่มการตรวจสอบว่าตัวเลขเป็นจำนวนบวกและจำนวนเต็ม และเช็คแยกต่างหากสำหรับศูนย์

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

ตอนนี้ฉันจะให้รหัสวิธีการสำหรับการแก้ปัญหานี้แบบเรียกซ้ำ:

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

ลองดูผลลัพธ์ของการโทร:

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

เราได้รับค่าที่คาดหวัง:

1
1
2
6
24
120
720

มาเพิ่มผลลัพธ์ที่ดีและคำนวณแฟกทอเรียลสำหรับจำนวนที่มากขึ้น:

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) + "!");

เราได้รับ: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! ในกรณีนี้ การใช้ฟังก์ชันแบบเรียกซ้ำนั้นสมเหตุสมผลและปลอดภัย เราได้กำหนดเงื่อนไขในการออกจากบล็อกแบบเรียกซ้ำอย่างชัดเจน และเรามั่นใจว่าสามารถทำได้: เราป้อนตัวเลขจำนวนเต็มที่ไม่เป็นลบ หากตัวเลขเท่ากับศูนย์หรือหนึ่ง เราจะส่งคืนผลลัพธ์ หากตัวเลขมากกว่า เราคูณผลลัพธ์ด้วยฟังก์ชันของn-1ตัวเลข ใช้แฟกทอเรียลของสามเป็นตัวอย่าง:

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

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

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

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

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

ข้อควรระวังในการใช้งาน: ช่องโหว่ของฟังก์ชันนี้คืออะไร? หากคุณให้วิธีการเป็นจำนวนลบเป็นพารามิเตอร์ ให้ตรวจสอบ

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

ไม่สมเหตุสมผล และเราจะจบลงด้วยการเรียกตัวเองอย่างไม่รู้จบ ควรเพิ่มการตรวจสอบการไม่เชิงลบ:

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

และทุกอย่างจะดี ข้อดีของวิธีหนึ่งเหนืออีกวิธีหนึ่งคืออะไร? ดูเหมือนจะไม่มีความแตกต่างมากนัก แต่ในความเป็นจริงแล้ว การเรียกซ้ำจำนวนมากจะส่งผลเสียต่อประสิทธิภาพและการใช้หน่วยความจำ: call stack เป็นทรัพยากรที่แทบจะควบคุมไม่ได้ และภายใต้เงื่อนไขที่แตกต่างกันสำหรับการเรียกใช้ฟังก์ชันเรียกซ้ำเดียวกัน เราอาจหรืออาจจะไม่ประสบปัญหาที่เกี่ยวข้องกับทรัพยากรนี้ ปัญหาเกือบทั้งหมดได้รับการแก้ไขโดยใช้การวนซ้ำ (วงจรเช่นfor-each) ก็สามารถแก้ไขได้แบบวนซ้ำเช่นกัน ข้อดีของการเรียกซ้ำคืออ่านง่ายและเขียนได้ง่าย เราได้พูดถึงข้อเสียข้างต้นแล้ว: โอกาสที่จะ "ยิงเท้าตัวเอง" ไม่ใช่เรื่องลวงตา คุณต้องระมัดระวังให้มากขึ้นเมื่อใช้สิ่งที่เรียกว่า “การเรียกซ้ำแบบซับซ้อน”: ฟังก์ชันA()จะเรียกใช้ฟังก์ชันB()ที่เรียกใช้ฟังก์ชันA()การแก้ปัญหาดังกล่าวต้องอาศัยความเข้าใจอย่างถ่องแท้เกี่ยวกับวิธีการทำงานของการเรียกซ้ำ ตัวอย่างของงานดังกล่าว: การคำนวณค่าของx^n/(n!). แฟกทอเรียลดังที่เราได้กล่าวไว้ข้างต้น ถูกกำหนดบนเซตของจำนวนเต็มที่ไม่เป็นลบ สุดท้ายนี้ผมจะให้โค้ดการแก้ปัญหา การเรียกซ้ำแบบซับซ้อนจะประกอบด้วยสองวิธี:

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

ในการป้อน การ เรียกซ้ำ จะใช้เมธอดcalculateซึ่งจะเรียกเมธอดpowerซึ่งจะเรียกเมธอด calculateเรากำหนดพื้นฐานการเรียกซ้ำในวิธียกกำลัง:

if (n == 1) return x;

ขั้นตอนการเรียกซ้ำถูกกำหนดไว้ที่นั่นด้วย:

return x * calculate(x, n - 1);

สิ่งที่เหลืออยู่คือการเพิ่มการตรวจสอบความถูกต้องของข้อมูลอินพุต:

• จำนวนใดๆ ก็ตามที่ไม่ใช่ศูนย์จะเท่ากับกำลังของ1ศูนย์ ถ้าn = 0อย่างนั้นn! = 1. จำเป็นต้องส่งคืน1.
• ศูนย์กำลังใดๆ มีค่าเท่ากับศูนย์
• เราจะไม่พิจารณา ความไม่แน่นอนของประเภท0^0และจะยอมรับข้อมูลที่ป้อนดังกล่าวว่าไม่ถูกต้อง

จากการตรวจสอบทั้งหมด วิธีการจะมีลักษณะดังนี้:

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

เมื่อเรียกใช้ฟังก์ชันคุณต้องจำไว้ว่าต้องจับข้อผิดพลาด:

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}