04-01-17, 08:44 PM
السلام عليكم ورحمة الله وبركاته
سنتكلم في هذا المقال عن شيئ جميل وهو يعتبر احد اساليب برمجة الدوال او كما يطلق عليها (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 (n == 0)//شرط الايقاف
return 1;
return n * Factorial(n - 1); //الاستدعاء الذاتي
}
هذا ماسيحصل عند تشغيل الكود اعلاه في محرر السي شارب :
نعم سترجع الدالة العدد 3628800 وهو فعلا مضروب العدد 10 ، وقد قامت الدالة برحلة تطلبت استدعاء نفسها 10 مرات حتى ترجع ذلك الناتج .
الان يوجد شيئ خطير في اسلوب الـ Recursive وهو ما يتعلق بشرط الايقاف (يسمى بـ termination condition ) وهو يعتبر الخطر الاول في اسلوب الـ Recursive ، فإذا لعبت بشرط الايقاف وجعلته كالتالي :-
PHP كود :
if (n>11) //شرط الايقاف
return(1);
هل تظن ان الدالة ستتوقف عن استدعاء نفسها ؟؟ لا ابدا ـ ستستمر بإستدعاء نفسها الى يوم القيامة مالم يوقفها خطأ StackOverFlow اولا .
وخطأ StackOverFlow هو الخطر الثاني في اسلوب Recursive وسنوضح قصته لاحقا في المقالة .
اذن يجب ان يكون شرط الايقاف مدروسا بدقة لتفادي التهنيج الابدي .
متى نستخدم الـ Recursive Method
يعرف على ان الـ Recursive method تستعمل للدوران على كائنات ذات علاقة شجرية (parent-child relationship) ، وكمثال على هذه العلاقة يوجد لدينا الاداة المعروفة TreeView
-الان ماذا ستفعل اذا طلب منك الدوران على جميع الـ Nodes ووضع علامة Check بجانبهم ؟
هل تضن ان loop مثل هذا يفي بالغرض ؟ :
PHP كود :
foreach (TreeNode node in treeView1.Nodes)
{
node.Checked = true;
}
بالتأكيد انت مبرمج ذكي وتعرف ان اللوب السابق لايسمن ولايغني عن جوع ولا يحقق هدفنا ، لأنه سيجلب الـ root node فقط ( فيجوال بيسك العرب)
ماذا عن الباقي ؟؟ كيف اقوم بالدوران عليهم ؟؟
هنا لابد لنا من استعمال الـ Recursive Method :-
PHP كود :
private void Form1_Load(object sender, EventArgs 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 لايوجد لدي مانع ، سأحول الـ foreach الى for loop لتراه بشكل مباشر :-
PHP كود :
//Recursive Method
public void CheckAllNodes(TreeNode parentNode)
{
parentNode.Checked = true;
for (int i = 0; i < parentNode.Nodes.Count; i++)
{
CheckAllNodes(parentNode.Nodes[i]); //الاستدعاء الذاتي
}
}
حيث سيعتبر i < parentNode.Nodes.Count هو شرط استمرار الـloop وتحقق عكسه يعني توقف الـ loop وبالتالي توقف الـ recursive function .
--
وهذه حالة اخرى تستعمل فيها الـ 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 (n == 0)//شرط الايقاف
return 1;
return n * Factorial(n - 1); //الاستدعاء الذاتي
}
جرب الكود ، واذا لم يظهر الخطأ ، قم بزيادة الـ 3000 الى رقم اكبر
هل تظن ان نظام التشغيل يتهاون معنا ؟؟؟ لا ، فهو يعطي كل تطبيق يعمل عليه مساحة معينة من الـ stack ، فإذا امتلأت.. يقوم بإظهار الخطأ المشهور StackOverFlow وبذلك يحصل crash للبرنامج وتنتهي حياته البائسة بنهاية مأساوية .
بدائل الـ 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
- طبعا هذه البدائل في كثير من الاحيان تجعل كودك غير نظيف "معكرونة" ، ولكنها في النهاية تعتبر بدائل معتبرة .
--------------------
البديل الاول : Iterative method
لا يوجد سر ابدا في هذا Iterative ، فهو مجرد Method تحتوي على while loop بداخلها او حتى اي loop اخرى . فكما يقولون انه بالامكان تحويل اي Recursive الى Iterative ولكن بالطبع ستصبح الاكواد غبية قليلا.
سنحاول تطبيق مثال الدوران على عناصر الـ Treeview باستعمال الـ Iterative Method هذه المرة ، فسيصبح لدينا هذا الكود :
PHP كود :
//Iterative Method
public void CheckAllNodes(TreeNode parentNode)
{
parentNode.Checked = true;
Stack<TreeNode> nodes = 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 (n == 0)
return 1;
long value = 1;
for (int i = n; i > 0; i--)
{
value *= i;
}
return value;
}
فكما نرى كل Recursive ممكن تحويلها الى Iterative ولكن سيصبح الكود اعقد وأعقد ، وخاصة في الخوارزميات المعقدة امثال خوارزميات الترتيب :
فالتعامل مع الـ Recursive احيانا يبسط الامور كثيرا .
-- وفي النهاية هذه مقارنة بين الـ Recursive والـ Iterative في تنفيذ دالة حساب المضروب
يظهر بوضوح التفوق الساحق للـ Iterative.
--------------------
البديل الثاني : Tail Recursive
درس المطورون مشكلة الـ Stackoverflow وبعد ما عرفوا المشكلة كما شرحناها سابقا ، قام المطورون بإبتكار طريقة لتجاوز هذا الموضوع ، وأساس هذه الفكرة تقوم على "تأجيل" استدعاء الدالة لنفسها الى اخر تعليمة .
والسبب في ذلك واضح ، وهو ان بمجرد وصول الCompiler الى اخر تعليمة في اي Method، يقوم بمسح كل مايتعلق بالـ Method من الـ Stack ، فإذا لم يكن كود الاستدعاء الذاتي كآخر تعليمة ، يعني ذلك ان المترجم سيدخل في الاستدعاء الثاني وثم الثالث والرابع ثم يرجع للثالث ثم الثاني ثم الاول . ثم يرجع للدالة الرئيسية main , وهذه مصيبة لان الـ Compiler سيصبح مضطرا لإبقاء معلومات الاستدعاءات السابقة للرجوع اليها لاحقا
فبتأجيل كود الاستدعاء الذاتي لآخر تعليمة ، سيحل مشكلة بقاء معلومات الاستدعائات السابقة في الStack .
ولكن هل السي شارب تدعم هذه الفكرة ، لا .. للاسف الشديد مترجم السي شارب لا يوفر طريقة لتحقيق هذا السيناريو الهندي . والا لكان هذا البديل ممتازا جدا .
المشكلة ان اسلوب تطبيق الـ Tail Recursive يختلف من خوارزمية الى اخرى ، فليست له طريقة محددة لتنفيذه . وعند محاولة تنفيذه قد ينتهي بك الامر الى تطبيق الـ Iterative method اصلا .
ادعكم مع هذه المقالة التي تطبق الـ Tail Recursive مع دالة الـ Factorial
Tail recursion in C#
الخاتمة
يظهر ان موضوع الـ Recursive Method مزعج للغاية ، ولذلك يفضل استخدام الـ Recursive في هذه الحالات:
- عندما يكون تنفيذ الـ Iterative Method صعبا ومعقدا للغاية
- عندما لا يكون الأداء والسرعة مهمين في مشروعك ، فكما لاحظنا يوجد تفوق ساحق (نسبيا) للـ Iterative Method من ناحية الاداء
- عندما لاتكون خوارزميتك عميقة جدا
انتهى