تقييم الموضوع :
  • 0 أصوات - بمعدل 0
  • 1
  • 2
  • 3
  • 4
  • 5
[مقال] الـ Recursive Methods
#1
السلام عليكم ورحمة الله وبركاته


سنتكلم في هذا المقال عن شيئ جميل وهو يعتبر احد اساليب برمجة الدوال او كما يطلق عليها (Methods).

ربما أغلبكم قام بتطبيق هذا الاسلوب في احد الايام ، ولكن ربما لم يعرف ان هذا اسلوب معروف جدا يستعمل كثيرا عند كتابة الدوال وله مخاطر عظيمة.

في هذه المقالة سنسلط الضوء على هذه Recursive Methods سنبين ماهي ، متى نستعملها ، وماهي اخطارها ، وماهي بدائلها.






ماهي الـ Recursive Method


الـ Recursive Method هي الدالة التي تستدعي نفسها بإستمرار حتى يقوم شرط ما بإيقافها.



ابسط مثال لإستخدام الـ Recursive هو عند كتابة دالة تحسب المضروب الرياضي ( !n  ) :

PHP كود :
static void Main(string[] args)
{
    
console.Write(factorial(10));
}
//recursive method
public long Factorial(int n)
{
 
   if (== 0)//شرط الايقاف
 
       return 1;
 
   return n Factorial(1); //الاستدعاء الذاتي



هذا ماسيحصل عند تشغيل الكود اعلاه في محرر السي شارب :



نعم سترجع الدالة العدد 3628800 وهو فعلا مضروب العدد 10 ، وقد قامت الدالة برحلة تطلبت استدعاء نفسها 10 مرات حتى ترجع ذلك الناتج   Undecided .

الان يوجد شيئ خطير في اسلوب الـ Recursive  وهو ما يتعلق بشرط الايقاف (يسمى بـ termination condition ) وهو يعتبر الخطر الاول في اسلوب الـ Recursive ، فإذا لعبت بشرط الايقاف وجعلته كالتالي :-

PHP كود :
    if (n>11//شرط الايقاف
 
           return(1); 


هل تظن ان الدالة ستتوقف عن استدعاء نفسها ؟؟ لا ابدا  Big Grin ـ ستستمر بإستدعاء نفسها الى يوم القيامة مالم يوقفها خطأ StackOverFlow اولا  Sleepy .


وخطأ StackOverFlow هو الخطر الثاني في اسلوب Recursive وسنوضح قصته لاحقا في المقالة .

اذن يجب ان يكون شرط الايقاف مدروسا بدقة لتفادي التهنيج الابدي .





متى نستخدم الـ Recursive Method


يعرف على ان الـ  Recursive method  تستعمل للدوران على كائنات ذات علاقة شجرية (parent-child relationship) ، وكمثال على هذه العلاقة يوجد لدينا الاداة المعروفة TreeView





-الان ماذا ستفعل اذا طلب منك الدوران على جميع الـ Nodes ووضع علامة Check بجانبهم ؟

هل تضن ان loop مثل هذا يفي بالغرض ؟ :

PHP كود :
           foreach (TreeNode node in treeView1.Nodes)
 
           {
 
               node.Checked true;
 
           


بالتأكيد انت مبرمج ذكي  Cool وتعرف ان اللوب السابق لايسمن ولايغني عن جوع ولا يحقق هدفنا ، لأنه سيجلب الـ root node فقط ( فيجوال بيسك العرب)

ماذا عن الباقي ؟؟ كيف اقوم بالدوران عليهم ؟؟
هنا لابد لنا من استعمال الـ Recursive Method Cool :-

PHP كود :
       private void Form1_Load(object senderEventArgs e)
 
       {
 
           CheckAllNodes(treeView1.Nodes[0]);
 
       }

 
       //Recursive Method
 
       public void CheckAllNodes(TreeNode parentNode)
 
       {
 
           parentNode.Checked true;

 
           foreach (TreeNode node in parentNode.Nodes)
 
           {
 
               CheckAllNodes(node); //الاستدعاء الذاتي
 
           }
 
       


قد تتسائل اين شرط الايقاف الذي يخرجنا من الـ Recursive عند انتهاء المطلوب ؟ .. الجواب هو ان الـ foreach تخرج نقسها تلقائيا عند انتهاء الدوران على الجميع .

ولكن ان اردت رؤية الـ termination condition لايوجد لدي مانع Cool  ، سأحول الـ foreach الى for loop لتراه بشكل مباشر :-



PHP كود :
       //Recursive Method
 
       public void CheckAllNodes(TreeNode parentNode)
 
       {
 
           parentNode.Checked true;

 
           for (int i 0parentNode.Nodes.Counti++)
 
           {
 
               CheckAllNodes(parentNode.Nodes[i]); //الاستدعاء الذاتي
 
           }
 
       

حيث سيعتبر i < parentNode.Nodes.Count هو شرط استمرار الـloop وتحقق عكسه يعني توقف الـ loop وبالتالي توقف الـ recursive function Smile.







--


وهذه حالة اخرى تستعمل فيها الـ Recursive Method بنفس الطريقة السابقة وذلك للوصول الى جميع الـControls :





--


وقد تستخدم الـ Recursive في عملية الغوص في مجلدات واقراص  الويندوز للبحث عن ملفات معينة.


فكم قلت ، اغلبكم استخدم هذا الاسلوب في كتابة الFunction ولكنه قد يجهل اسمه وقصته .

فالخلاصة : نستفيد في الـ Recursive Function في تنفيذ نفس الكود على كائنات لها علاقة child-parent







أخطار الـ Recursive Method


ذكرنا في بداية المقالة اهم مكون في اسلوب الـ Recursive وهو termination condition ، ونوهنا على اهميته في تجنب الحصول على تكرار ابدي لن يتوقف الا بحصول خطأ الـ Stackoverflow ..

الان حتى لو تجنبنا خطر termination condition  وكتبنا شرط جيد ومنطقي لن يسبب اي مشاكل ، هناك خطر محدق اخر وهو خطر شديد ولا مهرب منه ..

وهو خطأ يحصل عندما تقوم بإستدعائات كثيرة لنفس الدالة من نفس الدالة ..



في الحقيقة هذا العيب الكبير في هذا الاسلوب ، حتى لو صنعت دالة Recursive مثالية وكانت كل اكوادك صحيحة ومنطقية .. هذا الخطأ لايعرف الرحمة ..

فيحدث هذا الخطأ دائما عند إمتلاء الـ Stack وهو مكان في الذاكرة مخصص للتطبيق يخزن فيه معومات الـ Method كـ (عنوانها ، بارمتراتها و قيم بعض المتغيرات التي بداخلها) ، فعند استدعاء Method معين ، يتم عمل Push للـ Method الى الـ stack:



فتخيل انك تريد ناتج مضروب العدد 3000 باستعمال الدالة التي عرضناها في بداية الموضوع ،،، ذلك يعني ان الدالة ستستدعي نفسها 3000 مرة للحصول على الناتج ، بعبارة اخرى سيتم دفع 3000 نسخة من نفس الدالة الى الـ  stack :

PHP كود :
static void Main(string[] args)
{
    
console.Write(factorial(3000));
//error stackoverflow
}

//recursive method
public decimal Factorial(int n)
{
 
   if (== 0)//شرط الايقاف
 
       return 1;
 
   return n Factorial(1); //الاستدعاء الذاتي


جرب الكود ، واذا لم يظهر الخطأ ، قم بزيادة الـ 3000 الى رقم اكبر

هل تظن ان نظام التشغيل يتهاون معنا ؟؟؟ لا ، فهو يعطي كل تطبيق يعمل عليه مساحة معينة من الـ stack ، فإذا امتلأت.. يقوم بإظهار الخطأ المشهور StackOverFlow وبذلك يحصل crash للبرنامج وتنتهي حياته البائسة بنهاية مأساوية . Confused






بدائل الـ Recursive Method



يقول Ellis Horowitz (صاحب كتاب اساسيات هيكلة البيانات بلغة C) :
"
Any program that can be written using assignment, the if-then-else statement and the while statement can also be
written using assignment, if-then-else and Recursion
"

بما معناه : "كل برنامج يستعمل if و الـ Recursion method يمكن عمله باستخدام if + while loop" .
وهذا مايطلق عليه : Iterative method


اذن يوجد عندنا بديلين للـ Recursive Method :
  • Iterative Method
  • Tail Recursive

- طبعا هذه البدائل في كثير من الاحيان تجعل كودك غير نظيف "معكرونة"  Big Grin  ، ولكنها  في النهاية تعتبر بدائل معتبرة .



--------------------



البديل الاول : Iterative method



لا يوجد سر ابدا في هذا Iterative ، فهو مجرد Method تحتوي على while loop بداخلها  او حتى اي loop اخرى . فكما يقولون انه بالامكان تحويل اي Recursive الى Iterative ولكن بالطبع ستصبح الاكواد غبية قليلا.

سنحاول تطبيق مثال الدوران على عناصر الـ Treeview باستعمال الـ Iterative Method هذه المرة ،  فسيصبح لدينا هذا الكود :
PHP كود :
       //Iterative Method
 
       public void CheckAllNodes(TreeNode parentNode)
 
       {
 
           parentNode.Checked true;
 
           Stack<TreeNodenodes = new Stack<TreeNode>();
 
           nodes.Push(parentNode);


 
           while (nodes.Count 0)
 
           {
 
               foreach (TreeNode node in parentNode.Nodes)
 
               {
 
                   node.Checked true;
 
                   nodes.Push(node);
 
               }

 
               parentNode nodes.Pop();
 
           }
 
       

وهذا الكود بالطبع يعطي نفس نتيجة الـ Recursive Method التي عملناها سابقا :


وايضا للمعلومية : كثيرا مايستخدم الكلاس Stack مع الـ Iterative Method .




وايضا اذا اردنا تحويل دالة حساب المضروب من Recursive الى Iterative سيصبح لدينا الكود التالي :
PHP كود :
public long Factorial(int n)
{
 
   if (== 0)
 
       return 1;
 
   long value 1;
 
   for (int i n0i--)
 
   {
 
       value *= i;
 
   }
 
   return value;



فكما نرى كل Recursive ممكن تحويلها الى Iterative ولكن سيصبح الكود اعقد وأعقد ، وخاصة في الخوارزميات المعقدة امثال خوارزميات الترتيب :


فالتعامل مع الـ Recursive احيانا يبسط الامور كثيرا .



-- وفي النهاية هذه مقارنة بين الـ Recursive والـ Iterative في تنفيذ دالة حساب المضروب




يظهر بوضوح التفوق الساحق للـ Iterative.


--------------------



البديل الثاني :  Tail Recursive



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

والسبب في ذلك واضح ، وهو ان بمجرد وصول الCompiler الى اخر تعليمة في اي Method، يقوم بمسح كل مايتعلق بالـ Method من الـ Stack ، فإذا لم يكن كود الاستدعاء الذاتي كآخر تعليمة ، يعني ذلك ان المترجم سيدخل في الاستدعاء الثاني وثم الثالث والرابع ثم يرجع للثالث ثم الثاني ثم الاول . ثم يرجع للدالة الرئيسية main , وهذه مصيبة لان الـ Compiler سيصبح مضطرا لإبقاء معلومات الاستدعاءات السابقة للرجوع اليها لاحقا Sad

فبتأجيل كود الاستدعاء الذاتي لآخر تعليمة ، سيحل مشكلة بقاء معلومات الاستدعائات السابقة في الStack .

ولكن هل السي شارب تدعم هذه الفكرة ، لا .. للاسف الشديد مترجم السي شارب لا يوفر طريقة لتحقيق هذا السيناريو الهندي . والا لكان هذا البديل ممتازا جدا Undecided  .



المشكلة ان اسلوب تطبيق الـ Tail Recursive يختلف من خوارزمية الى اخرى ، فليست له طريقة محددة لتنفيذه . وعند محاولة تنفيذه قد ينتهي بك الامر الى تطبيق الـ Iterative method اصلا . Big Grin  


ادعكم مع هذه المقالة التي تطبق الـ Tail Recursive مع دالة الـ Factorial

Tail recursion in C#







الخاتمة


يظهر ان موضوع الـ Recursive Method مزعج للغاية ، ولذلك يفضل استخدام الـ Recursive في هذه الحالات:
  • عندما يكون تنفيذ الـ Iterative Method صعبا ومعقدا للغاية
  • عندما لا يكون الأداء والسرعة مهمين في مشروعك ، فكما لاحظنا يوجد تفوق ساحق (نسبيا) للـ Iterative Method  من ناحية الاداء
  • عندما لاتكون خوارزميتك عميقة جدا



انتهى
الرد }}}}
#2
مبدع كما عهدناك
موضوع جميل و في العمق , تعجبني عمليات المقارنه لديك
امثلة من صميم الواقع و حلول متعددة
بارك الله فيك اخي الشاكي و زادك من نعمه
اللهم لك الحمد كما ينبغي لجلال وجهك و عظيم سلطانك
في حل و ترحال
الرد }}}}
تم الشكر بواسطة: الشاكي لله
#3
(05-01-17, 04:30 AM)ابو ليلى كتب : مبدع كما عهدناك
موضوع جميل و في العمق , تعجبني عمليات المقارنه لديك
امثلة من صميم الواقع و حلول متعددة
بارك الله فيك اخي الشاكي و زادك من نعمه


حفظكم الله يا ابو ليلى ..


يعطيك العافية .
الرد }}}}
تم الشكر بواسطة: ابو ليلى


المواضيع المحتمل أن تكون متشابهة .
الموضوع : الكاتب الردود : المشاهدات : آخر رد
Lightbulb [مقال] خاطرة في تصميم التوابع Methods عبد الكريم كنعان 1 328 08-02-16, 09:29 AM
آخر رد: myalsailamy

التنقل السريع :


يقوم بقرائة الموضوع: بالاضافة الى ( 1 ) ضيف كريم