هياكل البيانات: Recursion

بسم الله الرحمن الرحيم

السلام عليكم ورحمة الله وبركاته

 

استأنافا لما بدأنا عنه حول مواضيع هياكل البيانات سنتقطرق اليوم على نوع من أنواع الـ Methods واللتي لها علاقة

بما يليها من مواضيع حول هياكل البيانات، كما ولها طبيقات رياضية كثيرة، والتي سنذكر منه ها هنا.

 

ماذا نعني بـ Recursion ؟

المعنى الحرفي لكلمة Recursion  هو الإستدعاء الذاتي وهذا المعنى لوحده يكفي لتعريفها، فبكل بساطة هو نوع من

أنواع الـMethods والتي تقوم بنداء نفسها، ولهذه Method هيكلة وأساسيات لابد من توافرها في هذه Method.

 

الشكل العام للـRecursion Methods:

public void Test1(int i){
  //أي عدد من اسطر الأكواد
  if(){//الحالة الأساسية والتي تقوم بإنهاء النداء الذاتي
  }
  Test1(/*any Value To pass*/);//النداء الذاتي
  //أي عدد من أسطر الأكواد
}

الأمر المهم الذي يجب عدم نسيانه هو الحالة الأساسية وهي عبارة عن شرط هذا الشرط

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

شبيه بالشرط الذي نضعه لإنها loop. وعند نسيان هذا الشرط سوف نواجه نداء لا نهائي من ثم انهيار التطبيق.

 

لفهم معنى Recursion أفضل سوف نقفز مباشرة الى عدد من الأمثلة:

 

١. مضروب العدد Factorial (س!):

ونعني به هنا هو مجموع حاصل ضرب جميع الأرقام من 1 الى العدد س.

ويمكننا حل هذه العملية الحسابية بكل بساطة باستخدام التالي:

public  int  Factorial (int i){
if(i == 0){
return 1;
} else {
return  i *  Factorial (i-1);
}
}

هذه الميثود تأخذ عدد من نوع int وتقوم بإرجاع عدد من نوع int كذلك.

أولا علينا تحديد الحالة الأساسية وفي هذه الحالة ستكون عندما يكون المضروب 0 فإن الناتج هو 1، 

أي عندما نرسل للميثود 0 فإنها تعطينا الناتج 1.

في حال لم نقم بإرسال 0 الى الميثود فإنها ستذهب للخيار الآخر وهو نداء الميثود لنفسها لكن هذا النداء

يحتوي على بعض الأمور التي يجب أخذها بعين الاعتبار، اولها بأننا قمنا بتحديث قيمة i فقمنا بإنقاصها 1؛

وهذا التحديث مهم حيث أنه في حال نسيانه سنواجه نداء لانهائي. الأمر الآخر بأننا قمنا بضرب العدد الحالي بسابقه.

 

لنفرض بأننا قمنا بنداء هذه الميثود كالتالي:

System.out.println(Factorial(4));

في النداء الأول بما أن 4 لا تساوي 0 فإننا سنقوم بالخطوة الثانية:

4 * Factorial(4-1)

وهذا يرسلنا الى النداء الثاني، ومن هذا النداء يتولد لنا:

3 * Factorial(3-1)

وندخل بعدها للنداء الثالث:

2 * Factorial(2-1)

ومنه للنداء الرابع:

1 * Factorial(1-1)

في النداء الخامس قيمة i تساوي 0 وهذا يحقق شرطنا فعندها سنقوم

بإعادة 1 الى آخر نداء لنا أي أننا سنقوم بالتالي وليكن في البال بأننا في حال

قمنا بأكثر من لنداء لنفس الميثود فإنا النداءات سوف تترب في stack أي أن

آخر نداء سوف يحصل على الإجابة قبل غيره. وهذا ينتج لنا التالي:

٢. المجموع للعدد س:

كما فعلنا في مثالنا السابق سنقوم هاهنا باستدعاء متكرر لنفس الميثود والتي ستقوم بدورها بجمع الأعداد من 0 إلى س.

public int SUM(int i){
  if(i == 0){
    return 0;
  } else{
    return i + SUM(i -1);
  }
}

 

٣. طباعة الأعداد:

هنا المستخدم يرسل رقم (س) ونقوم بطباعة الأرقام من س الى 1 بشكل تنازلي :

public void printInt(int i){
  if(i == 1){
    System.out.println(1);
  }else{
    System.out.println(i);
    printInt(i-1);
  }
}

أما في حال أردنا الطباعة بشكل تصاعدي فكل ما علينا فعله هو عكس آخر سطري كود لينتج لدينا:

public void printInt(int i){
  if(i == 1){
    System.out.println(1);
  }else{
    printInt(i-1);
    System.out.println(i);
  }
}

ملاحظة: نداء الميثود لنفسها لا يقتصر على الأرقام فحسب (كما سنرى في المواضيع القادمة بإذن الله) بل إنه أوسع من ذلك؛ لكن لتبسيط الأمور استعنت بمجموعة

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

 

 

اتمنى من الله أني وفقت لإصال المعلومة

في حفظ الله

كلمات دليلية: