كيفية إنشاء العودية في جافا - دالة عودية

العودية هي عملية تحديد شيء ما من حيثبحد ذاتها. فيما يتعلق ببرمجة Java ، فإن العودية هي السمة التي تسمح لطريقة استدعاء نفسها. يقال أن الطريقة التي تطلق على نفسها عودية وتدعم Java العودية.

في البداية قد يبدو هذا وكأنه حلقة لا تنتهي أبدًا ،ويبدو أن طريقتنا لن تنتهي أبدًا. قد يكون هذا صحيحًا في بعض الحالات ، ولكن في الممارسة العملية يمكننا التحقق لمعرفة ما إذا كان شرط معين صحيحًا وفي هذه الحالة الخروج (العودة من) أسلوبنا. الحالة التي ننهي فيها تعاودنا تسمى أ حالة القاعدة. بالإضافة إلى ذلك ، تمامًا كما هو الحال في الحلقة ، يجب علينا تغيير بعض القيمة والتقدم التدريجي بالقرب من الحالة الأساسية.

يجب أن يكون لكل عودة الخصائص التالية:

1. حالة أساسية بسيطة لدينا حل لها وقيمة إرجاع.
2. طريقة لتقريب مشكلتنا من الحالة الأساسية. أي طريقة لتقطيع جزء من المشكلة للحصول على مشكلة أبسط إلى حد ما.
3. استدعاء عودي يعيد المشكلة الأبسط إلى الطريقة.

مزايا

السبب الرئيسي للطرق العودية هو أنها يمكن أن تكونتستخدم لإنشاء إصدارات أوضح وأبسط من العديد من الخوارزميات مما يمكن لأقاربها التكراريين. على سبيل المثال ، يصعب تنفيذ خوارزمية الفرز QuickSort بطريقة تكرارية.

سلبيات

قد يتم تنفيذ الإصدارات العودية للعديد من الإجراءاتأبطأ قليلاً من المكافئ التكراري بسبب الحمل الإضافي الإضافي لاستدعاءات الوظائف الإضافية. يمكن أن تتسبب العديد من المكالمات العودية إلى طريقة في تجاوز المكدس. نظرًا لتخزين المعلمات والمتغيرات المحلية ، من الممكن أن يتم استنفاد المكدس. في حالة حدوث ذلك ، سيؤدي نظام وقت تشغيل جافا إلى حدوث استثناء. ومع ذلك ، ربما لن تقلق بشأن هذا إلا إذا كان روتين العودية متوحشًا.

فمثلا:

int myFactorial(int integer) {
if( integer == 1) {
return 1;
}
else {
return(integer*(myFactorial(integer-1);
}
}

يتم تعريف العودية الذيل على أنها تحدث عندمانداء العودية في نهاية التعليمات العودية. هذا ليس هو الحال مع حل عاملي أعلاه. من المفيد ملاحظة متى تستخدم الخوارزمية التكرار الذيل لأنه في مثل هذه الحالة ، يمكن عادة إعادة كتابة الخوارزمية لاستخدام التكرار بدلاً من ذلك. في الواقع ، سيقوم المترجم (أو على الأقل يجب) بتحويل البرنامج العودي إلى برنامج تكراري. هذا يحل المشكلة المحتملة لتجاوز سعة المكدس.

ليس هذا هو الحال مع عودية الرأس ، أو متىتستدعي الوظيفة نفسها بشكل متكرر في أماكن مختلفة مثل حل أبراج هانوي. بالطبع ، حتى في هذه الحالات ، يمكننا أيضًا إزالة التكرار باستخدام مكدسنا الخاص بنا ومحاكاة كيفية عمل التكرار بشكل أساسي.

في مثال عاملي فوق المترجمسيتعين عليه استدعاء الدالة العودية قبل إجراء الضرب لأنه يجب أن يحل قيمة (الإرجاع) للدالة قبل أن يتمكن من إكمال الضرب. لذا فإن أمر التنفيذ سيكون العودية "رأس" ، أي يحدث العودية قبل العمليات الأخرى.

لتحويل هذا إلى العودية الذيل نحتاج للحصول عليهتم الانتهاء من جميع عمليات الضرب وحلها قبل استدعاء الوظيفة بشكل متكرر. نحن بحاجة إلى فرض ترتيب العملية حتى لا ننتظر الضرب قبل العودة. إذا فعلنا ذلك ، يمكن تحرير إطار المكدس.

سبق لك أن رأيت برنامج Java لحساب عاملي العدد الصحيح.

الطريقة الصحيحة للقيام بعامل خلفي متكرر هي:

int factorial(int number) {
if(number == 0) {
return 1;
}
factorial_i(number, 1);
}
int factorial_i(int currentNumber, int sum) {
if(currentNumber == 1) {
return sum;
} else {
return factorial_i(currentNumber - 1, sum*currentNumber);
}
}

لاحظ أنه في عودة المكالمةfactorial_i (currentNumber - 1 ، sum * currentNumber) ؛ كلا المعلمتين قابلة للحل على الفور. يمكننا حساب ماهية كل معلمة دون انتظار استدعاء دالة عودية للعودة. هذا ليس هو الحال مع الإصدار السابق من مضروب. يتيح هذا الانسياب للمترجم تقليل استخدام المكدس كما هو موضح أعلاه.

يمكنك أيضًا أخذ الرقم من المستخدم كوسيطة سطر أوامر.

برنامج Java Recursion

class Factorial{
int fact(int n){
int result;
if ( n ==1)
return 1;
result = fact (n-1) * n;
return result;
}
}
class Recursion{
public static void main (String args[]){
Factorial f =new Factorial();
System.out.println("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));
}
}

انتاج |

شرح كود و مخرجات الجافا

إذا كنت غير مألوف مع أساليب العودية ، ثم عملية حقيقة () قد تبدو مربكة بعض الشيء. إليك كيف تعمل. متى حقيقة () يتم استدعاء مع وسيطة 1 ، ترجع الدالة 1 ؛ وإلا فإنها ترجع منتج حقيقة (ن -1) * ن. لتقييم هذا التعبير ، حقيقة () يسمى ن -1. تتكرر هذه العملية حتى ن يساوي 1 وتبدأ استدعاءات الطريقة للعودة.

لفهم أفضل كيف حقيقة () الطريقة ، دعنا نذهب من خلال مثال قصير. عندما تحسب مضروب الرقم 3 ، فإن أول استدعاء لـ حقيقة () سيؤدي إلى إجراء مكالمة ثانية بحجة 2. سيؤدي هذا الاستدعاء حقيقة () ليتم استدعاؤها للمرة الثالثة بحجة 2. سترجع هذه المكالمة 1 ، والتي يتم استدعاؤها بعد ذلك مرة ثالثة مع وسيطة 1. ستعود هذه المكالمة 1 ، ثم يتم ضربها في 2 (قيمة ن في الدعاء الثاني). ثم يتم إرجاع هذه النتيجة (وهي 2) إلى الاستدعاء الأصلي لـ حقيقة () واضرب في 3 (القيمة الأصلية لـ ن). هذا يعطي الإجابة ، 6. قد تجد أنه من المثير للاهتمام إدراج println () التصريحات في حقيقة () والتي ستظهر على مستوى كل مكالمة وما هي الإجابات المتوسطة.

عندما تطلق إحدى الطرق نفسها ، المتغيرات المحلية الجديدةويتم تخصيص المعلمات للتخزين على المكدس ، ويتم تنفيذ رمز الطريقة مع هذه المتغيرات الجديدة من البداية. لا تقوم المكالمة العودية بعمل نسخة جديدة من الطريقة. الحجج فقط جديدة. مع عودة كل مكالمة متكررة ، تتم إزالة المتغيرات والمعلمات المحلية القديمة من المكدس ، ويستأنف التنفيذ عند نقطة الاستدعاء داخل الطريقة.

بعد ذلك سنتعلم كيفية التعامل معها صفيف في جافا.

اطلع على المزيد من البرامج التعليمية المفيدة والمبادئ التوجيهية النهائية حول برمجة Java هنا.