يوضح هذا البرنامج التعليمي المتعمق حول العودية في Java ما هو العودية مع الأمثلة والأنواع والمفاهيم ذات الصلة. يغطي أيضًا Recursion Vs Iteration:
من دروسنا السابقة في Java ، رأينا النهج التكراري حيث نعلن حلقة ثم ننتقل عبر بنية بيانات بطريقة تكرارية عن طريق أخذ عنصر واحد في a time.
لقد رأينا أيضًا التدفق الشرطي حيث نحتفظ مرة أخرى بمتغير حلقة واحد ونكرر قطعة من الكود حتى يفي متغير الحلقة بالشرط. عندما يتعلق الأمر باستدعاءات الوظائف ، اكتشفنا الطريقة التكرارية لاستدعاءات الوظائف أيضًا.
في هذا البرنامج التعليمي ، سنناقش نهجًا مختلفًا للبرمجة ، أي النهج التكراري.
ما المقصود بالعودة في Java؟
العودية هي عملية تقوم بها دالة أو طريقة باستدعاء نفسها مرارًا وتكرارًا. هذه الوظيفة التي يتم استدعاؤها مرارًا وتكرارًا إما بشكل مباشر أو غير مباشر تسمى "الوظيفة العودية".
سنرى أمثلة مختلفة لفهم العودية. الآن دعنا نرى صيغة العودية.
بناء الجملة العودية
أي طريقة تنفذ العودية لها جزأين أساسيين:
- استدعاء الأسلوب الذي يمكن أن يطلق على نفسه ، أي عودي
- شرط مسبق سيوقف العودية.
لاحظ أن الشرط المسبق ضروري لأي طريقة عودية كما لو لم نفعل ذلك كسرالعودية ثم تستمر في العمل بلا حدود وتؤدي إلى تجاوز سعة المكدس. الشرط الأساسي. سنناقش المزيد حول الشرط الأساسي في القسم التالي.
فهم التكرار في Java
في هذا القسم ، سنحاول فهم عملية العودية ومعرفة كيفية حدوثها. سوف نتعرف على الشرط الأساسي ، تجاوز المكدس ، ونرى كيف يمكن حل مشكلة معينة من خلال العودية وغيرها من التفاصيل.
شرط قاعدة العودية
أثناء كتابة البرنامج العودي ، يجب علينا قدم أولاً الحل للحالة الأساسية. ثم نعبر عن المشكلة الأكبر من حيث المسائل الأصغر.
كمثال ، يمكننا أن نأخذ مشكلة تقليدية لحساب مضروب الرقم. بالنظر إلى الرقم n ، يجب أن نجد عاملاً لـ n يُشار إليه بالرمز n!
الآن دعنا ننفذ البرنامج لحساب مضروب n (n!) باستخدام العودية.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }الإخراج
في هذا البرنامج ، يمكننا أن نرى أن الشرط (n & lt ؛ = 1) هو الشرط الأساسي وعندما يتم الوصول إلى هذا الشرط ، ترجع الوظيفة 1 الجزء الآخر من الوظيفة هو النداء العودي. ولكن في كل مرة يتم استدعاء الطريقة العودية ، يتم إنقاص n بمقدار 1.
وبالتالي يمكننا أن نستنتج أن قيمة n في النهاية ستصبح 1 أو أقل من 1 وعند هذاالنقطة ، ستعيد الطريقة القيمة 1. سيتم الوصول إلى هذا الشرط الأساسي وستتوقف الوظيفة. لاحظ أن قيمة n يمكن أن تكون أي شيء طالما أنها تفي بالشرط الأساسي.
حل المشكلات باستخدام العودية
الفكرة الأساسية وراء استخدام العودية هي التعبير عن المشكلة الأكبر من حيث مشاكل أصغر. أيضًا ، نحتاج إلى إضافة شرط أساسي واحد أو أكثر حتى نتمكن من الخروج من العودية.
وقد تم توضيح ذلك بالفعل في المثال المضروب أعلاه. في هذا البرنامج ، عبرنا عن العامل n (n!) من حيث القيم الأصغر وكان لدينا شرط أساسي (n & lt ؛ = 1) بحيث عندما يصل n إلى 1 ، يمكننا إنهاء الطريقة العودية.
خطأ تجاوز المكدس في العودية
نحن ندرك أنه عند استدعاء أي طريقة أو وظيفة ، يتم تخزين حالة الوظيفة على المكدس ويتم استردادها عند إرجاع الوظيفة. يتم استخدام المكدس للطريقة العودية أيضًا.
ولكن في حالة العودية ، قد تحدث مشكلة إذا لم نحدد الشرط الأساسي أو عندما لا يتم الوصول إلى الشرط الأساسي أو تنفيذه بطريقة ما. إذا حدث هذا الموقف ، فقد ينشأ تجاوز سعة المكدس.
دعونا ننظر في المثال التالي للتدوين المضروب.
هنا قدمنا شرطًا أساسيًا خاطئًا ، n == 100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }لذا عندما n & gt؛ 100 ستعيد الطريقة 1 لكن العودية لن تتوقف. ستستمر قيمة n في التناقص إلى أجل غير مسمى كما هو الحال هناكليس هناك شرط آخر لوقفه. سيستمر هذا حتى يفيض المكدس.
ستكون حالة أخرى عندما تكون قيمة n & lt؛ 100. في هذه الحالة أيضًا ، لن تنفذ الطريقة مطلقًا الشرط الأساسي وتؤدي إلى تجاوز سعة مكدس.
أمثلة العودية في Java
في هذا القسم ، سنقوم بتنفيذ الأمثلة التالية باستخدام العودية.
# 1) سلسلة فيبوناتشي باستخدام العودية
يتم إعطاء سلسلة فيبوناتشي بواسطة ،
1،1،2،3،5،8،13،21 ، 34،55،…
يوضح التسلسل أعلاه أن العنصر الحالي هو مجموع العنصرين السابقين. أيضًا ، العنصر الأول في سلسلة فيبوناتشي هو 1.
لذلك بشكل عام إذا كان n هو الرقم الحالي ، فإنه يُعطى بمجموع (n-1) و (n-2). نظرًا لأن العنصر الحالي يتم التعبير عنه من حيث العناصر السابقة ، فيمكننا التعبير عن هذه المشكلة باستخدام العودية.
البرنامج لتنفيذ سلسلة فيبوناتشي موضح أدناه:
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n = 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ("Fibonacci Series: First 10 numbers:"); for (int i = 1; i = number; i++) { System.out.print(fibonacci(i) + " "); } } } الإخراج
# 2) تحقق مما إذا كان الرقم متماثلًا باستخدام العودية
المتماثل هو تسلسل يتساوى عندما نقرأها من اليسار إلى اليمين أو من اليمين إلى اليسار.
بالنظر إلى الرقم 121 ، نرى أنه عندما نقرأه من اليسار إلى اليمين ومن اليمين إلى اليسار ، فإنه يساوي. ومن ثم فإن الرقم 121 هو متماثل.
لنأخذ رقمًا آخر ، 1242. عندما نقرأه من اليسار إلى اليمين يكون 1242 وعندما نقرأه من اليمين إلى اليسار يُقرأ على أنه 2421. وبالتالي هذا ليس متناظرًا.
نحنقم بتنفيذ برنامج palindrome عن طريق عكس أرقام الأرقام والمقارنة المتتابعة للرقم المعطى بتمثيله المعكوس.
يقوم البرنامج أدناه بتنفيذ البرنامج للتحقق من التناظر.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num 10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { if (num 0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } n = 1221; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } } }الإخراج
# 3) عكس سلسلة التكرار Java
بالنظر إلى السلسلة "Hello" ، يتعين علينا عكسها بحيث السلسلة الناتجة هي "olleH".
يتم ذلك باستخدام العودية. بدءًا من آخر حرف في السلسلة ، نقوم بطباعة كل حرف بشكل متكرر حتى يتم استنفاد جميع الأحرف في السلسلة.
يستخدم البرنامج أدناه العودية لعكس سلسلة معينة.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() = 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("The given string: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("The reversed string: "); obj.reverseString(inputstr); } } الإخراج
# 4) بحث ثنائي بحث Java Recursion
خوارزمية البحث الثنائي هي خوارزمية مشهورة للبحث. في هذه الخوارزمية ، بالنظر إلى مصفوفة مرتبة من عناصر n ، نبحث في هذه المصفوفة عن العنصر الأساسي المحدد. في البداية ، نقسم المصفوفة إلى نصفين من خلال إيجاد العنصر الأوسط من المصفوفة. بهذه الطريقة تتكرر نفس العملية حتى يتم العثور على موقع العناصر الأساسية.
سنقوم بتنفيذ هذه الخوارزمية باستخدام العودية هنا.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray[], int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray[mid] == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray[] = { 4,6,12,16,22}; System.out.println("The given array : " + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " not present"); else System.out.println("Element " + key + " found at index " + result); } } الإخراج
# 5) أوجد القيمة الدنيا في المصفوفة باستخدام العودية
باستخدام العودية يمكننا أيضًا إيجاد القيمة الدنيا في المصفوفة.
ملفبرنامج Java للعثور على الحد الأدنى للقيمة في المصفوفة موضح أدناه.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //return first element if only one element or minimum of the array elements return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Given Array : " + Arrays.toString(numArray)); int n = numArray.length; System.out.print("Minimum element of array: " + getMin(numArray, 0, n) + "\n"); } }الإخراج
هذه بعض من أمثلة العودية. بصرف النظر عن هذه الأمثلة ، يمكن تنفيذ الكثير من المشكلات الأخرى في البرنامج باستخدام تقنيات متكررة. الطريقة العودية.
هم:
# 1) Tail Recursion
عندما يكون استدعاء الطريقة العودية هو البيان الأخير يتم تنفيذه داخل الطريقة العودية ، ويسمى "Tail Recursion".
في العودية الخلفية ، عادة ما يتم تنفيذ بيان الاستدعاء العودي مع بيان الإرجاع الخاص بالطريقة.
يرد أدناه بناء الجملة العام لعودة الذيل:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) عودة الرأس
عودية الرأس هي أي نهج تكراري ليس تكرارًا ذيلًا. حتى العودية العامة هي العودية الأمامية.
بناء جملة العودية على النحو التالي:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } العودية مقابل التكرار في Java
| العودية | التكرار |
|---|---|
| العودية هي عملية تستدعي فيها الطريقة نفسها بشكل متكرر حتى يتم استيفاء شرط أساسي. | التكرار هو عملية يتم من خلالها تنفيذ جزء من التعليمات البرمجية بشكل متكرر لعدد محدود من المرات أو حتى يتم استيفاء شرط. |
| هو تطبيق للوظائف. | قابل للتطبيق للحلقات. |
| يعمل جيدًا معحجم رمز أصغر. | يعمل جيدًا مع حجم رمز أكبر. |
| يستخدم المزيد من الذاكرة حيث يتم دفع كل مكالمة متكررة إلى المكدس | ذاكرة أقل نسبيًا |
| من الصعب تصحيح الأخطاء والحفاظ عليها | أسهل في تصحيح الأخطاء والحفاظ عليها |
| النتائج في تجاوز سعة المكدس إذا كانت القاعدة لم يتم تحديد الشرط أو لم يتم الوصول إليه. | قد ينفذ بلا حدود ولكنه سيوقف التنفيذ في النهاية مع أي أخطاء في الذاكرة |
| تعقيد الوقت مرتفع جدًا. | التعقيد الزمني نسبيًا في الجانب السفلي. |
الأسئلة المتداولة
Q # 1) كيف يعمل Recursion في Java؟
الإجابة: في العودية ، تستدعي الدالة العودية نفسها بشكل متكرر حتى يتم استيفاء الشرط الأساسي. يتم دفع ذاكرة الوظيفة التي تم استدعاؤها إلى المكدس الموجود أعلى الذاكرة لوظيفة الاستدعاء. لكل استدعاء دالة ، يتم عمل نسخة منفصلة من المتغيرات المحلية.
Q # 2) لماذا يتم استخدام Recursion؟
الجواب: العودية تستخدم لحل تلك المشاكل التي يمكن تقسيمها إلى مشاكل أصغر ويمكن التعبير عن المشكلة بأكملها من حيث مشكلة أصغر.
العودية تستخدم أيضا لتلك المشاكل أيضا معقدة ليتم حلها باستخدام نهج تكراري. إلى جانب المشاكل التي لا يمثل تعقيد الوقت مشكلة فيها ، استخدم العودية.
Q # 3) ما هي فوائدالعودية؟
الإجابة:
تشمل فوائد العودية:
- يقلل الاستدعاء من الاتصال الزائد من الوظيفة.
- يتيح لنا التكرار حل المشكلات بسهولة عند مقارنتها بالنهج التكراري.
Q # 4) أيهما أفضل - العودية أم التكرار؟
الإجابة: تقوم العودية بإجراء مكالمات متكررة حتى يتم الوصول إلى الوظيفة الأساسية. وبالتالي ، يوجد حمل للذاكرة حيث يتم دفع ذاكرة لكل استدعاء دالة إلى المكدس.
التكرار من ناحية أخرى لا يحتوي على الكثير من الذاكرة الزائدة. تنفيذ العودية أبطأ من الأسلوب التكراري. يقلل العودية من حجم الكود بينما الأسلوب التكراري يجعل الشفرة كبيرة.
Q # 5) ما هي مزايا العودية على التكرار؟
الإجابة:
- العودية تجعل الكود أكثر وضوحًا وأقصر.
- التكرار أفضل من الأسلوب التكراري لمشاكل مثل برج هانوي ، الشجرة عمليات الاجتياز ، إلخ.
- نظرًا لأن كل استدعاء دالة به ذاكرة مدفوعة إلى المكدس ، فإن العودية تستخدم المزيد من الذاكرة.
- أداء التكرار أبطأ من الأسلوب التكراري.
الخلاصة
التكرار مفهوم مهم جدًا في البرنامج بغض النظر عن لغة البرمجة. تُستخدم العودية في الغالب في حل مشاكل بنية البيانات مثل أبراج هانوي ، واجتياز الأشجار ، والقوائم المرتبطة ، وما إلى ذلك ، على الرغم من أنها تتطلب المزيد من الذاكرة ،العودية تجعل الكود أبسط وأوضح.
لقد اكتشفنا كل شيء عن العودية في هذا البرنامج التعليمي. لقد قمنا أيضًا بتنفيذ العديد من الأمثلة البرمجية لفهم أفضل للمفهوم.