العودية في جافا

لفهم ما هو العودية، عليك أن تفهم ما هو العودية. في الواقع، لا يوجد شيء صعب في فهم مثل هذه الوظائف، ما عليك سوى فهمها جيدًا مرة واحدة فقط. والتدرب عندما يتعلق الأمر بالبرمجة. لا يحدث العودية في البرمجة فحسب، بل في الحياة الواقعية أيضًا. خذ مرآة بين يديك وقف أمام مرآة أخرى. سوف ينعكس انعكاس الانعكاس في الانعكاس وما إلى ذلك. سترى عددًا لا حصر له من الانعكاسات تصل إلى ما لا نهاية. يمكنك العثور على المزيد حول العودية "الحقيقية" في المقالة " مخصص ليوم جرذ الأرض... " دعنا نعود من العالم الحقيقي إلى الحياة اليومية للمبرمج. تعريف بسيط: الوظائف العودية في 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;
}

وسيكون كل شيء على ما يرام. ما هي ميزة طريقة واحدة على أخرى؟ لا يبدو أن هناك فرقًا كبيرًا، ولكن في الواقع، سيكون للعديد من الاستدعاءات العودية تأثير سلبي على الأداء واستهلاك الذاكرة: مكدس الاستدعاءات هو مورد لا يمكن التحكم فيه تقريبًا وفي ظل ظروف مختلفة لاستدعاء نفس الوظيفة العودية، قد نواجه أو لا نواجه مشكلات مرتبطة بهذا المورد. 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());
}